|

Exercices corrigés MPSI-PCSI : raisonnement, ensembles, arithmétique

↩ Chapitre : Raisonnement et arithmétique (MPSI-MP) · Raisonnement et ensembles (PCSI-PSI)

Introduction

Douze exercices corrigés de raisonnement, ensembles, applications et arithmétique, classés par difficulté croissante : raisonnement par l’absurde et par récurrence, sommes, formule du binôme, injections et surjections, nombres premiers, théorème de Cantor, PGCD et congruences. Les exercices marqués (MPSI) utilisent des notions d’arithmétique propres au programme de MPSI ; tous les autres concernent aussi la PCSI.

Avant de commencer

Ces exercices s’appuient sur les résumés de cours de début d’année : calcul algébrique (MPSI), calcul algébrique (PCSI). Cherchez chaque exercice avant d’ouvrir le corrigé.

Exercices

Exercice 1 · Logique et raisonnement par l’absurde ★★★

  1. Montrer que \sqrt2 est irrationnel.
  2. Soit x\in\mathbb{R} tel que |x|\leqslant\varepsilon pour tout \varepsilon>0. Montrer que x=0.
  3. Écrire avec des quantificateurs la négation de « f:I\to\mathbb{R} est croissante ».
Corrigé

1. Supposons \sqrt2=\frac pq avec p,q\in\mathbb{N}^* et la fraction irréductible. Alors p^2=2q^2 est pair, donc p est pair (le carré d’un impair est impair) : p=2p'. Il vient q^2=2p'^2, donc q est pair aussi, ce qui contredit l’irréductibilité.

2. Si x\neq0, le choix \varepsilon=\frac{|x|}{2}>0 donne |x|\leqslant\frac{|x|}2, d’où |x|\leqslant0 : absurde. Donc x=0.

3. « f croissante » s’écrit \forall(x,y)\in I^2,\ x\leqslant y\Rightarrow f(x)\leqslant f(y). Sa négation est : \exists(x,y)\in I^2,\ x\leqslant y\text{ et }f(x)>f(y). Attention : « non croissante » ne signifie pas « décroissante ».

Exercice 2 · Une récurrence classique ★★★

Montrer que, pour tout n\geqslant1, \displaystyle\sum_{k=1}^{n}k^3=\Big(\frac{n(n+1)}{2}\Big)^2. Que remarque-t-on en comparant avec \displaystyle\sum_{k=1}^{n}k ?

Corrigé

Pour n=1, les deux membres valent 1. Si l’égalité est vraie au rang n, alors :

    \[\sum_{k=1}^{n+1}k^3=\frac{n^2(n+1)^2}{4}+(n+1)^3=\frac{(n+1)^2\big(n^2+4n+4\big)}{4}=\Big(\frac{(n+1)(n+2)}{2}\Big)^2,\]

ce qui est l’égalité au rang n+1. On remarque que \displaystyle\sum_{k=1}^{n}k^3=\Big(\sum_{k=1}^{n}k\Big)^2.

Exercice 3 · Sommes télescopiques et sommes doubles ★★★

  1. Calculer \displaystyle\sum_{k=1}^{n}\frac{1}{k(k+1)}.
  2. Calculer \displaystyle\sum_{1\leqslant i\leqslant j\leqslant n}i.
Corrigé

1. \dfrac{1}{k(k+1)}=\dfrac1k-\dfrac{1}{k+1} : la somme est télescopique et vaut 1-\dfrac{1}{n+1}=\dfrac{n}{n+1}.

2. On somme d’abord sur i à j fixé :

    \[\sum_{1\leqslant i\leqslant j\leqslant n}i=\sum_{j=1}^{n}\frac{j(j+1)}{2}=\frac12\Big(\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\Big)=\frac{n(n+1)(n+2)}{6}.\]

Exercice 4 · Formule du binôme ★★★

Soit n\geqslant1. Calculer :

  1. \displaystyle\sum_{k=0}^{n}\binom nk et \displaystyle\sum_{k=0}^{n}(-1)^k\binom nk ;
  2. \displaystyle\sum_{k=0}^{n}k\binom nk (on pourra vérifier que k\binom nk=n\binom{n-1}{k-1} pour k\geqslant1) ;
  3. la somme des \binom nk pour k pair.
Corrigé

1. La formule du binôme avec a=b=1, puis avec a=1, b=-1, donne 2^n et (1-1)^n=0 (car n\geqslant1).

2. k\binom nk=\dfrac{k\cdot n!}{k!(n-k)!}=n\cdot\dfrac{(n-1)!}{(k-1)!(n-k)!}=n\binom{n-1}{k-1}. Donc \displaystyle\sum_{k=1}^{n}k\binom nk=n\sum_{j=0}^{n-1}\binom{n-1}{j}=n\,2^{n-1}.

3. En ajoutant les deux sommes de la question 1, les termes d’indice impair se compensent : 2\displaystyle\sum_{k\text{ pair}}\binom nk=2^n, d’où une somme égale à 2^{n-1}.

Exercice 5 · Composées injectives ou surjectives ★★★

Soient g:E\to F et f:F\to G.

  1. Montrer que si f\circ g est injective, alors g est injective.
  2. Montrer que si f\circ g est surjective, alors f est surjective.
  3. Donner un exemple où f\circ g est bijective, mais où f n’est pas injective et g n’est pas surjective.
Corrigé

1. Si g(x)=g(x'), alors f(g(x))=f(g(x')), et l’injectivité de f\circ g donne x=x'.

2. Soit z\in G. Il existe x\in E tel que f(g(x))=z : l’élément y=g(x)\in F vérifie f(y)=z.

3. E=G=\{0\}, F=\{0,1\}, g(0)=0 et f constante égale à 0. Alors f\circ g=\mathrm{id}_{\{0\}} est bijective, mais f(0)=f(1) et 1 n’a pas d’antécédent par g.

Exercice 6 · Images directes et réciproques ★★★

Soit f:E\to F, A,B\subset E et C,D\subset F.

  1. Montrer que f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D) et f(A\cup B)=f(A)\cup f(B).
  2. Montrer que f(A\cap B)\subset f(A)\cap f(B), et que l’inclusion peut être stricte.
  3. Montrer que si f est injective, f(A\cap B)=f(A)\cap f(B).
Corrigé

1. x\in f^{-1}(C\cap D)\iff f(x)\in C\text{ et }f(x)\in D\iff x\in f^{-1}(C)\cap f^{-1}(D). Et y\in f(A\cup B)\iff\exists x\in A\cup B,\ y=f(x)\iff y\in f(A)\text{ ou }y\in f(B).

2. Si y=f(x) avec x\in A\cap B, alors y\in f(A) et y\in f(B). Avec f(x)=x^2 sur \mathbb{R}, A=\mathbb{R}_-, B=\mathbb{R}_+ : f(A\cap B)=\{0\} alors que f(A)\cap f(B)=\mathbb{R}_+.

3. Soit y\in f(A)\cap f(B) : y=f(a)=f(b) avec a\in A, b\in B. Par injectivité, a=b\in A\cap B, donc y\in f(A\cap B).

Exercice 7 · Nombres premiers ★★★

  1. Montrer par récurrence forte que tout entier n\geqslant2 admet au moins un diviseur premier.
  2. En déduire que l’ensemble des nombres premiers est infini.
Corrigé

1. Pour n=2, 2 est premier. Soit n\geqslant3 et supposons la propriété vraie pour tous les entiers de [\![2,n-1]\!]. Si n est premier, il est son propre diviseur premier. Sinon n=ab avec 2\leqslant a\leqslant n-1 ; par hypothèse de récurrence, a admet un diviseur premier p, qui divise aussi n.

2. Supposons qu’il n’y ait qu’un nombre fini de nombres premiers p_1,\dots,p_r, et posons N=p_1p_2\cdots p_r+1\geqslant2. D’après la question 1, N admet un diviseur premier, qui est l’un des p_i. Mais alors p_i divise N-p_1\cdots p_r=1 : absurde.

Exercice 8 · Théorème de Cantor ★★★

Soit E un ensemble et f:E\to\mathcal{P}(E) une application.

  1. On pose A=\{x\in E\ :\ x\notin f(x)\}. Montrer que A n’a pas d’antécédent par f.
  2. En déduire qu’il n’existe aucune surjection de E sur \mathcal{P}(E), mais qu’il existe une injection de E dans \mathcal{P}(E).
Corrigé

1. Supposons A=f(a) pour un a\in E. Si a\in A, alors par définition de A, a\notin f(a)=A ; si a\notin A=f(a), alors a vérifie la condition qui définit A, donc a\in A. Dans les deux cas on aboutit à une contradiction.

2. Pour toute application f:E\to\mathcal{P}(E), la partie A n’est pas atteinte : f n’est pas surjective. En revanche, x\mapsto\{x\} est injective. En particulier, il n’existe pas de bijection de \mathbb{N} sur \mathcal{P}(\mathbb{N}).

Exercice 9 · PGCD, PPCM et relation de Bézout ★★★

  1. Calculer 1071\wedge462 par l’algorithme d’Euclide.
  2. Décomposer 1071 et 462 en produit de nombres premiers ; retrouver leur PGCD et calculer leur PPCM.
  3. (MPSI) Déterminer un couple (u,v)\in\mathbb{Z}^2 tel que 1071u+462v=1071\wedge462.
Corrigé

1. 1071=2\times462+147, 462=3\times147+21, 147=7\times21. Le dernier reste non nul est 21 : 1071\wedge462=21.

2. 1071=3^2\times7\times17 et 462=2\times3\times7\times11. Le PGCD est le produit des facteurs communs avec le plus petit exposant : 3\times7=21. Le PPCM prend les plus grands exposants : 2\times3^2\times7\times11\times17=23\,562.

3. On remonte l’algorithme : 21=462-3\times147=462-3\times(1071-2\times462)=7\times462-3\times1071. Le couple (u,v)=(-3,7) convient.

Exercice 10 · Calculs de congruences (MPSI) ★★★

  1. Montrer que 7 divise 3^{2n+1}+2^{n+2} pour tout n\in\mathbb{N}.
  2. Quel est le chiffre des unités de 7^{2026} ?
  3. Montrer que le carré d’un entier impair est congru à 1 modulo 8.
Corrigé

1. 3^{2n+1}=3\times9^n\equiv3\times2^n\ [7] et 2^{n+2}=4\times2^n. Donc 3^{2n+1}+2^{n+2}\equiv7\times2^n\equiv0\ [7].

2. Modulo 10, les puissances de 7 valent 7,9,3,1, puis se répètent : 7^4\equiv1\ [10]. Comme 2026=4\times506+2, 7^{2026}\equiv7^2\equiv9\ [10] : le chiffre des unités est 9.

3. Si n=2k+1, n^2=4k(k+1)+1. Le produit k(k+1) de deux entiers consécutifs est pair, donc 4k(k+1) est multiple de 8 et n^2\equiv1\ [8].

Exercice 11 · PGCD de nombres de Mersenne (MPSI) ★★★

Soient m,n\in\mathbb{N}^*. Montrer que (2^m-1)\wedge(2^n-1)=2^{m\wedge n}-1.

Corrigé

Lemme. Pour q\in\mathbb{N}, 2^n-1 divise 2^{qn}-1, car a^q-1=(a-1)(a^{q-1}+\dots+1) avec a=2^n.

Étape. Écrivons la division euclidienne m=qn+r, 0\leqslant r<n. Alors 2^m-1=2^r\big(2^{qn}-1\big)+\big(2^r-1\big). Comme 2^n-1 divise 2^{qn}-1, on a 2^m-1\equiv2^r-1 modulo 2^n-1, et donc (2^m-1)\wedge(2^n-1)=(2^n-1)\wedge(2^r-1) (on ne change pas le PGCD de deux entiers en retranchant à l’un un multiple de l’autre).

Conclusion. Le couple d’exposants (m,n) est remplacé par (n,r), exactement comme dans l’algorithme d’Euclide appliqué à (m,n). Celui-ci s’arrête sur (m\wedge n,0), et (2^{m\wedge n}-1)\wedge(2^0-1)=(2^{m\wedge n}-1)\wedge0=2^{m\wedge n}-1.

Exercice 12 · Petit théorème de Fermat (MPSI) ★★★

Soit p un nombre premier.

  1. Montrer que p divise \binom pk pour 1\leqslant k\leqslant p-1.
  2. En déduire que (a+1)^p\equiv a^p+1\ [p] pour tout a\in\mathbb{Z}, puis que a^p\equiv a\ [p] pour tout a\in\mathbb{N}, et enfin pour tout a\in\mathbb{Z}.
  3. Montrer que si p ne divise pas a, alors a^{p-1}\equiv1\ [p].
Corrigé

1. On a k\binom pk=p\binom{p-1}{k-1}, donc p divise k\binom pk. Comme 1\leqslant k\leqslant p-1 et p est premier, p\wedge k=1 : par le lemme de Gauss, p divise \binom pk.

2. Par la formule du binôme, (a+1)^p=a^p+1+\displaystyle\sum_{k=1}^{p-1}\binom pka^k\equiv a^p+1\ [p]. Par récurrence sur a\in\mathbb{N} : 0^p\equiv0, et si a^p\equiv a, alors (a+1)^p\equiv a+1. Pour a<0 : si p est impair, a^p=-(-a)^p\equiv-(-a)=a ; si p=2, a^2-a=a(a-1) est pair.

3. p divise a^p-a=a\,(a^{p-1}-1) et p\wedge a=1 : le lemme de Gauss donne p\mid a^{p-1}-1.


Pour aller plus loin

Besoin d’aide sur ce chapitre ?

Un blocage sur une notion, une méthode de rédaction à acquérir, un devoir ou un concours à préparer : Pr. Elakili, agrégé de mathématiques depuis 1991, plus de 20 ans d’enseignement en classes préparatoires, propose des cours particuliers, en présentiel à Casablanca, ou à distance, partout au Maroc et en France.

Publications similaires