Exercices — Arithmétique dans l'ensemble des entiers relatifs

Pour $a$ et $b$ entiers relatifs, on rappelle que $a\mid b$ signifie qu'il existe $k\in \mathbb{Z}$ tel que $b=ka$.

1. Déterminer tous les diviseurs positifs de $60$, puis de $84$, en balayant les entiers $d$ tels que $1⩽d⩽\lfloor \sqrt{n}\rfloor$. Justifier au préalable que ce balayage les donne bien tous.

2. Les affirmations suivantes, où $a$, $b$ et $c$ désignent des entiers relatifs, sont-elles vraies ou fausses ? Justifier chaque réponse.

   a. Si $a\mid b$ et $b\mid c$, alors $a\mid c$.

   b. Si $a\mid b$ et $a\mid c$, alors $a\mid (3b-5c)$.

   c. Tout entier relatif divise $0$.

   d. Si $0\mid b$, alors $b=0$.

   e. Si $a\mid b$ et $b\mid a$, alors $a=b$ ou $a=-b$.

3. Déterminer tous les entiers $n\in \mathbb{Z}$ tels que $n\mid 12$, puis tous les entiers $n\in \mathbb{Z}$ tels que $(n-1)\mid 6$.

4. Soit $n\in \mathbb{Z}$. Montrer que $2\mid n(n+1)$, puis que $3\mid n(n+1)(n+2)$.

On rappelle le théorème de la division euclidienne : pour tout $a\in \mathbb{Z}$ et tout $b\in {\mathbb{N}}^{\ast }$, il existe un unique couple $(q,r)\in \mathbb{Z}\times \mathbb{N}$ tel que $a=bq+r$ et $0⩽r<b$. La condition $0⩽r<b$ fait partie de l'énoncé : c'est elle qui assure l'unicité.

1. Effectuer les divisions euclidiennes suivantes, en précisant à chaque fois le quotient et le reste.

   a. $37$ par $5$

   b. $-37$ par $5$

   c. $100$ par $7$

   d. $-100$ par $7$

2. Donner le quotient et le reste de la division euclidienne de $2026$ par $7$, par $12$, puis par $100$.

3. Déterminer tous les entiers compris entre $-20$ et $30$ dont le reste dans la division euclidienne par $7$ vaut $3$.

4. Soit $n\in \mathbb{Z}$. En discutant selon le reste de $n$ dans la division euclidienne par $3$, déterminer les valeurs possibles du reste de $n^2$ par $3$. En déduire qu'un carré d'entier n'est jamais congru à $2$ modulo $3$, puis que $2024$ n'est pas le carré d'un entier.

On rappelle le principe de l'algorithme d'Euclide : si $a=bq+r$, alors les couples $(a,b)$ et $(b,r)$ ont les mêmes diviseurs communs, donc $a\wedge b=b\wedge r$. En itérant, le dernier reste non nul est le PGCD. On rappelle également que pour $a$ et $b$ entiers non nuls, $(a\wedge b)(a\vee b)=\mathrm{\mid }ab\mathrm{\mid }$.

1. Calculer les PGCD suivants par l'algorithme d'Euclide, en écrivant toutes les divisions euclidiennes effectuées.

   a. $1071\wedge 462$

   b. $4147\wedge 2513$

   c. $2026\wedge 1998$

2. En déduire les PPCM $1071\vee 462$, $4147\vee 2513$ et $2026\vee 1998$.

3. Vérifier la cohérence de chaque résultat de la question 1. en contrôlant que le PGCD obtenu divise effectivement les deux entiers de départ.

Le théorème de Bézout affirme que pour tous entiers $a$ et $b$ non tous deux nuls, il existe un couple $(u,v)\in {\mathbb{Z}}^2$ tel que $au+bv=a\wedge b$. La démonstration constructive consiste à dérouler l'algorithme d'Euclide, puis à le remonter en exprimant chaque reste à l'aide des deux nombres précédents.

1. Pour chacun des couples $(a,b)$ suivants, calculer $a\wedge b$ par l'algorithme d'Euclide, puis déterminer par remontée un couple $(u,v)\in {\mathbb{Z}}^2$ tel que $au+bv=a\wedge b$. Vérifier l'égalité obtenue.

   a. $a=17$, $b=40$

   b. $a=91$, $b=65$

   c. $a=2026$, $b=1147$

2. Le couple $(u,v)$ obtenu à la question 1. a. n'est pas unique : en exhiber un second, puis expliquer comment en fabriquer une infinité.

On rappelle que tout entier $n⩾2$ s'écrit de manière unique, à l'ordre des facteurs près, sous la forme $n=p_1^{{\alpha }_1}\cdots p_s^{{\alpha }_s}$ où les $p_i$ sont des nombres premiers deux à deux distincts et les ${\alpha }_i$ des entiers strictement positifs. Pour $p\in \mathcal{P}$, on note $v_p(n)$ l'exposant de $p$ dans cette décomposition, nul si $p$ ne divise pas $n$.

1. Décomposer en produit de facteurs premiers les entiers suivants.

   a. $360$

   b. $1001$

   c. $2026$

   d. $5544$

2. En déduire le nombre de diviseurs positifs de chacun de ces quatre entiers, après avoir justifié la formule utilisée.

3. Calculer $360\wedge 5544$ et $360\vee 5544$ à l'aide des exposants (minimum et maximum), puis vérifier le PGCD par l'algorithme d'Euclide.

4. Montrer que les entiers $n⩾1$ dont tous les exposants de la décomposition sont pairs sont exactement les carrés parfaits.

On rappelle qu'un entier $n⩾2$ est premier lorsque ses seuls diviseurs positifs sont $1$ et $n$, et l'on note $\mathcal{P}$ l'ensemble des nombres premiers. On admet le résultat suivant, démontré en cours : tout entier $n⩾2$ admet au moins un diviseur premier.

1. Décrire le crible d'Ératosthène permettant d'obtenir tous les nombres premiers inférieurs à $100$, en justifiant à quel moment on peut arrêter de rayer. Donner la liste obtenue.

2. Démontrer le critère suivant : si $n⩾2$ n'admet aucun diviseur premier $p$ tel que $p⩽\sqrt{n}$, alors $n$ est premier.

3. À l'aide de ce critère, déterminer si les entiers suivants sont premiers. Lorsqu'ils ne le sont pas, donner leur décomposition en facteurs premiers.

   a. $221$

   b. $223$

   c. $391$

   d. $401$

Pour $n⩾1$, on rappelle que $a\equiv b[n]$ signifie que $n\mid (a-b)$, et que cette relation est compatible avec l'addition et la multiplication : si $a\equiv b[n]$ et $c\equiv d[n]$, alors $a+c\equiv b+d[n]$ et $ac\equiv bd[n]$. En particulier, $a\equiv b[n]$ entraîne $a^k\equiv b^k[n]$ pour tout $k\in \mathbb{N}$. Aucun des calculs ci-dessous ne nécessite de théorème : tout se fait à la main, en cherchant une petite puissance congrue à $1$ ou à $-1$.

1. Déterminer les restes suivants.

   a. le reste de $3^{2026}$ dans la division par $7$

   b. le dernier chiffre de l'écriture décimale de $7^{2026}$

   c. le reste de $2^{2026}$ modulo $5$

   d. le reste de ${12}^{34}$ modulo $11$

2. Dégager de ces quatre exemples une méthode générale pour calculer le reste de $a^m$ modulo $n$ à la main.

Soit $n\in {\mathbb{N}}^{\ast }$, d'écriture décimale $n={\displaystyle \sum _{k=0}^p{a}_k{10}^k}$, où les chiffres $a_k$ appartiennent à $\{0,1,\dots ,9\}$ et $a_p\mathrm{\ne }0$. On note $S={\displaystyle \sum _{k=0}^p{a}_k}$ la somme de ses chiffres et $T={\displaystyle \sum _{k=0}^p(-1{)}^k{a}_k}$ sa somme alternée, commencée au chiffre des unités.

1. Établir que $10\equiv 1[9]$, puis démontrer que $n\equiv S[9]$. En déduire les critères de divisibilité par $9$ et par $3$.

2. Établir que $10\equiv -1[11]$, puis démontrer que $n\equiv T[11]$. En déduire le critère de divisibilité par $11$.

3. Appliquer ces trois critères aux entiers suivants : sont-ils divisibles par $3$, par $9$, par $11$ ?

   a. $2026371$

   b. $8514$

   c. $123456$

   d. $90728$

4. On note $\overline{51x3}$ l'entier à quatre chiffres dont les chiffres sont $5$, $1$, $x$ et $3$ dans cet ordre, avec $x\in \{0,1,\dots ,9\}$. Déterminer les valeurs de $x$ pour lesquelles $\overline{51x3}$ est divisible par $9$, puis celles pour lesquelles il est divisible par $11$.

Dans tout l'exercice, $n$ désigne un entier relatif. On rappelle que si un entier $d$ divise deux entiers $u$ et $v$, alors $d$ divise toute combinaison linéaire $\alpha u+\beta v$, où $\alpha$ et $\beta$ sont des entiers. C'est cette propriété qui permet d'éliminer $n$ et de se ramener à une divisibilité par un entier fixe.

1. La méthode, sur un premier exemple. On cherche tous les $n\in \mathbb{Z}$ tels que $(n+3)\mid (n^2+1)$.

   a. Vérifier que, pour tout $n\in \mathbb{Z}$, $n^2+1=(n+3)(n-3)+10$.

   b. En déduire que $(n+3)\mid (n^2+1)$ si et seulement si $(n+3)\mid 10$.

   c. Conclure en dressant la liste des entiers $n$ solutions, et vérifier chacun d'eux.

2. Déterminer tous les $n\in \mathbb{Z}$ tels que $(n-2)\mid (3n+5)$.

3. Déterminer tous les $n\in \mathbb{Z}$ tels que $(2n+1)\mid (n+7)$. On pourra remarquer que $2n+1$ est impair, donc premier avec $2$, et considérer $2(n+7)$.

4. Déterminer tous les $n\in \mathbb{Z}$ tels que $(n+1)\mid (n^3+2)$. On cherchera une identité analogue à celle de la question 1. a.

On rappelle que la relation de congruence est compatible avec le produit : si $x\equiv r[m]$, alors $x^2\equiv r^2[m]$. Comme tout entier est congru modulo $m$ à son reste dans la division euclidienne par $m$, il suffit d'un petit tableau pour connaître tous les restes possibles d'un carré.

1. Déterminer les restes possibles du carré d'un entier dans la division euclidienne par $4$, puis par $3$, puis par $8$. On présentera à chaque fois un tableau de valeurs.

2. En déduire qu'aucun entier de la forme $4k+3$, avec $k\in \mathbb{Z}$, n'est somme de deux carrés d'entiers.

3. On s'intéresse à l'équation $x^2+y^2=2026$, d'inconnue $(x,y)\in {\mathbb{Z}}^2$.

   a. Montrer que si $(x,y)$ est solution, alors $x$ et $y$ sont tous les deux impairs.

   b. Que donne le passage modulo $8$ ? Peut-on conclure par les seules congruences ?

   c. Montrer que l'on peut se ramener au cas $0⩽x⩽y$, puis établir l'encadrement $33⩽y⩽45$. Conclure en dressant la liste de toutes les solutions dans ${\mathbb{Z}}^2$.

4. Montrer que l'équation $x^2-y^2=2026$ n'admet aucune solution dans ${\mathbb{Z}}^2$.

5. Soient $x$ et $y$ deux entiers. Montrer que si $3\mid x^2+y^2$, alors $3\mid x$ et $3\mid y$.

Dans tout l'exercice, $n$ désigne un entier relatif. On rappelle deux propriétés qui suffisent à mener tous les calculs :

• si $d$ divise $u$ et $v$, alors $d$ divise $\alpha u+\beta v$ pour tous entiers $\alpha$ et $\beta$ ; en particulier $u\wedge v$ divise toute combinaison linéaire de $u$ et de $v$ ;
• tout diviseur commun de $u$ et de $v$ divise $u\wedge v$.

La méthode est toujours la même : on cherche une combinaison linéaire de $u$ et de $v$ qui élimine $n$, ce qui majore le PGCD ; on détermine ensuite, par une étude de cas selon la congruence de $n$, quelle valeur est effectivement atteinte.

1. On pose $d=(n+1)\wedge (n^2+1)$.

   a. Montrer que $d$ divise $2$.

   b. Déterminer $d$ en fonction de la parité de $n$.

2. Calculer $(3n+2)\wedge (5n+3)$ pour tout $n\in \mathbb{Z}$.

3. Calculer $(2n+1)\wedge (9n+4)$ pour tout $n\in \mathbb{Z}$.

4. On pose $d=n\wedge (n+6)$. Montrer que $d=n\wedge 6$, puis déterminer $d$ selon le reste de $n$ dans la division euclidienne par $6$.

Résoudre une équation $ax+by=c$ dans ${\mathbb{Z}}^2$ suit toujours le même plan : condition d'existence (l'équation a des solutions si et seulement si $a\wedge b$ divise $c$), recherche d'une solution particulière, puis passage à la solution générale par le lemme de Gauss, et enfin réciproque.

1. On considère l'équation $17x+40y=1$, d'inconnue $(x,y)\in {\mathbb{Z}}^2$.

   a. Appliquer l'algorithme d'Euclide à $40$ et $17$, puis remonter les calculs pour obtenir un couple d'entiers $(x_0,y_0)$ tel que $17x_0+40y_0=1$.

   b. Résoudre l'équation dans ${\mathbb{Z}}^2$, en rédigeant intégralement l'analyse et la synthèse.

2. Résoudre dans ${\mathbb{Z}}^2$ l'équation $17x+40y=7$.

3. Résoudre dans ${\mathbb{Z}}^2$ l'équation $12x+18y=30$.

4. Montrer que l'équation $35x+21y=8$ n'admet aucune solution dans ${\mathbb{Z}}^2$.

5. Un collège commande des manuels à $17$ euros pièce et des calculatrices à $40$ euros pièce. La facture s'élève exactement à $2026$ euros. Déterminer tous les couples $(x,y)\in {\mathbb{N}}^2$ possibles, où $x$ est le nombre de manuels et $y$ celui de calculatrices. Combien y a-t-il de commandes possibles ?

On rappelle le théorème de Bézout : deux entiers $u$ et $v$ sont premiers entre eux si et seulement s'il existe des entiers $\alpha$ et $\beta$ tels que $\alpha u+\beta v=1$. C'est l'outil central de cet exercice : pour montrer que deux entiers sont premiers entre eux, on exhibe une telle relation, ou bien on montre que tout diviseur commun divise $1$.

1. Préliminaire. Soient $a$, $b$ et $c$ trois entiers tels que $c\wedge a=1$ et $c\wedge b=1$. En multipliant deux relations de Bézout, montrer que $c\wedge ab=1$.

Dans les questions 2. et 3., $a$ et $b$ désignent deux entiers tels que $a\wedge b=1$.

2. a. Montrer que $(a+b)\wedge a=1$ et que $(a+b)\wedge b=1$.

   b. En déduire que $(a+b)\wedge ab=1$.

3. On pose $d=(a+b)\wedge (a-b)$.

   a. Montrer que $d$ divise $2$.

   b. Montrer que $a$ et $b$ ne peuvent pas être tous les deux pairs, puis déterminer $d$ selon les parités de $a$ et de $b$.

4. Soit $n\in \mathbb{Z}$.

   a. Montrer que $n\wedge (n+1)=1$.

   b. Montrer que $(2n+1)\wedge n(n+1)=1$.

5. Soient $a$ et $b$ deux entiers premiers entre eux. Montrer que $a^m\wedge b^k=1$ pour tous $m,k\in {\mathbb{N}}^{\ast }$.

On rappelle deux résultats du cours, valables pour $x$ et $y$ dans ${\mathbb{N}}^{\ast }$ et $d=x\wedge y$ :

• il existe $x^{\mathrm{\prime }}$ et $y^{\mathrm{\prime }}$ dans ${\mathbb{N}}^{\ast }$ tels que $x=d{x}^{\mathrm{\prime }}$, $y=d{y}^{\mathrm{\prime }}$ et $x^{\mathrm{\prime }}\wedge y^{\mathrm{\prime }}=1$ ;
• $(x\wedge y)\times (x\vee y)=xy$.

La méthode est toujours la même : on pose $x=d{x}^{\mathrm{\prime }}$ et $y=d{y}^{\mathrm{\prime }}$ avec $x^{\mathrm{\prime }}\wedge y^{\mathrm{\prime }}=1$, on traduit la seconde condition sur le couple $(x^{\mathrm{\prime }},y^{\mathrm{\prime }})$, on énumère les possibilités, puis on revient à $(x,y)$ sans oublier de vérifier les candidats.

0. Préliminaire. Soient $d\in {\mathbb{N}}^{\ast }$ et $x^{\mathrm{\prime }}$, $y^{\mathrm{\prime }}$ deux entiers tels que $x^{\mathrm{\prime }}\wedge y^{\mathrm{\prime }}=1$. Montrer que $(d{x}^{\mathrm{\prime }})\wedge (d{y}^{\mathrm{\prime }})=d$.

1. Déterminer tous les couples $(x,y)\in ({\mathbb{N}}^{\ast }{)}^2$ tels que $x\wedge y=12$ et $x\vee y=180$.

2. Déterminer tous les couples $(x,y)\in ({\mathbb{N}}^{\ast }{)}^2$ tels que $x\wedge y=5$ et $x+y=100$.

3. Déterminer tous les couples $(x,y)\in ({\mathbb{N}}^{\ast }{)}^2$ tels que $xy=1734$ et $x\wedge y=17$. On pourra commencer par vérifier que $1734=2\times 3\times {17}^2$.

On rappelle le lemme de Gauss : si $a\mid bc$ et $a\wedge b=1$, alors $a\mid c$. On utilisera aussi librement le résultat suivant, établi dans l'exercice sur les entiers premiers entre eux : si $p\wedge q=1$, alors $p\wedge q^2=1$.

1. Soient $a$, $b$ et $c$ trois entiers tels que $a\mid c$, $b\mid c$ et $a\wedge b=1$. Montrer que $ab\mid c$.

2. Donner un contre-exemple montrant que l'hypothèse $a\wedge b=1$ est indispensable.

3. Soit $n\in \mathbb{Z}$. En déduire les équivalences suivantes, en justifiant à chaque fois l'hypothèse de primalité entre eux :

   a. $6\mid n⟺2\mid n$ et $3\mid n$

   b. $12\mid n⟺3\mid n$ et $4\mid n$

   c. $35\mid n⟺5\mid n$ et $7\mid n$

   Pourquoi ne peut-on pas écrire « $12\mid n$ si et seulement si $2\mid n$ et $6\mid n$ » ?

4. Soit $r\in \mathbb{Q}$. Montrer qu'il existe un unique couple $(p,q)\in \mathbb{Z}\times {\mathbb{N}}^{\ast }$ tel que $p\wedge q=1$ et $r={\displaystyle \frac{p}{q}}$ : c'est la forme irréductible de $r$.

5. Soient $a$, $b$, $c$ trois entiers avec $a\mathrm{\ne }0$, et soit ${\displaystyle \frac{p}{q}}$ la forme irréductible d'un rationnel solution de $a{x}^2+bx+c=0$.

   a. Montrer que $a{p}^2+bpq+c{q}^2=0$, puis en déduire que $p\mid c$ et que $q\mid a$.

   b. Application : déterminer les solutions rationnelles de $6x^2-5x+1=0$.

Pour $p\in \mathcal{P}$ et $m\in {\mathbb{N}}^{\ast }$, on note $v_p(m)$ l'exposant de $p$ dans la décomposition de $m$ en produit de facteurs premiers. On rappelle qu'un entier $n\in \mathbb{N}$ est un carré parfait lorsqu'il existe $k\in \mathbb{N}$ tel que $n=k^2$.

1. a. Démontrer que $\sqrt{2}$ est irrationnel en écrivant $\sqrt{2}={\displaystyle \frac{a}{b}}$ avec $a\wedge b=1$, puis en étudiant la parité de $a$, et enfin celle de $b$.

   b. Retrouver ce résultat par une seconde méthode, en comparant les valuations $2$-adiques des deux membres de l'égalité $a^2=2b^2$.

2. Soit $p\in \mathcal{P}$. Démontrer que $\sqrt{p}$ est irrationnel.

3. Soit $n\in {\mathbb{N}}^{\ast }$. Démontrer que $\sqrt{n}$ est irrationnel si et seulement si $n$ n'est pas un carré parfait.

4. On pose $x=\sqrt{2}+\sqrt{3}$. Calculer $x^2$, puis exprimer $\sqrt{6}$ à l'aide de $x^2$. En déduire que $x$ est irrationnel.

5. On note ${\log }_{10}(2)$ l'unique réel $t$ tel que ${10}^t=2$, c'est-à-dire $t={\displaystyle \frac{\ln 2}{\ln 10}}$. Démontrer que ${\log }_{10}(2)$ est irrationnel. On pourra supposer ${\log }_{10}(2)={\displaystyle \frac{p}{q}}$ avec $p\in \mathbb{Z}$ et $q\in {\mathbb{N}}^{\ast }$, et se ramener à l'égalité $2^q={10}^p$.

Soit $p\in \mathcal{P}$. Pour $a\in {\mathbb{N}}^{\ast }$, on note $v_p(a)$ l'exposant de $p$ dans la décomposition de $a$ en produit de facteurs premiers, de sorte que $a={\prod }_{q\in \mathcal{P}}{q}^{v_q(a)}$, ce produit ne comportant qu'un nombre fini de facteurs différents de $1$. On admet la caractérisation équivalente : pour tout $k\in \mathbb{N}$, $p^k\mid a$ si et seulement si $k⩽v_p(a)$. Dans tout l'exercice, $a$ et $b$ désignent des éléments de ${\mathbb{N}}^{\ast }$.

1. a. Démontrer que $v_p(ab)=v_p(a)+v_p(b)$.

   b. En déduire que $v_p(a^n)=n{v}_p(a)$ pour tout $n\in \mathbb{N}$.

2. a. Démontrer que $v_p(a+b)⩾\min (v_p(a),v_p(b))$.

   b. Démontrer qu'il y a égalité dès que $v_p(a)\mathrm{\ne }{v}_p(b)$.

   c. Donner un exemple où $v_p(a)=v_p(b)$ et où l'inégalité de 2. a. est stricte.

3. Démontrer que $a\mid b$ si et seulement si $v_q(a)⩽v_q(b)$ pour tout $q\in \mathcal{P}$.

4. Démontrer que $v_q(a\wedge b)=\min (v_q(a),v_q(b))$ et $v_q(a\vee b)=\max (v_q(a),v_q(b))$ pour tout $q\in \mathcal{P}$. En déduire $(a\wedge b)(a\vee b)=ab$.

5. Calculer $v_3(5544)$, puis $v_2(360\times 5544)$.

6. Démontrer que $a$ est un carré parfait si et seulement si $v_q(a)$ est pair pour tout $q\in \mathcal{P}$.

7. Démontrer que si $a^2\mid b^2$, alors $a\mid b$.

Pour $n\in {\mathbb{N}}^{\ast }$, on note $d(n)$ le nombre de diviseurs positifs de $n$ et $\sigma (n)$ la somme de ces diviseurs. Par exemple, les diviseurs positifs de $10$ sont $1$, $2$, $5$ et $10$, donc $d(10)=4$ et $\sigma (10)=18$.

Dans les questions 1. à 4., on considère un entier $n⩾2$ dont la décomposition en facteurs premiers s'écrit $n=p_1^{{\alpha }_1}\cdots p_r^{{\alpha }_r}$, où $p_1,\dots ,p_r$ sont des nombres premiers deux à deux distincts et ${\alpha }_1,\dots ,{\alpha }_r\in {\mathbb{N}}^{\ast }$.

1. Démontrer que les diviseurs positifs de $n$ sont exactement les entiers de la forme $p_1^{{\beta }_1}\cdots p_r^{{\beta }_r}$ avec $0⩽{\beta }_i⩽{\alpha }_i$ pour tout $i\in \{1,\dots ,r\}$, et que deux choix distincts de $({\beta }_1,\dots ,{\beta }_r)$ donnent deux diviseurs distincts.

2. En déduire que $d(n)={\displaystyle \prod _{i=1}^r({\alpha }_i+1)}$.

3. En développant le produit ${\displaystyle \prod _{i=1}^r(1+p_i+\cdots +p_i^{{\alpha }_i})}$, démontrer que $\sigma (n)={\displaystyle \prod _{i=1}^r\frac{p_i^{{\alpha }_i+1}-1}{p_i-1}}$.

4. Calculer $d(n)$ et $\sigma (n)$ pour $n=360$, $n=2026$ et $n=1024$.

5. Déterminer tous les entiers $n⩾1$ tels que $d(n)=6$, et donner les cinq plus petits.

6. Démontrer que $d(n)$ est impair si et seulement si $n$ est un carré parfait.

Soient $n⩾2$ un entier et $a\in \mathbb{Z}$. On dit qu'un entier $u$ est un inverse de $a$ modulo $n$ lorsque $au\equiv 1[n]$.

1. a. Démontrer que $a$ admet un inverse modulo $n$ si et seulement si $a\wedge n=1$.

   b. Démontrer que, dans ce cas, deux inverses de $a$ modulo $n$ sont congrus modulo $n$.

   c. Déterminer un inverse de $7$ modulo $13$, puis un inverse de $5$ modulo $7$.

2. Résoudre dans $\mathbb{Z}$ l'équation $7x\equiv 3[13]$.

3. Résoudre dans $\mathbb{Z}$ l'équation $15x\equiv 9[21]$.

4. Résoudre dans $\mathbb{Z}$ les équations $6x\equiv 4[10]$, puis $4x\equiv 3[10]$.

5. Soient $a,b\in \mathbb{Z}$ et $d=a\wedge n$. Démontrer que l'équation $ax\equiv b[n]$ admet des solutions si et seulement si $d\mid b$, et qu'elle équivaut alors à une unique condition de la forme $x\equiv x_0\left[\frac{n}{d}\right]$. Combien de valeurs distinctes le reste de $x$ dans la division euclidienne par $n$ peut-il prendre ?

On rappelle le petit théorème de Fermat : si $p\in \mathcal{P}$ et si $a\in \mathbb{Z}$ n'est pas divisible par $p$, alors $a^{p-1}\equiv 1[p]$ ; sous la seule hypothèse $p\in \mathcal{P}$, on a $a^p\equiv a[p]$ pour tout $a\in \mathbb{Z}$.

1. Déterminer le reste de la division euclidienne de $3^{2026}$ par $17$.

2. Déterminer le reste de la division euclidienne de $5^{2026}$ par $13$.

3. Soit $n\in \mathbb{Z}$.

   a. Démontrer que $7\mid n^7-n$.

   b. Démontrer que $2\mid n^7-n$ et que $3\mid n^7-n$.

   c. En déduire que $42\mid n^7-n$.

4. Démontrer que $30\mid n^5-n$ pour tout $n\in \mathbb{Z}$.

5. a. Vérifier que $4\wedge 9=1$, puis calculer le reste de $4^8$ dans la division euclidienne par $9$. Qu'en déduit-on sur l'hypothèse « $p$ est premier » ?

   b. Vérifier que $2^{10}\equiv 1[341]$, puis en déduire que $2^{340}\equiv 1[341]$. Sachant que $341=11\times 31$, que peut-on dire de la réciproque du petit théorème de Fermat ?

Aucun résultat tout fait n'est utilisé dans cet exercice : chaque système se résout à la main, en paramétrant la première congruence et en reportant dans la suivante.

On cherche d'abord les entiers $x$ vérifiant simultanément

$$\begin{array}{rl}{\displaystyle x}& {\displaystyle \equiv 2[7]}\\ {\displaystyle x}& {\displaystyle \equiv 3[11]}\end{array}$$

1. a. Justifier que la première condition équivaut à l'existence de $k\in \mathbb{Z}$ tel que $x=2+7k$.

   b. Reporter dans la seconde condition et montrer qu'elle équivaut à $7k\equiv 1[11]$. Résoudre en $k$.

   c. En déduire que l'ensemble des solutions est décrit par une unique congruence modulo $77$.

2. Résoudre de même le système $x\equiv 1[3]$, $x\equiv 2[5]$ et $x\equiv 3[7]$, en traitant d'abord les deux premières conditions.

3. Résoudre le système $x\equiv 1[6]$ et $x\equiv 4[10]$. Plus généralement, démontrer qu'un système $x\equiv b[m]$, $x\equiv b^{\mathrm{\prime }}[m^{\mathrm{\prime }}]$ ne peut avoir de solution que si $b\equiv b^{\mathrm{\prime }}[m\wedge m^{\mathrm{\prime }}]$.

4. Un panier contient moins de $200$ œufs. En les groupant par $3$, il en reste $2$ ; en les groupant par $5$, il en reste $3$ ; en les groupant par $7$, il en reste $2$. Déterminer tous les nombres d'œufs possibles.

Partie A. Clé du numéro de sécurité sociale. Le numéro d'inscription au répertoire est formé de $13$ chiffres (sexe, année et mois de naissance, département, commune, numéro d'ordre), qui constituent un entier $N$. On lui adjoint une clé de contrôle définie par $\text{cl}\acute{\text{e}}=97-r$, où $r$ est le reste de la division euclidienne de $N$ par $97$. On travaille sur le numéro fabriqué $N=1851244123456$.

1. a. Calculer la clé de $N$, sachant que $97\times 19084990963=1851244123411$.

   b. Une erreur de saisie remplace le septième chiffre, $4$, par un $5$ : le numéro devient $N^{\mathrm{\prime }}=1851245123456$. Calculer sa clé et constater qu'elle diffère de la précédente.

   c. Démontrer que toute erreur portant sur un seul chiffre du numéro modifie la clé, et donc est détectée.

Partie B. Clé ISBN-10. Un ISBN-10 est une suite $(a_1,\dots ,a_{10})$ où $a_k\in \{0,\dots ,9\}$ pour $k\in \{1,\dots ,9\}$ et $a_{10}\in \{0,\dots ,10\}$ (la valeur $10$ s'écrivant X), soumise à la condition de validité

$$\sum _{k=1}^{10}k{a}_k\equiv 0[11]$$

2. a. Vérifier que $2841775429$ est un ISBN-10 valide.

   b. Le cinquième chiffre de ce code est devenu illisible : $2841?75429$. Le retrouver.

   c. Démontrer plus généralement qu'un chiffre effacé, en position quelconque, est déterminé de façon unique par les neuf autres.

3. a. Deux chiffres distincts, situés à des positions différentes, sont intervertis par erreur. Démontrer que la condition de validité n'est alors plus satisfaite : l'erreur est détectée. Illustrer en échangeant $a_2$ et $a_3$ dans le code de la question 2. a.

   b. Démontrer qu'une clé calculée uniquement à partir de la somme $a_1+\cdots +a_{10}$ ne détecterait pas cette interversion.

Dans tout l'exercice, $a$ désigne un entier tel que $a⩾2$.

1. Soit $n\in {\mathbb{N}}^{\ast }$. Établir l'identité

   $$a^n-1=(a-1)\sum _{k=0}^{n-1}{a}^k\mathrm{.}$$

   En déduire que $(a-1)\mid (a^n-1)$.

2. Soient $d,n\in {\mathbb{N}}^{\ast }$ tels que $d\mid n$. Montrer que $(a^d-1)\mid (a^n-1)$.

3. Soit $n⩾2$. On suppose que $a^n-1$ est un nombre premier. a. Montrer que $a=2$. b. Montrer que $n$ est un nombre premier.

   Les entiers $M_n=2^n-1$ sont appelés nombres de Mersenne. Autrement dit, parmi tous les entiers de la forme $a^n-1$, seuls les $M_n$ d'indice $n$ premier ont une chance d'être premiers.

4. La réciproque est-elle vraie ? Étudier le cas $n=11$, sachant que $23\times 89=2047$.

5. Soit $m\in {\mathbb{N}}^{\ast }$ un entier impair. Établir l'identité

   $$a^m+1=(a+1)\sum _{k=0}^{m-1}(-1{)}^k{a}^k,$$

   et en déduire que $(a+1)\mid (a^m+1)$.

6. Soit $n\in {\mathbb{N}}^{\ast }$. On suppose que $2^n+1$ est un nombre premier. Montrer que $n$ est une puissance de $2$, c'est-à-dire qu'il existe $s\in \mathbb{N}$ tel que $n=2^s$.

   Indication. Écrire $n=2^{s}m$ avec $m$ impair, puis appliquer la question 5 à $a=2^{2^s}$.

Pour $n\in \mathbb{N}$, on pose $M_n=2^n-1$. On remarquera que $M_0=0$ et que $M_n⩾1$ dès que $n⩾1$.

L'objectif est de démontrer la formule remarquable

$$M_m\wedge M_n=M_{m\wedge n}\text{pour tous }m,n\in \mathbb{N}\text{ non tous les deux nuls}\mathrm{.}$$

1. Soient $m\in \mathbb{N}$ et $n\in {\mathbb{N}}^{\ast }$. On note $m=qn+r$ la division euclidienne de $m$ par $n$, avec $q\in \mathbb{N}$ et $0⩽r<n$. Montrer que

   $$2^m\equiv 2^r[M_n],\text{puis que}{M}_m\equiv M_r[M_n]\mathrm{.}$$

2. En déduire que $M_m\wedge M_n=M_n\wedge M_r$.

   Indication. Montrer que les couples $(M_m,M_n)$ et $(M_r,M_n)$ ont exactement les mêmes diviseurs communs.

3. Démontrer par récurrence forte sur $n\in \mathbb{N}$ la propriété ${\mathcal{H}}_n$ suivante : « pour tout $m\in \mathbb{N}$ tel que $(m,n)\mathrm{\ne }(0,0)$, $M_m\wedge M_n=M_{m\wedge n}$ ». On expliquera en quoi la démonstration consiste à « transporter » l'algorithme d'Euclide des exposants vers les nombres de Mersenne.

4. Calculer $(2^{12}-1)\wedge (2^{18}-1)$, puis $(2^{100}-1)\wedge (2^{60}-1)$.

5. En déduire que, pour $m,n\in {\mathbb{N}}^{\ast }$, les entiers $M_m$ et $M_n$ sont premiers entre eux si et seulement si $m$ et $n$ le sont.

Pour $n\in \mathbb{N}$, on appelle $n$-ième nombre de Fermat l'entier

$$F_n=2^{2^n}+1.$$

On notera $\mathcal{P}$ l'ensemble des nombres premiers. Attention à l'ordre des exponentiations : l'exposant de $2$ est lui-même $2^n$.

1. Calculer $F_0$, $F_1$, $F_2$, $F_3$ et $F_4$. Vérifier au passage que $F_0$, $F_1$, $F_2$ et $F_3$ sont premiers (on admettra que $F_4=65537$ l'est également).

2. Montrer que, pour tout $n\in \mathbb{N}$, l'entier $F_n$ est impair et vérifie $F_n⩾3$.

3. Démontrer par récurrence que, pour tout $n\in {\mathbb{N}}^{\ast }$,

   $$\prod _{k=0}^{n-1}{F}_k=F_n-2.$$

4. En déduire que les nombres de Fermat sont deux à deux premiers entre eux : pour tous $m,n\in \mathbb{N}$ tels que $m\mathrm{\ne }n$, on a $F_m\wedge F_n=1$.

5. Une nouvelle démonstration de l'infinité des nombres premiers. Pour chaque $n\in \mathbb{N}$, on note $q_n$ le plus petit diviseur premier de $F_n$. Montrer que l'application $n\mapsto q_n$ est injective de $\mathbb{N}$ dans $\mathcal{P}$, puis conclure que $\mathcal{P}$ est infini.

6. Fermat avait conjecturé que tous les $F_n$ sont premiers. Montrer que $641=5\times 2^7+1$ et que $641=2^4+5^4$, puis en déduire que $641\mid F_5$. Que peut-on conclure ?

On sait que l'ensemble $\mathcal{P}$ des nombres premiers est infini. On se propose de montrer qu'il en reste une infinité même si l'on impose en plus une condition de congruence. On note

$$A=\{p\in \mathcal{P}\mid p\equiv 3[4]\}\mathrm{.}$$

1. Montrer que tout entier impair est congru à $1$ ou à $3$ modulo $4$, et que ces deux cas s'excluent.

2. Soient $s\in {\mathbb{N}}^{\ast }$ et $a_1,\dots ,a_s$ des entiers tous congrus à $1$ modulo $4$. Montrer par récurrence sur $s$ que ${\displaystyle \prod _{i=1}^s{a}_i\equiv 1[4]}$.

3. Soit $N$ un entier tel que $N⩾3$ et $N\equiv 3[4]$. Montrer que $N$ admet au moins un diviseur premier congru à $3$ modulo $4$.

   Indication. Décomposer $N$ en produit de facteurs premiers et raisonner par l'absurde à l'aide des questions 1 et 2.

4. Démontrer que $A$ est infini. On raisonnera par l'absurde en supposant $A=\{p_1,\dots ,p_r\}$ et en considérant l'entier

   $$N=4p_1{p}_2\cdots p_r-1.$$

5. Adapter la méthode pour démontrer qu'il existe une infinité de nombres premiers congrus à $5$ modulo $6$.

Soient $p$ un nombre premier et $n\in {\mathbb{N}}^{\ast }$. Pour un entier $m⩾1$, on note $v_p(m)$ la valuation $p$-adique de $m$, c'est-à-dire l'exposant de $p$ dans la décomposition de $m$ en facteurs premiers. On rappelle que $v_p(m)$ est caractérisée par

$$\mathrm{\forall }k\in \mathbb{N},p^k\mid m⟺k⩽v_p(m),$$

et que $v_p(ab)=v_p(a)+v_p(b)$ pour tous $a,b\in {\mathbb{N}}^{\ast }$.

1. Soit $k\in {\mathbb{N}}^{\ast }$. Montrer que le nombre d'entiers $j$ vérifiant $1⩽j⩽n$ et $p^k\mid j$ est exactement $\lfloor {\displaystyle \frac{n}{p^k}}\rfloor$.

2. Montrer que si $p^k>n$, alors $\lfloor {\displaystyle \frac{n}{p^k}}\rfloor =0$, et qu'il existe un entier $K$ tel que $p^K>n$. La somme ${\sum }_{k⩾1}\lfloor \frac{n}{p^k}\rfloor$ n'a donc qu'un nombre fini de termes non nuls : elle a bien un sens.

3. Formule de Legendre. Démontrer que

   $$v_p(n!)=\sum _{k⩾1}\lfloor \frac{n}{p^k}\rfloor \mathrm{.}$$

   Indication. Établir d'abord $v_p(n!)={\sum }_{j=1}^n{v}_p(j)$, puis dénombrer de deux façons l'ensemble des couples $(j,k)$ tels que $1⩽j⩽n$, $1⩽k⩽K$ et $p^k\mid j$.

4. Calculer $v_2(100!)$ et $v_5(100!)$. En déduire le nombre de zéros par lesquels se termine l'écriture décimale de $100!$.

5. Déterminer le nombre de zéros terminaux de $2026!$.

6. Montrer que $v_p(n!)⩽{\displaystyle \frac{n}{p-1}}$. Déterminer enfin le plus grand entier $k$ tel que $3^k\mid 100!$, et vérifier la majoration sur cet exemple.

Soient $p$ un nombre premier et $a\in \mathbb{Z}$ un entier tel que $p\nmid a$. On considère l'ensemble

$$\mathrm{\Omega }=\{k\in {\mathbb{N}}^{\ast }\mid a^k\equiv 1[p]\}\mathrm{.}$$

1. Montrer que $\mathrm{\Omega }\mathrm{\ne }\mathrm{\varnothing }$, puis justifier que $\mathrm{\Omega }$ admet un plus petit élément. On le note $\omega$ et on l'appelle période de $a$ modulo $p$.

2. Soit $m\in \mathbb{N}$. Démontrer l'équivalence

   $$a^m\equiv 1[p]⟺\omega \mid m\mathrm{.}$$

   Indication. Pour le sens direct, effectuer la division euclidienne de $m$ par $\omega$ et utiliser la minimalité de $\omega$.

3. En déduire que $\omega \mid p-1$.

4. Déterminer la période de $2$ modulo $7$, celle de $3$ modulo $11$, puis celle de $10$ modulo $7$. On utilisera la question 3 pour limiter les valeurs à tester.

5. Question culturelle. Sachant que ${\displaystyle \frac{1}{7}}=\mathrm{0,142857}142857\dots$, relier la longueur de la période du développement décimal de ${\displaystyle \frac{1}{7}}$ au résultat obtenu pour $10$ modulo $7$.

6. Soit $n$ un nombre premier et soit $q$ un diviseur premier de $2^n-1$. Montrer que $q\equiv 1[n]$.

7. En déduire la liste des diviseurs premiers possibles de $2^{11}-1=2047$, et retrouver ainsi la factorisation $2047=23\times 89$.

Le petit théorème de Fermat est admis dans le cours ; l'objet de cet exercice est d'en donner une démonstration complète, entièrement fondée sur la formule du binôme. Dans tout l'exercice, $p$ désigne un nombre premier.

1. Établir, pour tout $k$ tel que $1⩽k⩽p$, l'identité dite « du pion »

   $$k\left(\genfrac{}{}{0px}{}{p}{k}\right)=p\left(\genfrac{}{}{0px}{}{p-1}{k-1}\right)\mathrm{.}$$

   En déduire que $p\mid {\displaystyle \left(\genfrac{}{}{0px}{}{p}{k}\right)}$ pour tout $k$ tel que $1⩽k⩽p-1$.

2. Montrer sur l'exemple de ${\displaystyle \left(\genfrac{}{}{0px}{}{4}{2}\right)}$ que l'hypothèse « $p$ premier » ne peut pas être supprimée.

3. En déduire que, pour tous $a,b\in \mathbb{Z}$,

   $$(a+b{)}^p\equiv a^p+b^p[p]\mathrm{.}$$

4. Démontrer par récurrence sur $a\in \mathbb{N}$ que $a^p\equiv a[p]$.

5. Étendre le résultat à tout $a\in \mathbb{Z}$. On distinguera les cas $p=2$ et $p$ impair.

6. En déduire la seconde forme du petit théorème de Fermat : si $p\nmid a$, alors $a^{p-1}\equiv 1[p]$.

7. Démontrer enfin que ${\displaystyle \left(\genfrac{}{}{0px}{}{2p}{p}\right)}\equiv 2[p]$.

Toutes les équations de cet exercice se traitent selon le même principe : se ramener à une égalité de la forme « produit de deux entiers $=$ constante », puis énumérer les diviseurs de cette constante. On prendra soin, à chaque fois, de préciser l'ensemble dans lequel on résout et de ne perdre aucune solution.

1. L'équation $x^2-y^2=105$. a. Soit $(x,y)\in {\mathbb{Z}}^2$ une solution. Montrer que $x-y$ et $x+y$ ont la même parité, puis qu'ils sont tous les deux impairs. b. Résoudre l'équation dans $({\mathbb{N}}^{\ast }{)}^2$ et présenter les solutions dans un tableau. c. En déduire toutes les solutions dans ${\mathbb{Z}}^2$, et vérifier qu'il y en a exactement $16$.

2. L'équation $x^2-y^2=2026$. Dresser la table des restes de $k^2$ modulo $4$, puis celle des valeurs possibles de $x^2-y^2$ modulo $4$. En déduire que cette équation n'a aucune solution dans ${\mathbb{Z}}^2$, et plus généralement qu'un entier congru à $2$ modulo $4$ n'est jamais différence de deux carrés d'entiers.

3. L'équation $xy=2(x+y)$. Montrer qu'elle équivaut à $(x-2)(y-2)=4$, puis la résoudre dans ${\mathbb{Z}}^2$.

4. L'équation ${\displaystyle \frac{1}{x}}+{\displaystyle \frac{1}{y}}={\displaystyle \frac{1}{6}}$. On cherche les couples $(x,y)\in ({\mathbb{N}}^{\ast }{)}^2$. Montrer d'abord que $x⩾7$ et $y⩾7$, puis que l'équation équivaut à $(x-6)(y-6)=36$. Conclure par un tableau.

5. Une famille d'équations. Soit $n\in \mathbb{N}$. Résoudre dans ${\mathbb{N}}^2$ l'équation $x^2=y^2+3^n$, et donner le nombre de solutions en fonction de $n$.

Pour tout $n\in \mathbb{N}$, on pose $u_n=2^n+3^n$. Les premières valeurs sont

$$u_0=2,u_1=5,u_2=13,u_3=35,u_4=97,u_5=275.$$

1. Compléter le tableau des restes de $u_n$ modulo $5$ pour $0⩽n⩽7$, et conjecturer une caractérisation des entiers $n$ tels que $5\mid u_n$.

2. Démontrer cette conjecture. On pourra remarquer que $3\equiv -2[5]$ et distinguer selon la parité de $n$. Pour le cas $n$ pair, on justifiera soigneusement que $5\nmid 2^{n+1}$.

3. Soit $n\in \mathbb{N}$. Calculer $3u_n-u_{n+1}$ et $u_{n+1}-2u_n$, puis en déduire la valeur de $u_n\wedge u_{n+1}$.

4. Divisibilité par $7$. a. Justifier que $2^3\equiv 1[7]$, puis que $3^6\equiv 1[7]$ en invoquant le petit théorème de Fermat. b. En déduire que la suite des restes de $u_n$ modulo $7$ est périodique de période $6$, dresser le tableau de ces restes pour $0⩽n⩽5$, et déterminer tous les $n$ tels que $7\mid u_n$.

5. Divisibilité par $13$. En utilisant le petit théorème de Fermat, déterminer le reste de la division euclidienne de $u_{2026}$ par $13$. On commencera par écrire la division euclidienne de $2026$ par $12$.

6. Dresser le tableau des restes de $u_n$ modulo $13$ pour $0⩽n⩽11$, en déduire tous les entiers $n$ tels que $13\mid u_n$, et vérifier la cohérence avec la question 5.

On appelle triplet pythagoricien tout triplet $(x,y,z)\in ({\mathbb{N}}^{\ast }{)}^3$ tel que $x^2+y^2=z^2$, et l'on dit qu'un tel triplet est primitif lorsque $x\wedge y\wedge z=1$. L'objet de l'exercice est de les décrire tous.

1. Soit $(x,y,z)$ un triplet pythagoricien primitif. Montrer que $x$, $y$ et $z$ sont deux à deux premiers entre eux.

2. Montrer qu'un carré d'entier est congru à $0$ ou à $1$ modulo $4$. En déduire que, dans un triplet primitif, $x$ et $y$ ne sont pas de même parité, puis que $z$ est impair.

3. Un lemme. Soient $a$ et $b$ deux entiers de ${\mathbb{N}}^{\ast }$ tels que $a\wedge b=1$ et tels que $ab$ soit le carré d'un entier. Montrer, en raisonnant sur les valuations $v_p(a)$ et $v_p(b)$, que $a$ et $b$ sont tous les deux des carrés d'entiers.

Dans les questions 4 et 5, $(x,y,z)$ désigne un triplet pythagoricien primitif dans lequel $x$ est impair et $y$ est pair, ce qui ne coûte rien d'après la question 2 quitte à échanger $x$ et $y$. On écrit $y=2w$ avec $w\in {\mathbb{N}}^{\ast }$.

4. Montrer que $z>x$, que $z-x$ et $z+x$ sont pairs, puis, en posant $s={\displaystyle \frac{z-x}{2}}$ et $t={\displaystyle \frac{z+x}{2}}$, que $s$ et $t$ sont des entiers de ${\mathbb{N}}^{\ast }$ vérifiant $st=w^2$ et $s\wedge t=1$.

5. En déduire qu'il existe des entiers $m>n⩾1$, premiers entre eux et de parités différentes, tels que

$$x=m^2-n^2,y=2mn,z=m^2+n^2\mathrm{.}$$

6. Réciproque. Soient $m>n⩾1$ deux entiers premiers entre eux et de parités différentes. Montrer que le triplet $(m^2-n^2,2mn,m^2+n^2)$ est un triplet pythagoricien primitif.

7. Dresser le tableau des triplets obtenus pour $(m,n)\in \{(2,1),(3,2),(4,1),(4,3),(5,2),(5,4)\}$. Que donne le couple $(m,n)=(3,1)$, et pourquoi ne contredit-il pas la question 6 ?

Soit $p$ un nombre premier. On dit qu'un entier $u$ est un inverse de $a$ modulo $p$ lorsque $au\equiv 1[p]$. L'objectif est de démontrer le théorème de Wilson :

$$(p-1)!\equiv -1[p],$$

puis sa réciproque.

1. Vérifier le théorème à la main pour $p=5$, $p=7$ et $p=11$, en donnant à chaque fois la division euclidienne de $(p-1)!$ par $p$.

2. Soit $a\in \mathbb{Z}$ tel que $p\nmid a$. Montrer que $a\wedge p=1$, puis, à l'aide du théorème de Bézout, que $a$ admet un inverse modulo $p$. Montrer enfin qu'il existe un unique entier $a^{\mathrm{\prime }}\in \{1,\dots ,p-1\}$ tel que $a{a}^{\mathrm{\prime }}\equiv 1[p]$.

3. Soit $a\in \{1,\dots ,p-1\}$. Montrer que

$$a^2\equiv 1[p]⟺a=1\text{ ou }a=p-1.$$

On factorisera $a^2-1$ et l'on utilisera le lemme d'Euclide. En déduire que $a^{\mathrm{\prime }}=a$ si et seulement si $a\in \{1,p-1\}$.

4. On suppose $p⩾3$ et l'on pose $A=\{2,3,\dots ,p-2\}$ (ensemble vide si $p=3$). Montrer que pour tout $a\in A$, on a $a^{\mathrm{\prime }}\in A$, $a^{\mathrm{\prime }}\mathrm{\ne }a$ et $(a^{\mathrm{\prime }}{)}^{\mathrm{\prime }}=a$. En déduire que $A$ se partitionne en paires $\{a,a^{\mathrm{\prime }}\}$, puis que

$$\prod _{a\in A}a\equiv 1[p]\mathrm{.}$$

5. Conclure : démontrer le théorème de Wilson pour tout nombre premier $p$ (on traitera à part le cas $p=2$). Détailler l'appariement obtenu pour $p=11$.

6. Réciproque. Soit $n⩾2$ un entier tel que $(n-1)!\equiv -1[n]$. Soit $d$ un diviseur positif de $n$ vérifiant $d⩽n-1$. Montrer que $d$ divise $(n-1)!$, puis que $d$ divise $(n-1)!+1$. En déduire que $n$ est premier.

7. Le théorème de Wilson et sa réciproque fournissent donc une caractérisation des nombres premiers. Expliquer en deux phrases pourquoi ce critère est inutilisable en pratique pour tester la primalité d'un grand entier.

Pour $n\in {\mathbb{N}}^{\ast }$, on note $\sigma (n)$ la somme de tous les diviseurs positifs de $n$ :

$$\sigma (n)=\sum _{d\mid n,d⩾1}d\mathrm{.}$$

On dit que $n$ est parfait lorsque $\sigma (n)=2n$, autrement dit lorsque $n$ est égal à la somme de ses diviseurs positifs stricts. L'exercice établit le théorème d'Euclide-Euler, qui décrit exactement tous les nombres parfaits pairs.

1. Calculer $\sigma (6)$, $\sigma (12)$ et $\sigma (28)$. Lesquels de ces trois entiers sont parfaits ?

2. Une formule de calcul. Soient $k⩾1$ un entier et $m\in {\mathbb{N}}^{\ast }$ un entier impair. Montrer que tout diviseur positif $D$ de $2^{k-1}m$ s'écrit de manière unique $D=2^{i}d$, où $0⩽i⩽k-1$ et où $d$ est un diviseur positif de $m$, et que réciproquement tout entier de cette forme divise $2^{k-1}m$. En déduire que

$$\sigma \text{\hspace{0.17em}⁣}\left(2^{k-1}m\right)=(2^k-1)\sigma (m)\mathrm{.}$$

3. Sens d'Euclide. Soit $k⩾2$ tel que $2^k-1$ soit premier. Montrer que $n=2^{k-1}(2^k-1)$ est parfait.

4. Appliquer la question 3 à $k=2,3,5,7$ et vérifier le résultat sur chacun des quatre entiers obtenus. Que se passe-t-il pour $k=4$ ?

5. Sens d'Euler. Soit $n$ un nombre parfait pair. a. Justifier qu'il existe un entier $k⩾2$ et un entier impair $m\in {\mathbb{N}}^{\ast }$ tels que $n=2^{k-1}m$. b. Montrer que $(2^k-1)\sigma (m)=2^{k}m$, puis que $(2^k-1)\mid m$. On écrit alors $m=(2^k-1)M$ avec $M\in {\mathbb{N}}^{\ast }$. c. Montrer que $\sigma (m)=m+M$. d. En raisonnant sur le nombre de diviseurs de $m$, montrer que $M=1$, puis que $m$ est premier. Conclure.

6. Complément. Montrer que si $2^k-1$ est premier, alors $k$ est premier. La réciproque est-elle vraie ? On étudiera le cas $k=11$.

On étudie l'équation

$$(E):x^2+y^2=3z^2,(x,y,z)\in {\mathbb{Z}}^3\mathrm{.}$$

Le triplet $(0,0,0)$ en est visiblement solution ; on va démontrer que c'est la seule, par la méthode dite de descente infinie : on suppose qu'il existe une solution non nulle, on en fabrique une strictement plus petite, et l'on contredit ainsi la minimalité d'une solution bien choisie.

1. Dresser la table des restes de $k^2$ modulo $3$ selon le reste de $k$ modulo $3$. En déduire que, pour tout $k\in \mathbb{Z}$, $3\mid k^2$ si et seulement si $3\mid k$, puis que pour tous $a,b\in \mathbb{Z}$ :

$$3\mid a^2+b^2⟹3\mid a\text{ et }3\mid b\mathrm{.}$$

2. Soit $(x,y,z)$ une solution de $(E)$ telle que $z=0$. Montrer que $x=y=0$. En déduire que toute solution non nulle de $(E)$ vérifie $z\mathrm{\ne }0$.

3. L'étape de descente. Soit $(x,y,z)$ une solution de $(E)$. Montrer successivement que $3\mid x$, que $3\mid y$, puis que $3\mid z$. En déduire que $({\displaystyle \frac{x}{3}},{\displaystyle \frac{y}{3}},{\displaystyle \frac{z}{3}})$ est encore une solution de $(E)$, et qu'elle est non nulle dès que $(x,y,z)$ l'est.

4. Conclusion. On suppose par l'absurde que $(E)$ possède une solution non nulle. Considérer l'ensemble $E=\{\mathrm{\mid }z\mathrm{\mid }:(x,y,z)\text{ solution non nulle de }(E)\}$, justifier qu'il admet un plus petit élément, et conclure.

5. En appliquant le résultat précédent à un triplet bien choisi, démontrer que $\sqrt{3}$ est irrationnel.

6. Reprendre l'ensemble de la démarche pour l'équation $x^2+y^2=7z^2$ : dresser la table des restes de $k^2$ modulo $7$, vérifier l'implication analogue à celle de la question 1, et conclure.

7. La même méthode appliquée à $x^2+y^2=5z^2$ échoue. Où exactement ? Exhiber une solution non nulle de cette équation.