Arithmétique dans Z (Exercices) · Révisions prépa · Ridami

Algèbre · 1re année

Arithmétique dans Z

Application du cours5 points

1. Divisions euclidiennes et puissances modulo 13

Effectuer la division euclidienne de $- 250$ par $13$ , puis celle de $250$ par $- 13$ .
Pour chaque $n \in [⁣ [0, 4] ⁣]$ , donner le reste de $5^{n}$ modulo $13$ .
En déduire le reste de $5^{2026}$ modulo $13$ .
Montrer que pour tout $n \in ℕ$ , l'entier $5^{4 n + 2} + 1$ est divisible par $13$ .
Déterminer les entiers naturels $n$ tels que $13$ divise $5^{n} + 8^{n}$ .

Voir le corrigé

1. On cherche $q$ et $r$ avec $0 \leq r < 13$ . Comme $13 \times 19 = 247$ , on a $250 = 13 \times 19 + 3$ . Donc $- 250 = 13 \times (- 19) - 3 = 13 \times (- 20) + 10$ , et $0 \leq 10 < 13$ : $- 250 = 13 \times (- 20) + 10$ , quotient $- 20$ , reste $10$ . Pour le diviseur $- 13$ : $250 = (- 13) \times (- 19) + 3$ avec $0 \leq 3 < ∣ - 13 ∣$ : quotient $- 19$ , reste $3$ . On retient que le reste est toujours positif ou nul (fiche §2).

2. $5^{0} = 1$ ; $5^{1} = 5$ ; $5^{2} = 25 = 13 + 12$ , donc $5^{2} \equiv 12 \equiv - 1 [13]$ ; $5^{3} \equiv - 5 \equiv 8 [13]$ ; $5^{4} = (5^{2})^{2} \equiv (- 1)^{2} = 1 [13]$ . Les restes sont $1, 5, 12, 8, 1$ .

3. $5^{4} \equiv 1 [13]$ et $2026 = 4 \times 506 + 2$ , donc $5^{2026} = (5^{4})^{506} \times 5^{2} \equiv 1 \times 12 [13]$ . Le reste vaut $12$ .

4. $5^{4 n + 2} = (5^{4})^{n} \times 5^{2} \equiv 1 \times (- 1) = - 1 [13]$ , donc $5^{4 n + 2} + 1 \equiv 0 [13]$ : $13$ divise $5^{4 n + 2} + 1$ .

5. $8 \equiv - 5 [13]$ , donc $5^{n} + 8^{n} \equiv 5^{n} + (- 5)^{n} [13]$ .

Si $n$ est impair, $(- 5)^{n} = - 5^{n}$ et $5^{n} + 8^{n} \equiv 0 [13]$ .
Si $n$ est pair, $5^{n} + 8^{n} \equiv 2 \times 5^{n} [13]$ . Or $13$ est premier et ne divise ni $2$ ni $5$ , donc (lemme d'Euclide, appliqué à $2 \times 5 \times \dots \times 5$ ) il ne divise pas $2 \times 5^{n}$ .

Conclusion : $13 ∣ 5^{n} + 8^{n} ⟺ n est impair$ .

Après avoir comparé avec le corrigé :

Application du cours5 points

2. Algorithme d'Euclide, Bézout et PPCM

Soient $a = 1517$ et $b = 1073$ .

À l'aide de l'algorithme d'Euclide, calculer $d = a \land b$ .
En remontant l'algorithme, trouver deux entiers $u$ et $v$ vérifiant $a u + b v = d$ .
En déduire $a \lor b$ et la forme irréductible de la fraction $\frac{1073}{1517}$ .
L'équation $1517 x + 1073 y = 100$ a-t-elle des solutions dans $ℤ^{2}$ ?
Résoudre dans $ℤ^{2}$ l'équation $1517 x + 1073 y = 111$ .

Voir le corrigé

1. Divisions successives : $1517 = 1073 \times 1 + 444, 1073 = 444 \times 2 + 185, 444 = 185 \times 2 + 74, 185 = 74 \times 2 + 37, 74 = 37 \times 2 + 0.$ Le dernier reste non nul est $37$ : $d = 1517 \land 1073 = 37$ .

2. On part de l'avant-dernière ligne et on remplace chaque reste : $37 = 185 - 2 \times 74$ ; $74 = 444 - 2 \times 185$ , d'où $37 = 185 - 2 (444 - 2 \times 185) = 5 \times 185 - 2 \times 444$ ; $185 = 1073 - 2 \times 444$ , d'où $37 = 5 \times 1073 - 12 \times 444$ ; enfin $444 = 1517 - 1073$ , d'où $37 = 5 \times 1073 - 12 (1517 - 1073) = 1517 \times (- 12) + 1073 \times 17.$ Le couple $(u, v) = (- 12, 17)$ convient. Contrôle : $1073 \times 17 = 18241$ et $1517 \times 12 = 18204$ , différence $37$ .

3. $(a \land b) (a \lor b) = a b$ , donc $a \lor b = \frac{1517 \times 1073}{37} = 41 \times 1073 = 43 993$ , car $1517 = 37 \times 41$ (et $1073 = 37 \times 29$ ). La fraction se simplifie par $37$ : $\frac{1073}{1517} = \frac{29}{41}$ , irréductible car $\frac{a}{37} \land \frac{b}{37} = 41 \land 29 = 1$ (fiche §4, mise en facteur du PGCD).

4. Si $(x, y)$ était solution, $37$ , qui divise $1517$ et $1073$ , diviserait $100$ : c'est faux. Aucune solution.

5. $111 = 3 \times 37$ : on divise par $37$ , l'équation équivaut à $41 x + 29 y = 3$ , avec $41 \land 29 = 1$ . Solution particulière : la question 2 divisée par $37$ donne $41 \times (- 12) + 29 \times 17 = 1$ ; en multipliant par $3$ , $(- 36, 51)$ est solution, et $(- 36 + 29, 51 - 41) = (- 7, 10)$ aussi (contrôle : $- 287 + 290 = 3$ ). Solution générale : si $41 x + 29 y = 3$ , alors $41 (x + 7) = - 29 (y - 10)$ . Ainsi $29 ∣ 41 (x + 7)$ et $29 \land 41 = 1$ : d'après le lemme de Gauss, $29 ∣ x + 7$ . On écrit $x = - 7 + 29 k$ ( $k \in ℤ$ ) ; en reportant, $41 \times 29 k = - 29 (y - 10)$ , donc $y = 10 - 41 k$ . Réciproque : $41 (- 7 + 29 k) + 29 (10 - 41 k) = - 287 + 290 = 3$ . $𝒮 = {(- 7 + 29 k, 10 - 41 k), k \in ℤ}$

Après avoir comparé avec le corrigé :

Application du cours5 points

3. Deux équations diophantiennes

Un club d'étudiants achète des lots de matériel à $23$ dinars et à $17$ dinars et dépense exactement $400$ dinars. (a) Résoudre dans $ℤ^{2}$ l'équation $23 x + 17 y = 400$ . (b) En déduire combien de lots de chaque sorte le club a achetés.
(a) Montrer que l'équation $15 x - 21 y = 8$ n'a pas de solution dans $ℤ^{2}$ . (b) Résoudre dans $ℤ^{2}$ l'équation $15 x - 21 y = 9$ .

Voir le corrigé

1.(a) Algorithme d'Euclide : $23 = 17 \times 1 + 6$ , $17 = 6 \times 2 + 5$ , $6 = 5 \times 1 + 1$ . Donc $23 \land 17 = 1$ et, en remontant, $1 = 6 - 5 = 6 - (17 - 2 \times 6) = 3 \times 6 - 17 = 3 (23 - 17) - 17 = 23 \times 3 + 17 \times (- 4)$ . En multipliant par $400$ : $23 \times 1200 + 17 \times (- 1600) = 400$ . Pour obtenir une solution plus simple, on ajoute $17 k$ à $x$ et on retranche $23 k$ à $y$ avec $k = - 70$ : $(1200 - 1190, - 1600 + 1610) = (10, 10)$ , et effectivement $230 + 170 = 400$ . Si $23 x + 17 y = 400$ , alors $23 (x - 10) = - 17 (y - 10)$ ; $17 ∣ 23 (x - 10)$ et $17 \land 23 = 1$ , donc (Gauss) $x = 10 + 17 k$ , puis $y = 10 - 23 k$ . Réciproquement, ces couples sont solutions ( $23 \times 17 k - 17 \times 23 k = 0$ ). $𝒮 = {(10 + 17 k, 10 - 23 k), k \in ℤ} .$

1.(b) Les nombres de lots sont des entiers naturels : $10 + 17 k \geq 0$ impose $k \geq - \frac{10}{17}$ , soit $k \geq 0$ ; $10 - 23 k \geq 0$ impose $k \leq \frac{10}{23}$ , soit $k \leq 0$ . Donc $k = 0$ : le club a acheté $10 lots de chaque sorte$ .

2.(a) $3$ divise $15$ et $21$ , donc divise $15 x - 21 y$ ; or $3 ∤ 8$ . Pas de solution (fiche §5 : il faut $15 \land 21 = 3 ∣ c$ ).

2.(b) $3 ∣ 9$ : l'équation équivaut à $5 x - 7 y = 3$ , avec $5 \land 7 = 1$ . Solution évidente : $(2, 1)$ ( $10 - 7 = 3$ ). Si $5 x - 7 y = 3$ , alors $5 (x - 2) = 7 (y - 1)$ ; $7 ∣ 5 (x - 2)$ et $7 \land 5 = 1$ , donc $x = 2 + 7 k$ , puis $5 \times 7 k = 7 (y - 1)$ donne $y = 1 + 5 k$ . Réciproque immédiate. $𝒮 = {(2 + 7 k, 1 + 5 k), k \in ℤ}$ .

Après avoir comparé avec le corrigé :

Application du cours6 points

4. Décomposition en facteurs premiers

Soient $m = 3528$ et $n = 2100$ .

Décomposer $m$ et $n$ en produit de facteurs premiers.
En déduire $m \land n$ et $m \lor n$ , puis vérifier la relation $(m \land n) (m \lor n) = m n$ sur les valuations.
Combien $m$ a-t-il de diviseurs positifs ?
Déterminer le plus petit entier $k \geq 1$ tel que $k n$ soit un carré parfait, puis le plus petit entier $k^{'} \geq 1$ tel que $k^{'} m$ soit le cube d'un entier.
(a) Soit $p$ premier et $N \geq 1$ . Justifier que le nombre d'entiers de $[⁣ [1, N] ⁣]$ divisibles par $p^{j}$ vaut $E ⁣ (\frac{N}{p^{j}})$ , puis que $v_{p} (N!) = \sum_{j \geq 1} E ⁣ (\frac{N}{p^{j}})$ . (b) Par combien de zéros se termine l'écriture décimale de $100!$ ?

Voir le corrigé

1. $3528 = 2 \times 1764 = 2^{2} \times 882 = 2^{3} \times 441$ et $441 = 21^{2} = 3^{2} \times 7^{2}$ , donc $m = 2^{3} \times 3^{2} \times 7^{2}$ . $2100 = 21 \times 100 = 3 \times 7 \times 2^{2} \times 5^{2}$ , donc $n = 2^{2} \times 3 \times 5^{2} \times 7$ .

2. On prend les exposants minimaux, puis maximaux (fiche §9) : $m \land n = 2^{2} \times 3 \times 7 = 84, m \lor n = 2^{3} \times 3^{2} \times 5^{2} \times 7^{2} = 88 200.$ Pour chaque premier, $\min (v_{p} (m), v_{p} (n)) + \max (v_{p} (m), v_{p} (n)) = v_{p} (m) + v_{p} (n)$ : $2$ : $2 + 3 = 3 + 2$ ; $3$ : $1 + 2 = 2 + 1$ ; $5$ : $0 + 2 = 0 + 2$ ; $7$ : $1 + 2 = 2 + 1$ . D'où $(m \land n) (m \lor n) = m n$ .

3. Un diviseur positif de $m$ s'écrit $2^{α} 3^{β} 7^{γ}$ avec $α \in [⁣ [0, 3] ⁣]$ , $β, γ \in [⁣ [0, 2] ⁣]$ , et ces écritures sont distinctes par unicité de la décomposition : $4 \times 3 \times 3 = 36$ diviseurs.

4. $k n$ est un carré si et seulement si toutes ses valuations sont paires. Les valuations impaires de $n$ sont celles de $3$ et de $7$ (égales à $1$ ) : il faut $v_{3} (k)$ et $v_{7} (k)$ impairs, et $k = 3 \times 7 = 21$ est le plus petit choix. $21 \times 2100 = 44 100 = 210^{2}$ . Donc $k = 21$ . $k^{'} m$ est un cube si et seulement si toutes ses valuations sont multiples de $3$ : il faut $v_{2} (k^{'}) \equiv 0$ , $v_{3} (k^{'}) \equiv 1$ et $v_{7} (k^{'}) \equiv 1 [3]$ , d'où le minimum $k^{'} = 3 \times 7 = 21$ ; en effet $21 \times 3528 = 2^{3} \times 3^{3} \times 7^{3} = 42^{3}$ . Donc $k^{'} = 21$ aussi (coïncidence due à la forme de $m$ et $n$ ).

5.(a) Les multiples de $p^{j}$ dans $[⁣ [1, N] ⁣]$ sont $p^{j}, 2 p^{j}, \dots, q p^{j}$ avec $q$ le plus grand entier tel que $q p^{j} \leq N$ , c'est-à-dire $q = E ⁣ (\frac{N}{p^{j}})$ . Ensuite $v_{p} (N!) = \sum_{i = 1}^{N} v_{p} (i)$ , et $v_{p} (i)$ est le nombre d'entiers $j \geq 1$ tels que $p^{j} ∣ i$ . On compte donc les couples $(i, j)$ avec $1 \leq i \leq N$ , $j \geq 1$ et $p^{j} ∣ i$ , d'abord à $i$ fixé (on obtient $\sum_{i} v_{p} (i)$ ), puis à $j$ fixé (on obtient le nombre de multiples de $p^{j}$ dans $[⁣ [1, N] ⁣]$ ) ; il n'y a qu'un nombre fini de tels couples car $p^{j} > N$ pour $j$ grand. D'où $v_{p} (N!) = \sum_{j \geq 1} E ⁣ (\frac{N}{p^{j}})$ .

5.(b) Le nombre de zéros finaux est la plus grande puissance de $10 = 2 \times 5$ qui divise $100!$ , soit $\min (v_{2} (100!), v_{5} (100!))$ . $v_{5} (100!) = E (20) + E (4) + E (0,8) = 20 + 4 = 24$ et $v_{2} (100!) = 50 + 25 + 12 + 6 + 3 + 1 = 97$ . Donc $100!$ se termine par $24 z \overset{ˊ}{e} ros$ .

Après avoir comparé avec le corrigé :

Niveau devoir6 points

5. PGCD dépendant d'un paramètre

Dans tout l'exercice, $n$ est un entier naturel.

On pose $d_{n} = (n^{2} + 3 n + 5) \land (n + 2)$ . (a) Montrer que $d_{n} = (n + 2) \land 3$ . (b) En déduire la valeur de $d_{n}$ selon le reste de $n$ modulo $3$ .
On pose $e_{n} = (2 n + 3) \land (5 n + 1)$ . (a) Montrer que $e_{n}$ divise $13$ . (b) Déterminer les entiers $n$ pour lesquels $e_{n} = 13$ . (c) Pour quelles valeurs de $n$ la fraction $\frac{5 n + 1}{2 n + 3}$ est-elle irréductible ?
Montrer que pour tout $n \in ℕ^{*}$ , les entiers $n! + 1$ et $(n + 1)! + 1$ sont premiers entre eux. Que se passe-t-il pour $n = 0$ ?

Voir le corrigé

1.(a) $n^{2} + 3 n + 5 = (n + 2) (n + 1) + 3$ . Le lemme $a \land b = b \land (a - k b)$ (fiche §4), avec $k = n + 1$ , donne $d_{n} = (n + 2) \land 3$ .

1.(b) $(n + 2) \land 3$ vaut $3$ si $3 ∣ n + 2$ , et $1$ sinon ( $3$ est premier). Or $3 ∣ n + 2 ⟺ n \equiv 1 [3]$ . Donc $d_{n} = 3 si n \equiv 1 [3], d_{n} = 1 sinon.$ Exemple : $n = 1$ , $9 \land 3 = 3$ .

2.(a) $e_{n}$ divise $2 n + 3$ et $5 n + 1$ , donc la combinaison $5 (2 n + 3) - 2 (5 n + 1) = 13$ .

2.(b) Les diviseurs positifs de $13$ sont $1$ et $13$ . $e_{n} = 13$ si et seulement si $13 ∣ 2 n + 3$ et $13 ∣ 5 n + 1$ . $2 n + 3 \equiv 0 [13] ⟺ 2 n \equiv 10 [13] ⟺ n \equiv 5 [13]$ (on simplifie par $2$ , premier avec $13$ ). Réciproquement, si $n \equiv 5 [13]$ : $2 n + 3 \equiv 13 \equiv 0$ et $5 n + 1 \equiv 26 \equiv 0 [13]$ . Donc $e_{n} = 13 ⟺ n \equiv 5 [13]$ .

2.(c) La fraction est irréductible si et seulement si $e_{n} = 1$ , c'est-à-dire $n \equiv̸ 5 [13]$ . Pour $n = 5$ : $\frac{26}{13} = 2$ .

3. Soit $n \geq 1$ et $δ = (n! + 1) \land ((n + 1)! + 1)$ . Il divise la combinaison $(n + 1)! + 1 - (n + 1) (n! + 1) = - n$ , donc $δ ∣ n$ . Comme $n ∣ n!$ , on a $δ ∣ n!$ ; et $δ ∣ n! + 1$ . Donc $δ$ divise $(n! + 1) - n! = 1$ : $δ = 1$ . Pour $n = 0$ , les deux entiers valent $0! + 1 = 1! + 1 = 2$ : leur PGCD est $2$ , la propriété tombe. L'argument utilisait $n ∣ n!$ , qui est faux pour $n = 0$ ( $0 ∤ 1$ ).

Après avoir comparé avec le corrigé :

Niveau devoir7 points

6. Inverses modulo $n$ , équations et système de congruences

(a) Justifier que $17$ et $60$ sont premiers entre eux et trouver un inverse de $17$ modulo $60$ dans $[⁣ [0, 59] ⁣]$ . (b) Résoudre dans $ℤ$ l'équation $17 x \equiv 9 [60]$ .
(a) Résoudre dans $ℤ$ l'équation $12 x \equiv 18 [30]$ ; combien a-t-elle de solutions dans $[⁣ [0, 29] ⁣]$ ? (b) Montrer que l'équation $12 x \equiv 20 [30]$ n'a pas de solution.
On considère le système $(Σ) : x \equiv 2 [7], x \equiv 5 [9], x \equiv 1 [4] .$ (a) Montrer que $x$ vérifie les deux premières congruences si et seulement si $x \equiv 23 [63]$ . (b) Résoudre $(Σ)$ dans $ℤ$ . (c) Plus généralement, soient $m, n \geq 1$ premiers entre eux et $α, β \in ℤ$ . Montrer que les solutions du système $x \equiv α [m]$ , $x \equiv β [n]$ forment exactement une classe modulo $m n$ .

Voir le corrigé

1.(a) $60 = 17 \times 3 + 9$ , $17 = 9 \times 1 + 8$ , $9 = 8 \times 1 + 1$ : $17 \land 60 = 1$ . En remontant : $1 = 9 - 8 = 9 - (17 - 9) = 2 \times 9 - 17 = 2 (60 - 3 \times 17) - 17 = 2 \times 60 - 7 \times 17$ . Donc $17 \times (- 7) \equiv 1 [60]$ , et $- 7 \equiv 53 [60]$ : l'inverse cherché est $53$ (contrôle : $17 \times 53 = 901 = 15 \times 60 + 1$ ).

1.(b) Si $17 x \equiv 9 [60]$ , en multipliant par $53$ : $x \equiv 53 \times 17 x \equiv 53 \times 9 = 477 \equiv 57 [60]$ . Réciproquement, $17 \times 57 = 969 = 16 \times 60 + 9$ . Donc $x \equiv 57 [60]$ .

2.(a) $12 x \equiv 18 [30] ⟺ 30 ∣ 12 x - 18 ⟺ 5 ∣ 2 x - 3$ (on divise par $6$ : $30 k = 12 x - 18 ⟺ 5 k = 2 x - 3$ ) $⟺ 2 x \equiv 3 [5]$ . L'inverse de $2$ modulo $5$ est $3$ ( $6 \equiv 1$ ), donc $x \equiv 9 \equiv 4 [5]$ . Les solutions sont les $x \equiv 4 [5]$ ; dans $[⁣ [0, 29] ⁣]$ : $4, 9, 14, 19, 24, 29$ , soit $6 solutions$ ( $6 = 12 \land 30$ ).

2.(b) Si $12 x \equiv 20 [30]$ , alors $30 ∣ 12 x - 20$ , donc $6 ∣ 12 x - 20$ , donc $6 ∣ 20$ : faux. Pas de solution.

3.(a) $x \equiv 2 [7] ⟺ x = 2 + 7 k$ , $k \in ℤ$ . Alors $x \equiv 5 [9] ⟺ 7 k \equiv 3 [9]$ . Comme $7 \times 4 = 28 \equiv 1 [9]$ , cela équivaut à $k \equiv 12 \equiv 3 [9]$ , soit $k = 3 + 9 j$ et $x = 23 + 63 j$ . Ainsi les deux premières congruences équivalent à $x \equiv 23 [63]$ (contrôle : $23 = 3 \times 7 + 2 = 2 \times 9 + 5$ ).

3.(b) On écrit $x = 23 + 63 j$ . Alors $x \equiv 1 [4] ⟺ 3 + 3 j \equiv 1 [4] ⟺ 3 j \equiv 2 [4] ⟺ j \equiv 6 \equiv 2 [4]$ (on multiplie par $3$ , inverse de $3$ modulo $4$ ). Donc $j = 2 + 4 i$ et $x = 149 + 252 i$ . $x \equiv 149 [252]$ Contrôle : $149 = 21 \times 7 + 2 = 16 \times 9 + 5 = 37 \times 4 + 1$ .

3.(c) Existence : Bézout donne $m u + n v = 1$ . Posons $x_{0} = β m u + α n v$ . Alors $x_{0} \equiv α n v [m]$ et $n v = 1 - m u \equiv 1 [m]$ , donc $x_{0} \equiv α [m]$ ; de même $x_{0} \equiv β [n]$ . Unicité modulo $m n$ : si $x$ et $x_{0}$ sont solutions, $m ∣ x - x_{0}$ et $n ∣ x - x_{0}$ , avec $m \land n = 1$ , donc $m n ∣ x - x_{0}$ (corollaire de Gauss). Réciproquement, tout $x \equiv x_{0} [m n]$ est solution. Les solutions forment la classe de $x_{0}$ modulo $m n$ . (C'est le lemme chinois ; la question 3.(b) l'applique deux fois, avec $7 \land 9 = 1$ puis $63 \land 4 = 1$ .)

Après avoir comparé avec le corrigé :

Niveau devoir7 points

7. Petit théorème de Fermat

Soit $p$ un nombre premier.

Montrer que pour tout $k \in [⁣ [1, p - 1] ⁣]$ , $p$ divise $(\binom{p}{k})$ .
En déduire que pour tous $a, b \in ℤ$ , $(a + b)^{p} \equiv a^{p} + b^{p} [p]$ .
Montrer que pour tout $a \in ℕ$ , $a^{p} \equiv a [p]$ , puis étendre ce résultat à $a \in ℤ$ .
Montrer que si $p ∤ a$ , alors $a^{p - 1} \equiv 1 [p]$ .
Application : trouver le reste de $3^{2026}$ modulo $11$ .
Montrer que pour tout $n \in ℤ$ , $2730$ divise $n^{13} - n$ . (On remarquera que $2730 = 2 \times 3 \times 5 \times 7 \times 13$ .)
(a) Montrer que $2^{10} \equiv 1 [341]$ , puis que $2^{340} \equiv 1 [341]$ . (b) L'entier $341$ est-il premier ? Que peut-on dire de la réciproque de la question 4 ?

Voir le corrigé

1. Pour $1 \leq k \leq p - 1$ : $k (\binom{p}{k}) = k \frac{p!}{k! (p - k)!} = p \frac{(p - 1)!}{(k - 1)! (p - k)!} = p (\binom{p - 1}{k - 1})$ . Donc $p ∣ k (\binom{p}{k})$ . Comme $1 \leq k < p$ et $p$ est premier, $p \land k = 1$ ; d'après le lemme de Gauss, $p ∣ (\binom{p}{k})$ .

2. Binôme : $(a + b)^{p} = a^{p} + b^{p} + \sum_{k = 1}^{p - 1} (\binom{p}{k}) a^{k} b^{p - k}$ , et chaque terme de la somme est multiple de $p$ (question 1).

3. Récurrence sur $a \in ℕ$ . Pour $a = 0$ : $0^{p} = 0$ . Si $a^{p} \equiv a [p]$ , alors par la question 2 (avec $b = 1$ ) : $(a + 1)^{p} \equiv a^{p} + 1 \equiv a + 1 [p]$ . Pour $a \in ℤ$ quelconque, soit $r \in [⁣ [0, p - 1] ⁣]$ son reste : $a \equiv r [p]$ , donc $a^{p} \equiv r^{p} \equiv r \equiv a [p]$ .

4. $p ∣ a^{p} - a = a (a^{p - 1} - 1)$ . Si $p ∤ a$ , alors $p \land a = 1$ ( $p$ premier) et le lemme de Gauss donne $p ∣ a^{p - 1} - 1$ .

5. $11$ est premier et ne divise pas $3$ : $3^{10} \equiv 1 [11]$ . Comme $2026 = 10 \times 202 + 6$ , $3^{2026} \equiv 3^{6} [11]$ . Or $3^{5} = 243 = 22 \times 11 + 1 \equiv 1 [11]$ , donc $3^{6} \equiv 3$ . Le reste vaut $3$ .

6. Soit $q \in {2, 3, 5, 7, 13}$ . On remarque que $q - 1 \in {1, 2, 4, 6, 12}$ divise $12$ . Si $q ∣ n$ , alors $q ∣ n^{13} - n$ . Sinon, $n^{q - 1} \equiv 1 [q]$ (question 4), donc $n^{12} = {(n^{q - 1})}^{12 / (q - 1)} \equiv 1$ et $n^{13} \equiv n [q]$ . Ainsi les cinq premiers $2, 3, 5, 7, 13$ divisent $n^{13} - n$ ; ils sont deux à deux premiers entre eux, donc leur produit $2730$ divise $n^{13} - n$ (corollaire de Gauss, appliqué de proche en proche).

7.(a) $2^{10} = 1024 = 3 \times 341 + 1$ , donc $2^{10} \equiv 1 [341]$ , puis $2^{340} = (2^{10})^{34} \equiv 1 [341]$ .

7.(b) $341 = 11 \times 31$ n'est pas premier. Pourtant $2^{341 - 1} \equiv 1 [341]$ : la conclusion de la question 4 peut être vraie pour un entier non premier. La réciproque du petit théorème de Fermat est fausse ; un test « $2^{n - 1} \equiv 1 [n]$ » ne prouve pas que $n$ est premier.

Après avoir comparé avec le corrigé :

Niveau devoir7 points

8. Les nombres de Fermat

Pour $n \in ℕ$ , on pose $F_{n} = 2^{2^{n}} + 1$ .

Calculer $F_{0}, F_{1}, F_{2}, F_{3}$ .
Montrer que $F_{n + 1} - 2 = (F_{n} - 2) F_{n}$ , puis que pour tout $n \geq 1$ , $F_{0} F_{1} \dots F_{n - 1} = F_{n} - 2$ .
En déduire que pour $m \neq n$ , $F_{m} \land F_{n} = 1$ .
En déduire une nouvelle preuve de l'existence d'une infinité de nombres premiers.
(a) Vérifier que $641 = 5 \times 2^{7} + 1 = 5^{4} + 2^{4}$ . (b) En déduire, sans calculer $F_{5}$ , que $641$ divise $F_{5}$ . Les $F_{n}$ sont-ils tous premiers ?
Soit $m \geq 1$ tel que $2^{m} + 1$ est premier. Montrer que $m$ est une puissance de $2$ . (On pourra écrire $m = 2^{s} t$ avec $t$ impair.)

Voir le corrigé

1. $F_{0} = 3$ , $F_{1} = 5$ , $F_{2} = 17$ , $F_{3} = 257$ .

2. $F_{n + 1} - 2 = 2^{2^{n + 1}} - 1 = {(2^{2^{n}})}^{2} - 1 = (2^{2^{n}} - 1) (2^{2^{n}} + 1) = (F_{n} - 2) F_{n}$ . Récurrence : pour $n = 1$ , $F_{0} = 3 = F_{1} - 2$ . Si $F_{0} \dots F_{n - 1} = F_{n} - 2$ , alors $F_{0} \dots F_{n} = (F_{n} - 2) F_{n} = F_{n + 1} - 2$ .

3. Supposons $m < n$ et soit $d = F_{m} \land F_{n}$ . $F_{m}$ figure dans le produit $F_{0} \dots F_{n - 1} = F_{n} - 2$ , donc $d ∣ F_{n} - 2$ ; comme $d ∣ F_{n}$ , on obtient $d ∣ 2$ . Or $F_{n}$ est impair, donc $d = 1$ .

4. Chaque $F_{n} \geq 3$ admet un diviseur premier $p_{n}$ (fiche §8). Si $m \neq n$ , $p_{m} \neq p_{n}$ : sinon ce premier diviserait $F_{m} \land F_{n} = 1$ . L'application $n \mapsto p_{n}$ est donc injective de $ℕ$ dans $𝒫$ : $𝒫$ est infini.

5.(a) $5 \times 2^{7} + 1 = 640 + 1 = 641$ et $5^{4} + 2^{4} = 625 + 16 = 641$ .

5.(b) Posons $x = 5 \times 2^{7}$ , de sorte que $x \equiv - 1 [641]$ et donc $x^{4} \equiv 1 [641]$ , c'est-à-dire $5^{4} \times 2^{28} \equiv 1$ . Par ailleurs $2^{4} = 641 - 5^{4} \equiv - 5^{4} [641]$ , d'où $2^{32} = 2^{4} \times 2^{28} \equiv - 5^{4} \times 2^{28} \equiv - 1 [641]$ . Donc $641 ∣ 2^{32} + 1 = F_{5}$ . Comme $641 < F_{5}$ et $641 > 1$ , $F_{5}$ n'est pas premier : les nombres de Fermat ne sont pas tous premiers.

6. Écrivons $m = 2^{s} t$ avec $t$ impair et supposons $t \geq 3$ . Posons $a = 2^{2^{s}}$ ; alors $2^{m} + 1 = a^{t} + 1$ et, $t$ étant impair, $a + 1 ∣ a^{t} + 1$ (fiche §1). Or $1 < a + 1 < a^{t} + 1$ (car $a \geq 2$ et $t \geq 3$ ) : $2^{m} + 1$ aurait un diviseur strict autre que $1$ , contradiction. Donc $t = 1$ et $m = 2^{s}$ .

Après avoir comparé avec le corrigé :

Synthèse, niveau concours10 points

9. Problème : PGCD des nombres de Fibonacci

On définit la suite $(F_{n})_{n \in ℕ}$ par $F_{0} = 0$ , $F_{1} = 1$ et $F_{n + 2} = F_{n + 1} + F_{n}$ pour tout $n \in ℕ$ . Tous les $F_{n}$ sont des entiers naturels.

Partie A — Premières propriétés.

Calculer $F_{n}$ pour $n \in [⁣ [0, 12] ⁣]$ .
Montrer que pour tout $n \geq 1$ , $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ . En déduire que deux termes consécutifs de la suite sont toujours premiers entre eux.
Montrer que pour tous $m \geq 1$ et $n \geq 0$ : $F_{m + n} = F_{m} F_{n + 1} + F_{m - 1} F_{n}$ . (On pourra raisonner par récurrence double sur $n$ , $m$ étant fixé.)

Partie B — Le théorème du PGCD.

Montrer que pour tous $m, k \geq 1$ , $F_{m}$ divise $F_{k m}$ .
Soient $n \geq m \geq 1$ . Montrer que $F_{n} \land F_{m} = F_{n - m} \land F_{m}$ .
En déduire que pour tous $m, n \geq 1$ : $F_{m} \land F_{n} = F_{m \land n}$ . (On pourra raisonner par récurrence forte sur $m + n$ .)
Calculer $F_{84} \land F_{60}$ et $F_{100} \land F_{51}$ , sans calculer ces nombres.

Partie C — Applications.

Soit $m \geq 3$ . Montrer que $F_{m} ∣ F_{n} ⟺ m ∣ n$ .
Montrer que si $n \geq 5$ et $F_{n}$ est premier, alors $n$ est premier. L'implication inverse est-elle exacte ? (On pourra considérer $F_{19} = 4181 = 37 \times 113$ .)

Voir le corrigé

1. $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144$ .

2. Récurrence. Pour $n = 1$ : $F_{2} F_{0} - F_{1}^{2} = - 1$ . Supposons $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ . Alors $F_{n + 2} F_{n} - F_{n + 1}^{2} = (F_{n + 1} + F_{n}) F_{n} - F_{n + 1}^{2} = F_{n}^{2} - F_{n + 1} (F_{n + 1} - F_{n}) = F_{n}^{2} - F_{n + 1} F_{n - 1} = - (- 1)^{n} = (- 1)^{n + 1} .$ Ainsi $F_{n + 1} F_{n - 1} + F_{n} \times (- F_{n}) = (- 1)^{n} = \pm 1$ : c'est une relation de Bézout, donc $F_{n} \land F_{n + 1} = 1$ pour $n \geq 1$ ; pour $n = 0$ , $F_{0} \land F_{1} = 0 \land 1 = 1$ .

3. On fixe $m \geq 1$ et on note $P (n)$ l'égalité. $P (0)$ : $F_{m} = F_{m} F_{1} + F_{m - 1} F_{0}$ . $P (1)$ : $F_{m + 1} = F_{m} F_{2} + F_{m - 1} F_{1} = F_{m} + F_{m - 1}$ , vrai. Si $P (n)$ et $P (n + 1)$ sont vraies, en les additionnant : $F_{m + n} + F_{m + n + 1} = F_{m} (F_{n + 1} + F_{n + 2}) + F_{m - 1} (F_{n} + F_{n + 1})$ , soit $F_{m + n + 2} = F_{m} F_{n + 3} + F_{m - 1} F_{n + 2}$ : c'est $P (n + 2)$ .

4. Récurrence sur $k$ . Pour $k = 1$ , évident. Si $F_{m} ∣ F_{k m}$ , la question 3 avec $(m, n) \to (m, k m)$ donne $F_{(k + 1) m} = F_{m} F_{k m + 1} + F_{m - 1} F_{k m}$ : les deux termes sont multiples de $F_{m}$ .

5. Si $n = m$ : $F_{n} \land F_{m} = F_{m} = F_{0} \land F_{m}$ (car $F_{0} = 0$ ). Si $n > m$ , la question 3 appliquée à $(m, n - m)$ donne $F_{n} = F_{m} F_{n - m + 1} + F_{m - 1} F_{n - m}$ , donc $F_{n} \land F_{m} = (F_{m - 1} F_{n - m}) \land F_{m}$ (on retranche un multiple de $F_{m}$ , fiche §4). Soit $δ$ un diviseur commun de $F_{m}$ et de $F_{m - 1} F_{n - m}$ . Tout diviseur commun de $δ$ et $F_{m - 1}$ divise $F_{m} \land F_{m - 1} = 1$ (question 2), donc $δ \land F_{m - 1} = 1$ , et le lemme de Gauss donne $δ ∣ F_{n - m}$ . Inversement, un diviseur commun de $F_{m}$ et $F_{n - m}$ divise $F_{m - 1} F_{n - m}$ . Donc $𝒟 (F_{m}) \cap 𝒟 (F_{m - 1} F_{n - m}) = 𝒟 (F_{m}) \cap 𝒟 (F_{n - m})$ et $F_{n} \land F_{m} = F_{n - m} \land F_{m}$ .

6. Récurrence forte sur $s = m + n \geq 2$ . Pour $m = n$ : $F_{m} \land F_{m} = F_{m} = F_{m \land m}$ . Sinon, quitte à échanger, $n > m \geq 1$ ; par la question 5, $F_{n} \land F_{m} = F_{n - m} \land F_{m}$ avec $(n - m) + m < s$ et $n - m \geq 1$ , donc par hypothèse de récurrence $F_{n - m} \land F_{m} = F_{(n - m) \land m}$ . Enfin $(n - m) \land m = n \land m$ . On a ainsi suivi l'algorithme d'Euclide sur les indices.

7. $84 \land 60 = 12$ (fiche §4), donc $F_{84} \land F_{60} = F_{12} = 144$ . $100 = 51 + 49$ , $51 = 49 + 2$ , $49 = 2 \times 24 + 1$ : $100 \land 51 = 1$ , donc $F_{100} \land F_{51} = F_{1} = 1$ .

8. Si $m ∣ n$ , la question 4 donne $F_{m} ∣ F_{n}$ (pour $n = 0$ , $F_{0} = 0$ est multiple de tout entier). Réciproquement, si $F_{m} ∣ F_{n}$ avec $n \geq 1$ , alors $F_{m \land n} = F_{m} \land F_{n} = F_{m}$ . La suite $(F_{k})$ est strictement croissante à partir de $k = 2$ ( $F_{k + 1} = F_{k} + F_{k - 1} > F_{k}$ pour $k \geq 2$ ) et $F_{1} = F_{2} = 1 < F_{m}$ car $m \geq 3$ ; comme $m \land n \leq m$ , l'égalité $F_{m \land n} = F_{m}$ impose $m \land n = m$ , c'est-à-dire $m ∣ n$ . (Le cas $n = 0$ est trivial.)

9. Supposons $n \geq 5$ non premier : $n = a b$ avec $2 \leq a \leq b < n$ . Si l'on avait $b = 2$ , alors $a = 2$ et $n = 4$ , exclu ; donc $3 \leq b < n$ . Par la question 4, $F_{b} ∣ F_{n}$ , avec $F_{b} \geq F_{3} = 2$ et $F_{b} < F_{n}$ (stricte croissance à partir du rang $2$ ) : $F_{n}$ a un diviseur autre que $1$ et lui-même, il n'est pas premier. Par contraposée, $F_{n}$ premier et $n \geq 5$ entraînent $n$ premier. La réciproque est fausse : $19$ est premier, mais $F_{19} = 4181 = 37 \times 113$ . (Pour $n = 4$ , $F_{4} = 3$ est premier alors que $4$ ne l'est pas : d'où l'hypothèse $n \geq 5$ .)

Après avoir comparé avec le corrigé :

Synthèse, niveau concours10 points

10. Problème type concours : théorème de Wilson et carrés modulo $p$

Dans tout le problème, $p$ désigne un nombre premier impair. Les questions sont numérotées en continu.

Partie I — Le théorème de Wilson.

▶ Q.1 Montrer que pour tout $a \in [⁣ [1, p - 1] ⁣]$ , il existe un unique $a^{'} \in [⁣ [1, p - 1] ⁣]$ tel que $a a^{'} \equiv 1 [p]$ .

▶ Q.2 Montrer que $a^{'} = a$ si et seulement si $a \in {1, p - 1}$ .

▶ Q.3 En regroupant chaque facteur avec son inverse, montrer que $(p - 1)! \equiv - 1 [p]$ . Vérifier le résultat pour $p = 7$ .

▶ Q.4 Soit $n \geq 2$ un entier tel que $(n - 1)! \equiv - 1 [n]$ . Montrer que $n$ est premier.

Partie II — L'équation $x^{2} \equiv - 1 [p]$ .

▶ Q.5 On suppose $p \equiv 3 [4]$ . Montrer, à l'aide du petit théorème de Fermat, que l'équation $x^{2} \equiv - 1 [p]$ n'a pas de solution dans $ℤ$ .

▶ Q.6 On suppose $p \equiv 1 [4]$ et on pose $x_{0} = (\frac{p - 1}{2})!$ . Montrer que $x_{0}^{2} \equiv - 1 [p]$ . (On pourra associer $k$ et $p - k$ dans $(p - 1)!$ .)

▶ Q.7 Pour $p = 13$ , déterminer le reste de $x_{0}$ modulo $13$ et vérifier le résultat de Q.6.

Partie III — Infinité de nombres premiers dans deux familles.

▶ Q.8 Soit $n \in ℤ$ . Montrer que tout diviseur premier impair de $n^{2} + 1$ est congru à $1$ modulo $4$ .

▶ Q.9 En déduire qu'il existe une infinité de nombres premiers congrus à $1$ modulo $4$ . (On pourra considérer $N = (2 p_{1} \dots p_{k})^{2} + 1$ .)

▶ Q.10 Montrer qu'il existe une infinité de nombres premiers congrus à $3$ modulo $4$ . (On pourra considérer $4 p_{1} \dots p_{k} - 1$ .)

Voir le corrigé

Q.1 $p$ est premier et $1 \leq a \leq p - 1$ , donc $a \land p = 1$ : Bézout donne $a u + p v = 1$ , donc $a u \equiv 1 [p]$ ; le reste $a^{'}$ de $u$ modulo $p$ convient, et $a^{'} \neq 0$ (sinon $0 \equiv 1$ ). Unicité : si $a a^{'} \equiv a a^{''} \equiv 1$ , on simplifie par $a$ , premier avec $p$ : $a^{'} \equiv a^{''} [p]$ , et deux éléments de $[⁣ [1, p - 1] ⁣]$ congrus modulo $p$ sont égaux.

Q.2 $a^{'} = a ⟺ a^{2} \equiv 1 [p] ⟺ p ∣ (a - 1) (a + 1) ⟺ p ∣ a - 1$ ou $p ∣ a + 1$ (lemme d'Euclide). Pour $a \in [⁣ [1, p - 1] ⁣]$ , $a - 1 \in [⁣ [0, p - 2] ⁣]$ et $a + 1 \in [⁣ [2, p] ⁣]$ : cela donne $a = 1$ ou $a = p - 1$ .

Q.3 Pour $p = 3$ : $2! = 2 \equiv - 1 [3]$ . Pour $p \geq 5$ , les éléments de $[⁣ [2, p - 2] ⁣]$ se répartissent en paires ${a, a^{'}}$ avec $a \neq a^{'}$ (Q.1, Q.2 ; la relation « être inverse l'un de l'autre » est symétrique), et chaque paire a un produit $\equiv 1$ . Donc $(p - 1)! \equiv 1 \times 1 \times (p - 1) \equiv - 1 [p]$ . Pour $p = 7$ : $6! = 720 = 7 \times 103 - 1$ , soit $6! \equiv - 1 [7]$ ; les paires sont ${2, 4}$ et ${3, 5}$ .

Q.4 Supposons $n$ composé : $n = a b$ avec $1 < a < n$ . Alors $a \leq n - 1$ , donc $a ∣ (n - 1)!$ . De plus $a ∣ n ∣ (n - 1)! + 1$ . Donc $a ∣ 1$ , contradiction avec $a > 1$ . Ainsi $n$ est premier. (Avec Q.3 : pour $n \geq 2$ , $n$ premier $⟺ (n - 1)! \equiv - 1 [n]$ .)

Q.5 Écrivons $p = 4 k + 3$ . Si $x^{2} \equiv - 1 [p]$ , alors $p ∤ x$ (sinon $0 \equiv - 1$ ), et le petit théorème de Fermat donne $x^{p - 1} \equiv 1$ . Or $x^{p - 1} = (x^{2})^{2 k + 1} \equiv (- 1)^{2 k + 1} = - 1 [p]$ . Donc $1 \equiv - 1$ , soit $p ∣ 2$ : impossible pour $p$ impair.

Q.6 Pour $1 \leq k \leq \frac{p - 1}{2}$ , $p - k \equiv - k [p]$ , donc $(p - 1)! = \prod_{k = 1}^{(p - 1) / 2} k (p - k) \equiv \prod_{k = 1}^{(p - 1) / 2} (- k^{2}) = (- 1)^{\frac{p - 1}{2}} x_{0}^{2} [p] .$ Si $p = 4 k + 1$ , $\frac{p - 1}{2} = 2 k$ est pair. Avec Q.3 : $x_{0}^{2} \equiv (p - 1)! \equiv - 1 [p]$ .

Q.7 $x_{0} = 6! = 720 = 13 \times 55 + 5$ , donc $x_{0} \equiv 5 [13]$ , et $5^{2} = 25 = 2 \times 13 - 1 \equiv - 1 [13]$ .

Q.8 Soit $q$ premier impair avec $q ∣ n^{2} + 1$ : $n^{2} \equiv - 1 [q]$ . D'après Q.5 (appliquée à $q$ ), $q \equiv̸ 3 [4]$ ; $q$ étant impair, $q \equiv 1 [4]$ .

Q.9 Par l'absurde, si les premiers $\equiv 1 [4]$ formaient un ensemble fini ${p_{1}, \dots, p_{k}}$ , on poserait $N = (2 p_{1} \dots p_{k})^{2} + 1$ . $N$ est impair et $N \geq 5$ , donc admet un diviseur premier $q$ , impair. Par Q.8, $q \equiv 1 [4]$ , donc $q = p_{i}$ pour un $i$ . Mais alors $q ∣ (2 p_{1} \dots p_{k})^{2}$ et $q ∣ N$ , donc $q ∣ 1$ : contradiction.

Q.10 Supposons les premiers $\equiv 3 [4]$ en nombre fini : $p_{1} = 3, \dots, p_{k}$ ; soit $M = 4 p_{1} \dots p_{k} - 1 \equiv 3 [4]$ . $M$ est impair ; si tous ses facteurs premiers étaient $\equiv 1 [4]$ , leur produit $M$ serait $\equiv 1 [4]$ (produit de nombres $\equiv 1$ ). Donc $M$ a un diviseur premier $q \equiv 3 [4]$ , c'est-à-dire $q = p_{i}$ . Alors $q ∣ 4 p_{1} \dots p_{k} - M = 1$ : contradiction.

Après avoir comparé avec le corrigé :

Niveau devoir10 points

11. L'indicatrice d'Euler

Classique du programme : indicatrice d'Euler.

Pour $n \in ℕ^{*}$ , on note $E_{n} = {k \in [⁣ [1, n] ⁣] : k \land n = 1}$ et $φ (n) = Card E_{n}$ (nombre d'entiers de $1$ à $n$ premiers avec $n$ ). Cette fonction $φ$ est l'indicatrice d'Euler. Le chapitre ne la suppose pas connue : tout se démontre avec le lemme de Gauss et ses corollaires.

(1,5 point) Déterminer $φ (1)$ , $φ (12)$ en listant $E_{12}$ , puis montrer que $φ (p^{k}) = p^{k} - p^{k - 1}$ pour $p$ premier et $k \geq 1$ . Calculer $φ (81)$ .
(2,5 points) Soient $m, n \in ℕ^{*}$ premiers entre eux. À $x \in [⁣ [1, m n] ⁣]$ on associe le couple $ψ (x) = (r, s)$ , où $r$ est l'unique élément de $[⁣ [1, m] ⁣]$ congru à $x$ modulo $m$ et $s$ l'unique élément de $[⁣ [1, n] ⁣]$ congru à $x$ modulo $n$ . a) Montrer que $ψ$ est injective, puis bijective de $[⁣ [1, m n] ⁣]$ sur $[⁣ [1, m] ⁣] \times [⁣ [1, n] ⁣]$ . b) Montrer que $x \land m n = 1$ si et seulement si $r \land m = 1$ et $s \land n = 1$ . En déduire que $φ (m n) = φ (m) φ (n)$ .
(1,5 point) Déduire que si $n = p_{1}^{α_{1}} \dots p_{r}^{α_{r}}$ (facteurs premiers distincts), alors $φ (n) = n \prod_{i = 1}^{r} (1 - \frac{1}{p_{i}})$ . Calculer $φ (360)$ et $φ (100)$ . Montrer que $φ (n)$ est pair dès que $n \geq 3$ .
(2 points) Montrer que $\sum_{d ∣ n} φ (d) = n$ , la somme portant sur les diviseurs positifs de $n$ . On pourra classer les éléments de $[⁣ [1, n] ⁣]$ selon la valeur de $k \land n$ . Vérifier pour $n = 12$ .
(2 points) Théorème d'Euler. Soit $n \geq 2$ et $a \in ℤ$ avec $a \land n = 1$ . Montrer que $a^{φ (n)} \equiv 1 [n]$ . Quel résultat du §10 se trouve ainsi généralisé lorsque $n$ est premier ?
(0,5 point) Déterminer les deux derniers chiffres de l'écriture décimale de $3^{2026}$ .

Voir le corrigé

1. $φ (1) = 1$ ( $1 \in E_{1}$ ). Les entiers de $[⁣ [1, 12] ⁣]$ premiers avec $12 = 2^{2} \cdot 3$ sont ceux qui ne sont divisibles ni par $2$ ni par $3$ : $E_{12} = {1, 5, 7, 11}$ , donc $φ (12) = 4$ . Pour $p$ premier et $j \in [⁣ [1, p^{k}] ⁣]$ , les entiers $j$ et $p^{k}$ ne sont pas premiers entre eux exactement quand $p$ divise $j$ (tout diviseur commun supérieur à $1$ admet un facteur premier, nécessairement égal à $p$ ). Les multiples de $p$ dans $[⁣ [1, p^{k}] ⁣]$ sont $p, 2 p, \dots, p^{k - 1} \cdot p$ : il y en a $p^{k - 1}$ . Donc $φ (p^{k}) = p^{k} - p^{k - 1}$ et $φ (81) = φ (3^{4}) = 81 - 27 = 54$ .

2.a) Soient $x, y \in [⁣ [1, m n] ⁣]$ avec $ψ (x) = ψ (y)$ . Alors $x \equiv y [m]$ et $x \equiv y [n]$ , donc $m ∣ x - y$ et $n ∣ x - y$ . Comme $m \land n = 1$ , le corollaire 1 du lemme de Gauss donne $m n ∣ x - y$ . Or $∣ x - y ∣ < m n$ , donc $x = y$ : $ψ$ est injective. Les ensembles de départ et d'arrivée ont le même cardinal $m n$ : $ψ$ est bijective.

2.b) Comme $x \equiv r [m]$ , on a $x = r + q m$ et, par le lemme clé de l'algorithme d'Euclide, $x \land m = r \land m$ ; de même $x \land n = s \land n$ .

Si $x \land m n = 1$ , tout diviseur commun de $x$ et $m$ divise $x$ et $m n$ : $x \land m = 1$ , donc $r \land m = 1$ ; de même $s \land n = 1$ .
Réciproquement, si $r \land m = 1$ et $s \land n = 1$ , alors $x \land m = 1$ et $x \land n = 1$ , d'où $x \land m n = 1$ (corollaire 2 du lemme de Gauss).

Par la bijection $ψ$ , les éléments de $E_{m n}$ correspondent exactement aux couples de $E_{m} \times E_{n}$ : $φ (m n) = Card (E_{m} \times E_{n}) = φ (m) φ (n) .$

3. Les puissances $p_{i}^{α_{i}}$ sont premières entre elles deux à deux. Par récurrence sur $r$ à l'aide de la question 2 (le produit $p_{1}^{α_{1}} \dots p_{r - 1}^{α_{r - 1}}$ est premier avec $p_{r}^{α_{r}}$ ), $φ (n) = \prod_{i = 1}^{r} (p_{i}^{α_{i}} - p_{i}^{α_{i} - 1}) = \prod_{i = 1}^{r} p_{i}^{α_{i}} (1 - \frac{1}{p_{i}}) = n \prod_{i = 1}^{r} (1 - \frac{1}{p_{i}}) .$ Ainsi $360 = 2^{3} \cdot 3^{2} \cdot 5$ donne $φ (360) = 4 \cdot 6 \cdot 4 = 96$ , et $100 = 2^{2} \cdot 5^{2}$ donne $φ (100) = 2 \cdot 20 = 40$ . Parité. Soit $n \geq 3$ . L'application $k \mapsto n - k$ envoie $E_{n}$ dans $E_{n}$ (car $(n - k) \land n = k \land n$ ) et c'est une involution. Elle n'a pas de point fixe : $k = n - k$ imposerait $n = 2 k$ , donc $k ∣ n$ et $k \land n = k = 1$ , d'où $n = 2$ , exclu. Les éléments de $E_{n}$ se regroupent donc en paires ${k, n - k}$ : $φ (n)$ est pair.

4. Tout $k \in [⁣ [1, n] ⁣]$ a $k \land n$ diviseur de $n$ , égal à $\frac{n}{d}$ pour un unique diviseur $d$ de $n$ . Notons $A_{d} = {k \in [⁣ [1, n] ⁣] : k \land n = \frac{n}{d}}$ : les $A_{d}$ ( $d ∣ n$ ) forment une partition de $[⁣ [1, n] ⁣]$ . Fixons $d$ et posons $e = \frac{n}{d}$ . Si $k \in A_{d}$ , alors $e ∣ k$ , donc $k = e j$ avec $j \in [⁣ [1, d] ⁣]$ , et $k \land n = e j \land e d = e (j \land d)$ ; la condition $k \land n = e$ équivaut à $j \land d = 1$ . L'application $j \mapsto e j$ est donc une bijection de $E_{d}$ sur $A_{d}$ : $Card A_{d} = φ (d)$ . En sommant, $n = \sum_{d ∣ n} Card A_{d} = \sum_{d ∣ n} φ (d) .$ Pour $n = 12$ : $φ (1) + φ (2) + φ (3) + φ (4) + φ (6) + φ (12) = 1 + 1 + 2 + 2 + 2 + 4 = 12$ .

5. Notons $E_{n} = {k_{1}, \dots, k_{s}}$ avec $s = φ (n)$ . Pour $k \in E_{n}$ , $a \land n = 1$ et $k \land n = 1$ donnent $a k \land n = 1$ (corollaire 2). Soit $ρ (k)$ l'élément de $[⁣ [1, n] ⁣]$ congru à $a k$ modulo $n$ ; alors $ρ (k) \land n = a k \land n = 1$ , donc $ρ (k) \in E_{n}$ . De plus $ρ$ est injective : si $ρ (k) = ρ (k^{'})$ , alors $a k \equiv a k^{'} [n]$ , et la simplification par $a$ (premier avec $n$ ) donne $k \equiv k^{'} [n]$ , donc $k = k^{'}$ . Ainsi $ρ$ est une permutation de $E_{n}$ et $\prod_{k \in E_{n}} ρ (k) = \prod_{k \in E_{n}} k = : M$ . Par ailleurs $M = \prod_{k} ρ (k) \equiv \prod_{k} (a k) = a^{s} M [n] .$ Comme $M$ est un produit d'entiers premiers avec $n$ , $M \land n = 1$ et on peut simplifier : $a^{φ (n)} \equiv 1 [n]$ . Lorsque $n = p$ est premier, $φ (p) = p - 1$ : le théorème d'Euler contient alors le petit théorème de Fermat du §10, soit $a^{p - 1} \equiv 1 [p]$ pour $p ∤ a$ .

6. $3 \land 100 = 1$ et $φ (100) = 40$ , donc $3^{40} \equiv 1 [100]$ . On peut faire mieux à la main : $3^{10} = 59049 \equiv 49 [100]$ , $3^{20} \equiv 49^{2} = 2401 \equiv 1 [100]$ . Comme $2026 = 20 \times 101 + 6$ , $3^{2026} \equiv 3^{6} = 729 \equiv 29 [100]$ . Les deux derniers chiffres sont $29$ .

Après avoir comparé avec le corrigé :

Révisions prépa

Algèbre · 1re année

Arithmétique dans Z

Application du cours5 points

1. Divisions euclidiennes et puissances modulo 13

Effectuer la division euclidienne de $- 250$ par $13$ , puis celle de $250$ par $- 13$ .
Pour chaque $n \in [⁣ [0, 4] ⁣]$ , donner le reste de $5^{n}$ modulo $13$ .
En déduire le reste de $5^{2026}$ modulo $13$ .
Montrer que pour tout $n \in ℕ$ , l'entier $5^{4 n + 2} + 1$ est divisible par $13$ .
Déterminer les entiers naturels $n$ tels que $13$ divise $5^{n} + 8^{n}$ .

Voir le corrigé

3. $5^{4} \equiv 1 [13]$ et $2026 = 4 \times 506 + 2$ , donc $5^{2026} = (5^{4})^{506} \times 5^{2} \equiv 1 \times 12 [13]$ . Le reste vaut $12$ .

4. $5^{4 n + 2} = (5^{4})^{n} \times 5^{2} \equiv 1 \times (- 1) = - 1 [13]$ , donc $5^{4 n + 2} + 1 \equiv 0 [13]$ : $13$ divise $5^{4 n + 2} + 1$ .

5. $8 \equiv - 5 [13]$ , donc $5^{n} + 8^{n} \equiv 5^{n} + (- 5)^{n} [13]$ .

Si $n$ est impair, $(- 5)^{n} = - 5^{n}$ et $5^{n} + 8^{n} \equiv 0 [13]$ .
Si $n$ est pair, $5^{n} + 8^{n} \equiv 2 \times 5^{n} [13]$ . Or $13$ est premier et ne divise ni $2$ ni $5$ , donc (lemme d'Euclide, appliqué à $2 \times 5 \times \dots \times 5$ ) il ne divise pas $2 \times 5^{n}$ .

Conclusion : $13 ∣ 5^{n} + 8^{n} ⟺ n est impair$ .

Après avoir comparé avec le corrigé :

Application du cours5 points

2. Algorithme d'Euclide, Bézout et PPCM

Soient $a = 1517$ et $b = 1073$ .

À l'aide de l'algorithme d'Euclide, calculer $d = a \land b$ .
En remontant l'algorithme, trouver deux entiers $u$ et $v$ vérifiant $a u + b v = d$ .
En déduire $a \lor b$ et la forme irréductible de la fraction $\frac{1073}{1517}$ .
L'équation $1517 x + 1073 y = 100$ a-t-elle des solutions dans $ℤ^{2}$ ?
Résoudre dans $ℤ^{2}$ l'équation $1517 x + 1073 y = 111$ .

Voir le corrigé

4. Si $(x, y)$ était solution, $37$ , qui divise $1517$ et $1073$ , diviserait $100$ : c'est faux. Aucune solution.

Après avoir comparé avec le corrigé :

Application du cours5 points

3. Deux équations diophantiennes

Un club d'étudiants achète des lots de matériel à $23$ dinars et à $17$ dinars et dépense exactement $400$ dinars. (a) Résoudre dans $ℤ^{2}$ l'équation $23 x + 17 y = 400$ . (b) En déduire combien de lots de chaque sorte le club a achetés.
(a) Montrer que l'équation $15 x - 21 y = 8$ n'a pas de solution dans $ℤ^{2}$ . (b) Résoudre dans $ℤ^{2}$ l'équation $15 x - 21 y = 9$ .

Voir le corrigé

2.(a) $3$ divise $15$ et $21$ , donc divise $15 x - 21 y$ ; or $3 ∤ 8$ . Pas de solution (fiche §5 : il faut $15 \land 21 = 3 ∣ c$ ).

Après avoir comparé avec le corrigé :

Application du cours6 points

4. Décomposition en facteurs premiers

Soient $m = 3528$ et $n = 2100$ .

Décomposer $m$ et $n$ en produit de facteurs premiers.
En déduire $m \land n$ et $m \lor n$ , puis vérifier la relation $(m \land n) (m \lor n) = m n$ sur les valuations.
Combien $m$ a-t-il de diviseurs positifs ?
Déterminer le plus petit entier $k \geq 1$ tel que $k n$ soit un carré parfait, puis le plus petit entier $k^{'} \geq 1$ tel que $k^{'} m$ soit le cube d'un entier.
(a) Soit $p$ premier et $N \geq 1$ . Justifier que le nombre d'entiers de $[⁣ [1, N] ⁣]$ divisibles par $p^{j}$ vaut $E ⁣ (\frac{N}{p^{j}})$ , puis que $v_{p} (N!) = \sum_{j \geq 1} E ⁣ (\frac{N}{p^{j}})$ . (b) Par combien de zéros se termine l'écriture décimale de $100!$ ?

Voir le corrigé

Après avoir comparé avec le corrigé :

Niveau devoir6 points

5. PGCD dépendant d'un paramètre

Dans tout l'exercice, $n$ est un entier naturel.

On pose $d_{n} = (n^{2} + 3 n + 5) \land (n + 2)$ . (a) Montrer que $d_{n} = (n + 2) \land 3$ . (b) En déduire la valeur de $d_{n}$ selon le reste de $n$ modulo $3$ .
On pose $e_{n} = (2 n + 3) \land (5 n + 1)$ . (a) Montrer que $e_{n}$ divise $13$ . (b) Déterminer les entiers $n$ pour lesquels $e_{n} = 13$ . (c) Pour quelles valeurs de $n$ la fraction $\frac{5 n + 1}{2 n + 3}$ est-elle irréductible ?
Montrer que pour tout $n \in ℕ^{*}$ , les entiers $n! + 1$ et $(n + 1)! + 1$ sont premiers entre eux. Que se passe-t-il pour $n = 0$ ?

Voir le corrigé

1.(a) $n^{2} + 3 n + 5 = (n + 2) (n + 1) + 3$ . Le lemme $a \land b = b \land (a - k b)$ (fiche §4), avec $k = n + 1$ , donne $d_{n} = (n + 2) \land 3$ .

2.(a) $e_{n}$ divise $2 n + 3$ et $5 n + 1$ , donc la combinaison $5 (2 n + 3) - 2 (5 n + 1) = 13$ .

2.(c) La fraction est irréductible si et seulement si $e_{n} = 1$ , c'est-à-dire $n \equiv̸ 5 [13]$ . Pour $n = 5$ : $\frac{26}{13} = 2$ .

Après avoir comparé avec le corrigé :

Niveau devoir7 points

6. Inverses modulo $n$ , équations et système de congruences

(a) Justifier que $17$ et $60$ sont premiers entre eux et trouver un inverse de $17$ modulo $60$ dans $[⁣ [0, 59] ⁣]$ . (b) Résoudre dans $ℤ$ l'équation $17 x \equiv 9 [60]$ .
(a) Résoudre dans $ℤ$ l'équation $12 x \equiv 18 [30]$ ; combien a-t-elle de solutions dans $[⁣ [0, 29] ⁣]$ ? (b) Montrer que l'équation $12 x \equiv 20 [30]$ n'a pas de solution.
On considère le système $(Σ) : x \equiv 2 [7], x \equiv 5 [9], x \equiv 1 [4] .$ (a) Montrer que $x$ vérifie les deux premières congruences si et seulement si $x \equiv 23 [63]$ . (b) Résoudre $(Σ)$ dans $ℤ$ . (c) Plus généralement, soient $m, n \geq 1$ premiers entre eux et $α, β \in ℤ$ . Montrer que les solutions du système $x \equiv α [m]$ , $x \equiv β [n]$ forment exactement une classe modulo $m n$ .

Voir le corrigé

2.(b) Si $12 x \equiv 20 [30]$ , alors $30 ∣ 12 x - 20$ , donc $6 ∣ 12 x - 20$ , donc $6 ∣ 20$ : faux. Pas de solution.

Après avoir comparé avec le corrigé :

Niveau devoir7 points

7. Petit théorème de Fermat

Soit $p$ un nombre premier.

Montrer que pour tout $k \in [⁣ [1, p - 1] ⁣]$ , $p$ divise $(\binom{p}{k})$ .
En déduire que pour tous $a, b \in ℤ$ , $(a + b)^{p} \equiv a^{p} + b^{p} [p]$ .
Montrer que pour tout $a \in ℕ$ , $a^{p} \equiv a [p]$ , puis étendre ce résultat à $a \in ℤ$ .
Montrer que si $p ∤ a$ , alors $a^{p - 1} \equiv 1 [p]$ .
Application : trouver le reste de $3^{2026}$ modulo $11$ .
Montrer que pour tout $n \in ℤ$ , $2730$ divise $n^{13} - n$ . (On remarquera que $2730 = 2 \times 3 \times 5 \times 7 \times 13$ .)
(a) Montrer que $2^{10} \equiv 1 [341]$ , puis que $2^{340} \equiv 1 [341]$ . (b) L'entier $341$ est-il premier ? Que peut-on dire de la réciproque de la question 4 ?

Voir le corrigé

2. Binôme : $(a + b)^{p} = a^{p} + b^{p} + \sum_{k = 1}^{p - 1} (\binom{p}{k}) a^{k} b^{p - k}$ , et chaque terme de la somme est multiple de $p$ (question 1).

4. $p ∣ a^{p} - a = a (a^{p - 1} - 1)$ . Si $p ∤ a$ , alors $p \land a = 1$ ( $p$ premier) et le lemme de Gauss donne $p ∣ a^{p - 1} - 1$ .

7.(a) $2^{10} = 1024 = 3 \times 341 + 1$ , donc $2^{10} \equiv 1 [341]$ , puis $2^{340} = (2^{10})^{34} \equiv 1 [341]$ .

Après avoir comparé avec le corrigé :

Niveau devoir7 points

8. Les nombres de Fermat

Pour $n \in ℕ$ , on pose $F_{n} = 2^{2^{n}} + 1$ .

Calculer $F_{0}, F_{1}, F_{2}, F_{3}$ .
Montrer que $F_{n + 1} - 2 = (F_{n} - 2) F_{n}$ , puis que pour tout $n \geq 1$ , $F_{0} F_{1} \dots F_{n - 1} = F_{n} - 2$ .
En déduire que pour $m \neq n$ , $F_{m} \land F_{n} = 1$ .
En déduire une nouvelle preuve de l'existence d'une infinité de nombres premiers.
(a) Vérifier que $641 = 5 \times 2^{7} + 1 = 5^{4} + 2^{4}$ . (b) En déduire, sans calculer $F_{5}$ , que $641$ divise $F_{5}$ . Les $F_{n}$ sont-ils tous premiers ?
Soit $m \geq 1$ tel que $2^{m} + 1$ est premier. Montrer que $m$ est une puissance de $2$ . (On pourra écrire $m = 2^{s} t$ avec $t$ impair.)

Voir le corrigé

1. $F_{0} = 3$ , $F_{1} = 5$ , $F_{2} = 17$ , $F_{3} = 257$ .

5.(a) $5 \times 2^{7} + 1 = 640 + 1 = 641$ et $5^{4} + 2^{4} = 625 + 16 = 641$ .

Après avoir comparé avec le corrigé :

Synthèse, niveau concours10 points

9. Problème : PGCD des nombres de Fibonacci

On définit la suite $(F_{n})_{n \in ℕ}$ par $F_{0} = 0$ , $F_{1} = 1$ et $F_{n + 2} = F_{n + 1} + F_{n}$ pour tout $n \in ℕ$ . Tous les $F_{n}$ sont des entiers naturels.

Partie A — Premières propriétés.

Calculer $F_{n}$ pour $n \in [⁣ [0, 12] ⁣]$ .
Montrer que pour tout $n \geq 1$ , $F_{n + 1} F_{n - 1} - F_{n}^{2} = (- 1)^{n}$ . En déduire que deux termes consécutifs de la suite sont toujours premiers entre eux.
Montrer que pour tous $m \geq 1$ et $n \geq 0$ : $F_{m + n} = F_{m} F_{n + 1} + F_{m - 1} F_{n}$ . (On pourra raisonner par récurrence double sur $n$ , $m$ étant fixé.)

Partie B — Le théorème du PGCD.

Montrer que pour tous $m, k \geq 1$ , $F_{m}$ divise $F_{k m}$ .
Soient $n \geq m \geq 1$ . Montrer que $F_{n} \land F_{m} = F_{n - m} \land F_{m}$ .
En déduire que pour tous $m, n \geq 1$ : $F_{m} \land F_{n} = F_{m \land n}$ . (On pourra raisonner par récurrence forte sur $m + n$ .)
Calculer $F_{84} \land F_{60}$ et $F_{100} \land F_{51}$ , sans calculer ces nombres.

Partie C — Applications.

Soit $m \geq 3$ . Montrer que $F_{m} ∣ F_{n} ⟺ m ∣ n$ .
Montrer que si $n \geq 5$ et $F_{n}$ est premier, alors $n$ est premier. L'implication inverse est-elle exacte ? (On pourra considérer $F_{19} = 4181 = 37 \times 113$ .)

Voir le corrigé

1. $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144$ .

Après avoir comparé avec le corrigé :

Synthèse, niveau concours10 points

10. Problème type concours : théorème de Wilson et carrés modulo $p$

Dans tout le problème, $p$ désigne un nombre premier impair. Les questions sont numérotées en continu.

Partie I — Le théorème de Wilson.

▶ Q.1 Montrer que pour tout $a \in [⁣ [1, p - 1] ⁣]$ , il existe un unique $a^{'} \in [⁣ [1, p - 1] ⁣]$ tel que $a a^{'} \equiv 1 [p]$ .

▶ Q.2 Montrer que $a^{'} = a$ si et seulement si $a \in {1, p - 1}$ .

▶ Q.3 En regroupant chaque facteur avec son inverse, montrer que $(p - 1)! \equiv - 1 [p]$ . Vérifier le résultat pour $p = 7$ .

▶ Q.4 Soit $n \geq 2$ un entier tel que $(n - 1)! \equiv - 1 [n]$ . Montrer que $n$ est premier.

Partie II — L'équation $x^{2} \equiv - 1 [p]$ .

▶ Q.5 On suppose $p \equiv 3 [4]$ . Montrer, à l'aide du petit théorème de Fermat, que l'équation $x^{2} \equiv - 1 [p]$ n'a pas de solution dans $ℤ$ .

▶ Q.6 On suppose $p \equiv 1 [4]$ et on pose $x_{0} = (\frac{p - 1}{2})!$ . Montrer que $x_{0}^{2} \equiv - 1 [p]$ . (On pourra associer $k$ et $p - k$ dans $(p - 1)!$ .)

▶ Q.7 Pour $p = 13$ , déterminer le reste de $x_{0}$ modulo $13$ et vérifier le résultat de Q.6.

Partie III — Infinité de nombres premiers dans deux familles.

▶ Q.8 Soit $n \in ℤ$ . Montrer que tout diviseur premier impair de $n^{2} + 1$ est congru à $1$ modulo $4$ .

▶ Q.9 En déduire qu'il existe une infinité de nombres premiers congrus à $1$ modulo $4$ . (On pourra considérer $N = (2 p_{1} \dots p_{k})^{2} + 1$ .)

▶ Q.10 Montrer qu'il existe une infinité de nombres premiers congrus à $3$ modulo $4$ . (On pourra considérer $4 p_{1} \dots p_{k} - 1$ .)

Voir le corrigé

Q.7 $x_{0} = 6! = 720 = 13 \times 55 + 5$ , donc $x_{0} \equiv 5 [13]$ , et $5^{2} = 25 = 2 \times 13 - 1 \equiv - 1 [13]$ .

Q.8 Soit $q$ premier impair avec $q ∣ n^{2} + 1$ : $n^{2} \equiv - 1 [q]$ . D'après Q.5 (appliquée à $q$ ), $q \equiv̸ 3 [4]$ ; $q$ étant impair, $q \equiv 1 [4]$ .

Après avoir comparé avec le corrigé :

Niveau devoir10 points

11. L'indicatrice d'Euler

Classique du programme : indicatrice d'Euler.

(1,5 point) Déterminer $φ (1)$ , $φ (12)$ en listant $E_{12}$ , puis montrer que $φ (p^{k}) = p^{k} - p^{k - 1}$ pour $p$ premier et $k \geq 1$ . Calculer $φ (81)$ .
(2,5 points) Soient $m, n \in ℕ^{*}$ premiers entre eux. À $x \in [⁣ [1, m n] ⁣]$ on associe le couple $ψ (x) = (r, s)$ , où $r$ est l'unique élément de $[⁣ [1, m] ⁣]$ congru à $x$ modulo $m$ et $s$ l'unique élément de $[⁣ [1, n] ⁣]$ congru à $x$ modulo $n$ . a) Montrer que $ψ$ est injective, puis bijective de $[⁣ [1, m n] ⁣]$ sur $[⁣ [1, m] ⁣] \times [⁣ [1, n] ⁣]$ . b) Montrer que $x \land m n = 1$ si et seulement si $r \land m = 1$ et $s \land n = 1$ . En déduire que $φ (m n) = φ (m) φ (n)$ .
(1,5 point) Déduire que si $n = p_{1}^{α_{1}} \dots p_{r}^{α_{r}}$ (facteurs premiers distincts), alors $φ (n) = n \prod_{i = 1}^{r} (1 - \frac{1}{p_{i}})$ . Calculer $φ (360)$ et $φ (100)$ . Montrer que $φ (n)$ est pair dès que $n \geq 3$ .
(2 points) Montrer que $\sum_{d ∣ n} φ (d) = n$ , la somme portant sur les diviseurs positifs de $n$ . On pourra classer les éléments de $[⁣ [1, n] ⁣]$ selon la valeur de $k \land n$ . Vérifier pour $n = 12$ .
(2 points) Théorème d'Euler. Soit $n \geq 2$ et $a \in ℤ$ avec $a \land n = 1$ . Montrer que $a^{φ (n)} \equiv 1 [n]$ . Quel résultat du §10 se trouve ainsi généralisé lorsque $n$ est premier ?
(0,5 point) Déterminer les deux derniers chiffres de l'écriture décimale de $3^{2026}$ .

Voir le corrigé

2.b) Comme $x \equiv r [m]$ , on a $x = r + q m$ et, par le lemme clé de l'algorithme d'Euclide, $x \land m = r \land m$ ; de même $x \land n = s \land n$ .

Si $x \land m n = 1$ , tout diviseur commun de $x$ et $m$ divise $x$ et $m n$ : $x \land m = 1$ , donc $r \land m = 1$ ; de même $s \land n = 1$ .
Réciproquement, si $r \land m = 1$ et $s \land n = 1$ , alors $x \land m = 1$ et $x \land n = 1$ , d'où $x \land m n = 1$ (corollaire 2 du lemme de Gauss).

Par la bijection $ψ$ , les éléments de $E_{m n}$ correspondent exactement aux couples de $E_{m} \times E_{n}$ : $φ (m n) = Card (E_{m} \times E_{n}) = φ (m) φ (n) .$

Après avoir comparé avec le corrigé :

1. Divisions euclidiennes et puissances modulo 13

2. Algorithme d'Euclide, Bézout et PPCM

3. Deux équations diophantiennes

4. Décomposition en facteurs premiers

5. PGCD dépendant d'un paramètre

6. Inverses modulo n, équations et système de congruences

7. Petit théorème de Fermat

8. Les nombres de Fermat

9. Problème : PGCD des nombres de Fibonacci

10. Problème type concours : théorème de Wilson et carrés modulo p

11. L'indicatrice d'Euler

1. Divisions euclidiennes et puissances modulo 13

2. Algorithme d'Euclide, Bézout et PPCM

3. Deux équations diophantiennes

4. Décomposition en facteurs premiers

5. PGCD dépendant d'un paramètre

6. Inverses modulo n, équations et système de congruences

7. Petit théorème de Fermat

8. Les nombres de Fermat

9. Problème : PGCD des nombres de Fibonacci

10. Problème type concours : théorème de Wilson et carrés modulo p

11. L'indicatrice d'Euler

6. Inverses modulo $n$ , équations et système de congruences

10. Problème type concours : théorème de Wilson et carrés modulo $p$

6. Inverses modulo $n$ , équations et système de congruences

10. Problème type concours : théorème de Wilson et carrés modulo $p$