Point de départ · 1

Dans $\mathbb{N}$ , la division de $23$ par $5$ s'écrit $23 = 5 \times 4 + 3$ . Pour diviser $-23$ par $5$ dans $\mathbb{Z}$ , peut-on écrire $-23 = 5 \times (-4) - 3$ ?

Remarque

Non. Même lorsque le dividende ou le diviseur est négatif, le reste d'une division euclidienne doit impérativement être positif ou nul. L'écriture correcte est $-23 = 5 \times (-5) + 2$ .

Définition · 2

Théorème de la division euclidienne dans Z

$a = bq + r \quad \text{avec} \quad 0 \le r < |b|$

Pour tout entier relatif $a$ et tout entier relatif non nul $b$ , il existe un unique couple d'entiers relatifs $(q, r)$ vérifiant cette relation.

Vocabulaire

Dividende — a
Diviseur — b
Quotient — q
Reste — r

Remarque

La condition $0 \le r < |b|$ est absolue : le reste est toujours un entier naturel, quel que soit le signe de $a$ ou de $b$ .

Exemple travaillé · 3

Détermine le quotient $q$ et le reste $r$ de la division euclidienne de $a = -143$ par $b = 12$ .

1

On évalue le quotient approché : $\frac{-143}{12} \approx -11{,}92$ .

2

Comme le diviseur $b = 12$ est strictement positif, le quotient euclidien $q$ est l'entier immédiatement inférieur : $q = -12$ .

3

r = a - bq = -143 - 12 \times (-12) = -143 + 144 = 1

4

On vérifie la condition fondamentale : $0 \le 1 < 12$ . L'égalité s'écrit $-143 = 12 \times (-12) + 1$ .

Exemple travaillé · 4

Détermine le quotient $q$ et le reste $r$ de la division euclidienne de $a = 3171$ par $b = -19$ .

1

On effectue d'abord la division euclidienne par la valeur absolue $|b| = |-19| = 19$ :

2

3171 = 19 \times 166 + 17 \quad \text{avec} \quad 0 \le 17 < 19

3

On introduit le diviseur négatif $-19$ en compensant sur le quotient :

4

3171 = (-19) \times (-166) + 17

5

Le reste $r = 17$ vérifie bien $0 \le 17 < |-19|$ . On a donc $q = -166$ et $r = 17$ .

Piège classique · 5

Quels sont le quotient $q$ et le reste $r$ de la division euclidienne de $-23$ par $-5$ ?

Attention

Prendre $q = 4$ par troncature de $\frac{-23}{-5} = 4{,}6$ , ce qui conduit à $-23 = (-5) \times 4 - 3$ avec un reste négatif illicite $r = -3$ .

À la place : Le reste doit vérifier $0 \le r < |-5| = 5$ . Il faut ajuster le quotient à $q = 5$ : $-23 = (-5) \times 5 + 2$ , d'où $r = 2$ .

Exemple travaillé · 6

Détermine, s'ils existent, les entiers $a$ et $b$ vérifiant $a + b = 44$ , sachant que la division euclidienne de $a$ par $b$ a pour quotient $q = 6$ et pour reste $r = 2$ .

1

Par définition de la division euclidienne, on pose $a = 6b + 2$ sous la condition obligatoire $0 \le 2 < |b|$ .

2

On remplace $a$ dans l'équation de somme :

3

(6b + 2) + b = 44 \iff 7b + 2 = 44 \iff 7b = 42

4

On obtient $b = 6$ , puis $a = 6 \times 6 + 2 = 38$ .

5

On contrôle la condition de validité du reste : $2 < |6| = 6$ est vérifié. L'unique couple solution est $(a, b) = (38, 6)$ .

Vérification · 7

Parmi les égalités suivantes, laquelle traduit la division euclidienne de $-307$ par $-7$ ?

Remarque

Seule l'égalité $-307 = (-7) \times 44 + 1$ vérifie la condition stricte sur le reste : $0 \le 1 < |-7| = 7$ . Pour $q = 43$ , le reste $-6$ est négatif ; pour $q = 45$ , le reste $8$ dépasse la borne $|-7| = 7$ .

Point de départ · 8

On considère les entiers $a = 2n + 1$ et $b = n$ pour un entier naturel $n$ . On remarque l'égalité $1 \times (2n + 1) - 2 \times n = 1$ . Un diviseur commun à $a$ et $b$ peut-il être égal à $3$ ?

Remarque

Tout diviseur commun $d$ à $a$ et $b$ divise n'importe quelle combinaison linéaire $au + bv$ . Ici, $d$ doit diviser $1$ , donc $d$ ne peut valoir que $1$ : les entiers $a$ et $b$ sont premiers entre eux.

Définition · 9

Théorème de Bézout

$a \wedge b = 1 \iff \exists (u, v) \in \mathbb{Z}^2, \quad au + bv = 1$

Deux entiers relatifs non nuls $a$ et $b$ sont premiers entre eux si et seulement s'il existe une combinaison linéaire de $a$ et $b$ égale à $1$ .

Vocabulaire

Identité de Bézout — au + bv = 1
Coefficients de Bézout — (u, v)

Remarque

Les coefficients $u$ et $v$ ne sont pas uniques : si $(u_0, v_0)$ convient, il existe une infinité d'autres couples solutions.

Exemple travaillé · 10

Soit $n$ un entier naturel non nul. Démontre que les entiers $A = 3n + 1$ et $B = 2n + 1$ sont premiers entre eux.

1

On cherche deux entiers relatifs $u$ et $v$ tels que la combinaison $uA + vB$ élimine la variable $n$ .

2

2A - 3B = 2(3n + 1) - 3(2n + 1) = 6n + 2 - 6n - 3 = -1

3

On multiplie les deux membres par $-1$ pour obtenir une combinaison égale à $1$ :

4

(-2)A + 3B = 1

5

Il existe deux coefficients entiers $u = -2$ et $v = 3$ vérifiant $uA + vB = 1$ . D'après le théorème de Bézout, $A \wedge B = 1$ pour tout $n \in \mathbb{N}^*$ .

Exemple travaillé · 11

Détermine deux entiers relatifs $u$ et $v$ tels que $27u + 10v = 1$ .

1

On effectue les divisions euclidiennes successives de l'algorithme d'Euclide :

2

\begin{aligned} 27 &= 10 \times 2 + 7 \\ 10 &= 7 \times 1 + 3 \\ 7 &= 3 \times 2 + 1 \end{aligned}

3

Le dernier reste non nul est $1$ , ce qui confirme $27 \wedge 10 = 1$ . On exprime le reste $1$ à l'aide de la dernière division :

4

1 = 7 - 3 \times 2

5

On remplace le reste $3 = 10 - 7 \times 1$ dans cette égalité :

6

1 = 7 - (10 - 7 \times 1) \times 2 = 7 \times 3 - 10 \times 2

7

On remplace enfin le reste $7 = 27 - 10 \times 2$ :

8

1 = (27 - 10 \times 2) \times 3 - 10 \times 2 = 27 \times 3 - 10 \times 8

9

On obtient l'égalité $27(3) + 10(-8) = 1$ . Le couple $(u, v) = (3, -8)$ est une solution.

Piège classique · 12

Soient $a$ et $b$ deux entiers relatifs non nuls. On suppose qu'il existe deux entiers $u$ et $v$ tels que $au + bv = 6$ . Que peut-on affirmer avec certitude sur le PGCD $a \wedge b$ ?

Attention

Conclure que $a \wedge b = 6$ par analogie hâtive avec le théorème de Bézout.

À la place : L'équivalence de Bézout n'est stricte que pour $1$ . L'égalité $au + bv = 6$ prouve seulement que tout diviseur commun à $a$ et $b$ divise $6$ , donc que $a \wedge b$ divise $6$ (il peut valoir $1, 2, 3$ ou $6$ ). Par exemple, pour $a = 4$ et $b = 2$ , on a $4(2) + 2(-1) = 6$ , mais $4 \wedge 2 = 2 \ne 6$ .

Exemple travaillé · 13

Détermine tous les couples $(a, b)$ d'entiers naturels non nuls tels que $a \wedge b = 15$ et $a \vee b = 60$ .

1

On utilise la relation liant PGCD et PPCM pour des entiers naturels : $(a \wedge b)(a \vee b) = ab$ .

2

ab = 15 \times 60 = 900

3

On pose $a = 15a'$ et $b = 15b'$ avec $a', b' \in \mathbb{N}^*$ et la condition indispensable $a' \wedge b' = 1$ .

4

(15a')(15b') = 900 \iff 225 a'b' = 900 \iff a'b' = 4

5

Les couples d'entiers naturels $(a', b')$ dont le produit vaut $4$ sont $(1, 4)$ , $(4, 1)$ et $(2, 2)$ . Or $2 \wedge 2 = 2 \ne 1$ , donc le couple $(2, 2)$ est exclu.

6

Les seuls couples réduits valides sont $(a', b') \in \{(1, 4), (4, 1)\}$ . En multipliant par $15$ , on obtient les solutions :

7

(a, b) \in \{(15, 60), (60, 15)\}

Vérification · 14

On considère un entier naturel $n \ge 1$ . Parmi les affirmations suivantes, laquelle est exacte ?

Remarque

L'égalité $1 \times (n+1) + (-1) \times n = 1$ est une identité de Bézout : deux entiers consécutifs sont donc toujours premiers entre eux. En revanche, $5a + 3b = 2$ n'implique pas que le PGCD vaut $2$ (il divise $2$ ), et $(a \wedge b)(a \vee b) = 32$ donnerait $a \vee b = 32 / 4 = 8$ .

Point de départ · 15

Si un entier relatif $n$ vérifie $4 \mid 6n$ , peut-on affirmer avec certitude que $4$ divise $n$ ?

Remarque

Non. Par exemple, pour $n = 2$ , on a $6n = 12$ et $4$ divise bien $12$ , mais $4$ ne divise pas $2$ . La simplification n'est possible que si le diviseur est premier avec le coefficient.

Définition · 16

Lemme de Gauss et divisibilité par un produit

$a \mid bc \quad \text{et} \quad a \wedge b = 1 \implies a \mid c$

Soient $a$ , $b$ et $c$ trois entiers relatifs non nuls. Si $a$ divise le produit $bc$ et si $a$ est premier avec $b$ , alors $a$ divise nécessairement $c$ .

Corollaire

$a \mid n, \quad b \mid n \quad \text{et} \quad a \wedge b = 1 \implies ab \mid n$

Remarque

La divisibilité simultanée par $a$ et $b$ n'entraîne la divisibilité par leur produit $ab$ que si $a$ et $b$ sont premiers entre eux.

Piège classique · 17

Un entier relatif $N$ est divisible par $4$ et par $6$ . Est-il obligatoirement divisible par $24$ ?

Attention

Multiplier directement les deux diviseurs sans vérifier s'ils sont premiers entre eux, en affirmant que $4 \mid N$ et $6 \mid N \implies 24 \mid N$ .

À la place : Comme $4 \wedge 6 = 2 \ne 1$ , on ne peut pas appliquer le corollaire de Gauss. La divisibilité conjointe assure seulement que $N$ est divisible par $4 \vee 6 = 12$ . Par exemple, $N = 12$ est bien divisible par $4$ et par $6$ , mais n'est pas divisible par $24$ .

Définition · 18

Équations diophantiennes linéaires ax + by = c

$ax + by = c \text{ admet des solutions dans } \mathbb{Z}^2 \iff (a \wedge b) \mid c$

Soient $a, b \in \mathbb{Z}^*$ et $c \in \mathbb{Z}$ . Une équation linéaire $ax + by = c$ possède des solutions entières si et seulement si le plus grand diviseur commun de $a$ et $b$ divise le second membre $c$ .

Remarque

Si $d = a \wedge b$ divise $c$ , on simplifie l'équation en divisant par $d$ pour obtenir $a'x + b'y = c'$ avec $a' \wedge b' = 1$ avant d'appliquer le lemme de Gauss.

Exemple travaillé · 19

Résous dans $\mathbb{Z}^2$ l'équation : $35x - 14y = 7$ .

1

On détermine le PGCD des coefficients : $35 \wedge 14 = 7$ . Comme $7$ divise le second membre $7$ , l'équation admet des solutions dans $\mathbb{Z}^2$ .

2

On simplifie l'équation en divisant tous les termes par $7$ :

3

5x - 2y = 1

4

On cherche une solution particulière évidente : $5(1) - 2(2) = 1$ , donc $(x_0, y_0) = (1, 2)$ convient.

5

On soustrait l'égalité particulière à l'équation simplifiée :

6

5(x - 1) - 2(y - 2) = 0 \iff 5(x - 1) = 2(y - 2)

7

$2$ divise $5(x - 1)$ et $2 \wedge 5 = 1$ . D'après le lemme de Gauss, $2$ divise $x - 1$ , donc il existe $k \in \mathbb{Z}$ tel que $x - 1 = 2k$ , soit $x = 1 + 2k$ .

8

On remplace $x - 1$ par $2k$ dans l'égalité : $5(2k) = 2(y - 2) \iff y - 2 = 5k$ , soit $y = 2 + 5k$ .

9

L'ensemble des solutions est $S = \{(1 + 2k, 2 + 5k) \, ; \, k \in \mathbb{Z}\}$ .

Exemple travaillé · 20

On considère dans $\mathbb{Z}^2$ l'équation $11x + 8y = 79$ . Détermine l'ensemble des couples $(x, y)$ d'entiers naturels non nuls solutions de cette équation.

1

On remarque la solution particulière $(5, 3)$ car $11(5) + 8(3) = 55 + 24 = 79$ .

2

On écrit l'égalité avec la solution particulière :

3

11(x - 5) + 8(y - 3) = 0 \iff 11(x - 5) = 8(3 - y)

4

Comme $8$ divise $11(x - 5)$ et $8 \wedge 11 = 1$ , d'après le lemme de Gauss, $8$ divise $x - 5$ . Il existe donc $k \in \mathbb{Z}$ tel que $x = 5 - 8k$ et $y = 3 + 11k$ .

5

On traduit la condition $(x, y) \in (\mathbb{N}^*)^2$ sous forme d'inéquations sur $k$ :

6

\begin{cases} 5 - 8k \ge 1 \\ 3 + 11k \ge 1 \end{cases} \iff \begin{cases} 8k \le 4 \\ 11k \ge -2 \end{cases} \iff -\frac{2}{11} \le k \le \frac{1}{2}

7

Le seul entier relatif compris dans cet intervalle est $k = 0$ . L'unique couple d'entiers naturels non nuls solution est $(x, y) = (5, 3)$ .

Vérification · 21

L'équation diophantienne $24x - 16y = 25$ admet-elle des solutions dans $\mathbb{Z}^2$ ?

Remarque

On a $24 \wedge 16 = 8$ . Pour tout couple d'entiers $(x, y)$ , $24x - 16y = 8(3x - 2y)$ est un multiple de $8$ . Comme $8$ ne divise pas $25$ , l'équation n'admet aucune solution entière.

Point de départ · 22

Pour déterminer le reste de $29^{100} - 8^{100}$ dans la division par $7$ , doit-on calculer cette différence gigantesque ?

Remarque

Non. On observe que $29 = 7 \times 4 + 1$ et $8 = 7 \times 1 + 1$ ont tous les deux pour reste $1$ modulo $7$ . Leur différence $29 - 8 = 21$ est un multiple de $7$ . Les deux nombres ont le même comportement vis-à-vis des puissances et des opérations modulo $7$ .

Définition · 23

Congruence modulo n et propriétés opératoires

$a \equiv b \pmod n \iff a - b \in n\mathbb{Z}$

Soit $n \in \mathbb{N}^*$ . Deux entiers $a$ et $b$ sont dits congrus modulo $n$ si leur différence est un multiple de $n$ , ce qui équivaut à dire qu'ils ont le même reste dans la division euclidienne par $n$ .

$a \equiv b \pmod n \quad \text{et} \quad c \equiv d \pmod n \implies \begin{cases} a + c \equiv b + d \pmod n \\ ac \equiv bd \pmod n \\ a^k \equiv b^k \pmod n \; (k \in \mathbb{N}) \end{cases}$

Remarque

La relation de congruence est compatible avec l'addition, la multiplication et l'élévation aux puissances entières.

Exemple travaillé · 24

Détermine le reste de la division euclidienne de $N = 45^{33} \times 19^{21}$ par $8$ .

1

On réduit d'abord chaque base modulo $8$ :

2

45 = 8 \times 5 + 5 \equiv 5 \pmod 8 \quad \text{et} \quad 19 = 8 \times 2 + 3 \equiv 3 \pmod 8

3

On calcule les carrés pour faire apparaître des résidus égaux à $1$ :

4

5^2 = 25 = 8 \times 3 + 1 \equiv 1 \pmod 8 \quad \text{et} \quad 3^2 = 9 \equiv 1 \pmod 8

5

On décompose les exposants impairs sous forme $2k + 1$ :

6

45^{33} \equiv 5^{33} = (5^2)^{16} \times 5 \equiv 1^{16} \times 5 \equiv 5 \pmod 8

7

19^{21} \equiv 3^{21} = (3^2)^{10} \times 3 \equiv 1^{10} \times 3 \equiv 3 \pmod 8

8

On effectue le produit modulaire :

9

N \equiv 5 \times 3 = 15 = 8 \times 1 + 7 \equiv 7 \pmod 8

10

Comme $0 \le 7 < 8$ , le reste de la division euclidienne de $N$ par $8$ est $7$ .

Piège classique · 25

On considère l'égalité modulaire $2x \equiv 4 \pmod{10}$ . Peut-on simplifier directement par $2$ et conclure que $x \equiv 2 \pmod{10}$ ?

Attention

Diviser les deux membres par $2$ sans modifier le module $10$ , ce qui oublie la moitié des solutions dans $\mathbb{Z}$ .

À la place : Comme $2$ et $10$ ne sont pas premiers entre eux ( $2 \wedge 10 = 2$ ), la division par $2$ impose de diviser aussi le module par $2$ : $2x \equiv 4 \pmod{10} \iff x \equiv 2 \pmod 5$ . Dans $\mathbb{Z}$ , cela donne $x \equiv 2 \pmod{10}$ ou $x \equiv 7 \pmod{10}$ .

Exemple travaillé · 26

Résous dans $\mathbb{Z}$ l'équation modulaire : $6x \equiv 9 \pmod{15}$ .

1

On traduit la congruence sous forme d'une égalité de divisibilité dans $\mathbb{Z}$ :

2

6x - 9 = 15k \quad (k \in \mathbb{Z})

3

On simplifie par le diviseur commun $6 \wedge 15 = 3$ :

4

2x - 3 = 5k \iff 2x \equiv 3 \pmod 5

5

On cherche l'inverse de $2$ modulo $5$ . Comme $2 \times 3 = 6 \equiv 1 \pmod 5$ , l'inverse est $3$ .

6

On multiplie les deux membres par $3$ :

7

3(2x) \equiv 3(3) \pmod 5 \iff x \equiv 9 \equiv 4 \pmod 5

8

Les solutions dans $\mathbb{Z}$ sont les entiers de la forme $x = 4 + 5m$ avec $m \in \mathbb{Z}$ .

Piège classique · 27

On considère dans $\mathbb{Z}$ l'équation $(x - 1)(x - 2) \equiv 0 \pmod 6$ . Les seules solutions sont-elles $x \equiv 1 \pmod 6$ et $x \equiv 2 \pmod 6$ ?

Attention

Appliquer la règle du produit nul comme dans un corps en affirmant que $x - 1 \equiv 0$ ou $x - 2 \equiv 0 \pmod 6$ .

À la place : Le module $6$ n'est pas un nombre premier : il admet des diviseurs de zéro car $2 \times 3 = 6 \equiv 0 \pmod 6$ . Pour $x = 4$ , $(4 - 1)(4 - 2) = 3 \times 2 = 6 \equiv 0 \pmod 6$ . Pour $x = 5$ , $(5 - 1)(5 - 2) = 4 \times 3 = 12 \equiv 0 \pmod 6$ . Les solutions sont donc $x \equiv 1, 2, 4, 5 \pmod 6$ .

Vérification · 28

Pour tout entier relatif $x$ , l'équation $4x \equiv 8 \pmod{12}$ équivaut à :

Remarque

On a $4 \wedge 12 = 4$ . En divisant les coefficients et le module par $4$ , on obtient $x \equiv 2 \pmod 3$ . Dans $\mathbb{Z}$ , les solutions s'écrivent $x = 2 + 3k$ , ce qui correspond modulo $12$ aux quatre classes $x \in \{2, 5, 8, 11\}$ .

Point de départ · 29

On choisit le nombre premier $p = 7$ . Que valent $2^6$ et $3^6$ modulo $7$ ?

Remarque

On a $2^6 = 64 = 7 \times 9 + 1 \equiv 1 \pmod 7$ . De même, $3^3 = 27 \equiv -1 \pmod 7$ , donc $3^6 = (3^3)^2 \equiv (-1)^2 = 1 \pmod 7$ . Pour tout entier non divisible par $7$ , la puissance $6$ -ième donne toujours un reste égal à $1$ .

Définition · 30

Petit théorème de Fermat

$a^{p-1} \equiv 1 \pmod p$

p \text{ est premier et } p \nmid a

Si $p$ est un nombre premier et si $a$ est un entier non divisible par $p$ , alors $a^{p-1} - 1$ est un multiple de $p$ .

Corollaire

$a^p \equiv a \pmod p$

Pour tout entier relatif $a$ et tout nombre premier $p$ , l'entier $a^p - a$ est divisible par $p$ , sans aucune condition sur $a$ .

Exemple travaillé · 31

Détermine le reste de la division euclidienne de $15^{3601}$ par $13$ .

1

On réduit d'abord la base modulo $13$ :

2

15 = 13 \times 1 + 2 \equiv 2 \pmod{13}

3

Comme $13$ est un nombre premier et $13$ ne divise pas $2$ , d'après le petit théorème de Fermat :

4

2^{13-1} = 2^{12} \equiv 1 \pmod{13}

5

On effectue la division euclidienne de l'exposant $3601$ par $12$ :

6

3601 = 12 \times 300 + 1

7

On décompose la puissance modulaire :

8

15^{3601} \equiv 2^{3601} = (2^{12})^{300} \times 2^1 \equiv 1^{300} \times 2 \equiv 2 \pmod{13}

9

Comme $0 \le 2 < 13$ , le reste de la division euclidienne de $15^{3601}$ par $13$ est $2$ .

Piège classique · 32

Pour déterminer le reste de $3^{1000}$ modulo $7$ , par quel entier effectue-t-on la division euclidienne de l'exposant $1000$ ?

Attention

Diviser l'exposant par le module $7$ en pensant que la périodicité de la puissance dépend directement de la valeur du diviseur.

À la place : D'après le petit théorème de Fermat, comme $7$ est premier et ne divise pas $3$ , on a $3^{7-1} = 3^6 \equiv 1 \pmod 7$ . La période de l'exposant est $6$ , pas $7$ . On divise donc $1000$ par $6$ : $1000 = 6 \times 166 + 4$ , d'où $3^{1000} \equiv 3^4 = 81 \equiv 4 \pmod 7$ .

Exemple travaillé · 33

Démontre que pour tout entier naturel $n$ , l'entier $A = n^7 - n$ est divisible par $42$ .

1

On décompose $42$ en produit de facteurs premiers : $42 = 2 \times 3 \times 7$ .

2

Comme $2$ , $3$ et $7$ sont des nombres premiers distincts, ils sont deux à deux premiers entre eux. D'après le corollaire du lemme de Gauss, il suffit de démontrer que $A$ est divisible par $2$ , par $3$ et par $7$ .

3

Divisibilité par $2$ : pour tout entier naturel $n$ , $n$ et $n^7$ ont la même parité, donc $n^7 - n \equiv 0 \pmod 2$ .

4

Divisibilité par $3$ : d'après le corollaire du théorème de Fermat, $n^3 \equiv n \pmod 3$ . On en déduit :

5

n^7 = (n^3)^2 \times n \equiv n^2 \times n = n^3 \equiv n \pmod 3 \implies n^7 - n \equiv 0 \pmod 3

6

Divisibilité par $7$ : d'après le corollaire du théorème de Fermat avec le nombre premier $7$ :

7

n^7 \equiv n \pmod 7 \implies n^7 - n \equiv 0 \pmod 7

8

L'entier $A$ est divisible par $2$ , $3$ et $7$ , qui sont deux à deux premiers entre eux. Par conséquent, leur produit $2 \times 3 \times 7 = 42$ divise $A$ pour tout $n \in \mathbb{N}$ .

Piège classique · 34

Soit $n$ un entier non divisible par $3$ ni par $7$ . Un élève affirme : « Comme $n \wedge 21 = 1$ , d'après le petit théorème de Fermat on a $n^{20} \equiv 1 \pmod{21}$ ». Cette déduction est-elle exacte ?

Attention

Appliquer l'égalité $a^{m-1} \equiv 1 \pmod m$ à un entier composite $m = 21$ .

À la place : Le petit théorème de Fermat exige formellement que le module soit un nombre premier. Comme $21 = 3 \times 7$ n'est pas premier, la formule ne s'applique pas directement. Il faut déduire $n^2 \equiv 1 \pmod 3$ et $n^6 \equiv 1 \pmod 7$ , puis combiner ces résultats.

Vérification · 35

Soit $n$ un entier non divisible par $5$ . Quel est le reste de la division euclidienne de $n^8 + 3n^4 + 1$ par $5$ ?

Remarque

Comme $5$ est premier et ne divise pas $n$ , d'après le petit théorème de Fermat, $n^4 \equiv 1 \pmod 5$ . Par suite, $n^8 = (n^4)^2 \equiv 1^2 = 1 \pmod 5$ . L'expression devient $1 + 3(1) + 1 = 5 \equiv 0 \pmod 5$ . Le reste est donc $0$ .

Point de départ · 36

Quels sont les restes possibles de $x^2$ dans la division euclidienne par $4$ , pour tout entier relatif $x$ ?

Remarque

Si $x$ est pair, $x = 2k$ , alors $x^2 = 4k^2 \equiv 0 \pmod 4$ . Si $x$ est impair, $x = 2k+1$ , alors $x^2 = 4(k^2+k)+1 \equiv 1 \pmod 4$ . Un carré parfait n'est donc jamais congru à $2$ ou à $3$ modulo $4$ .

Définition · 37

Résidus quadratiques modulo 4 et modulo 8

$\forall x \in \mathbb{Z}, \quad x^2 \equiv 0 \pmod 4 \quad \text{ou} \quad x^2 \equiv 1 \pmod 4$

$\forall x \in \mathbb{Z}, \quad x^2 \equiv 0 \pmod 8, \quad x^2 \equiv 1 \pmod 8 \quad \text{ou} \quad x^2 \equiv 4 \pmod 8$

L'ensemble des restes possibles d'un carré est très restreint. Cette propriété permet de créer une obstruction modulaire pour prouver qu'une équation diophantienne n'a pas de solution entière.

Exemple travaillé · 38

Démontre que l'équation $x^2 - 3y^2 = 3$ n'admet aucun couple de solutions dans $\mathbb{Z}^2$ .

1

On examine l'équation modulo $4$ . Comme $-3 \equiv 1 \pmod 4$ et $3 \equiv 3 \pmod 4$ , l'équation devient :

2

x^2 + y^2 \equiv 3 \pmod 4

3

Pour tous entiers $x$ et $y$ , $x^2 \in \{0, 1\} \pmod 4$ et $y^2 \in \{0, 1\} \pmod 4$ . Les sommes possibles de deux carrés modulo $4$ sont :

4

0+0 = 0, \quad 0+1 = 1, \quad 1+1 = 2 \implies (x^2 + y^2) \in \{0, 1, 2\} \pmod 4

5

Or, $3 \notin \{0, 1, 2\}$ . L'égalité est donc impossible modulo $4$ : l'équation n'a aucune solution dans $\mathbb{Z}^2$ .

Piège classique · 39

On considère dans $\mathbb{Z}^3$ l'équation $x^2 + y^2 = 8z^2 + 6$ . Un élève affirme qu'une étude de parité modulo $2$ suffit pour prouver l'inexistence de solutions. A-t-il raison ?

Attention

Penser qu'une simple étude de parité modulo $2$ permet de conclure à l'absence de solution d'une équation quadratique.

À la place : Modulo $2$ , l'équation donne $x^2 + y^2 \equiv 0 \pmod 2$ , ce qui est tout à fait possible (il suffit que $x$ et $y$ soient de même parité). L'obstruction n'apparaît que modulo $8$ : le membre de droite vérifie $8z^2 + 6 \equiv 6 \pmod 8$ , alors que les sommes possibles de deux carrés modulo $8$ sont $\{0, 1, 2, 4, 5\}$ , ensemble qui ne contient pas $6$ .

Exemple travaillé · 40

Démontre que pour tout entier naturel $n$ , l'équation $x^2 + 9 = 3^{2n+1}$ n'admet aucune solution dans $\mathbb{Z}$ .

1

On réduit le membre de gauche modulo $4$ . Comme $9 = 4 \times 2 + 1 \equiv 1 \pmod 4$ , on a :

2

x^2 + 9 \equiv x^2 + 1 \pmod 4

3

Comme $x^2 \in \{0, 1\} \pmod 4$ , le membre de gauche ne peut prendre que deux valeurs modulo $4$ : $0+1=1$ ou $1+1=2$ .

4

On étudie le membre de droite modulo $4$ : on a $3 \equiv -1 \pmod 4$ , donc :

5

3^{2n+1} \equiv (-1)^{2n+1} \pmod 4

6

L'exposant $2n+1$ est impair pour tout $n \in \mathbb{N}$ , d'où $(-1)^{2n+1} = -1 \equiv 3 \pmod 4$ .

7

Comme $\{1, 2\} \cap \{3\} = \emptyset$ , l'égalité est impossible modulo $4$ . L'équation n'a donc aucune solution entière.

Piège classique · 41

Pour montrer que l'équation $x^2 - 5y^2 = 3$ n'a pas de solution dans $\mathbb{Z}^2$ , quel modulo est-il le plus judicieux de choisir ?

Attention

Choisir modulo $3$ pour annuler le second membre sans simplifier les deux variables.

À la place : En choisissant modulo $5$ , le terme $5y^2$ s'annule complètement ( $5y^2 \equiv 0 \pmod 5$ ). L'équation devient $x^2 \equiv 3 \pmod 5$ . Or les carrés modulo $5$ sont $\{0^2, (\pm 1)^2, (\pm 2)^2\} = \{0, 1, 4\}$ . Comme $3 \notin \{0, 1, 4\}$ , l'impossibilité est immédiate.

Vérification · 42

Parmi les congruences suivantes, laquelle est IMPOSSIBLE dans $\mathbb{Z}$ ?

Remarque

Pour tout $x \in \mathbb{Z}$ , $x^2 \equiv 0$ ou $1 \pmod 4$ . Un carré n'est donc jamais congru à $2$ modulo $4$ . En revanche, $2^2 = 4 \equiv 4 \pmod 5$ et $1^2 = 1 \equiv 1 \pmod 8$ sont possibles.

Arithmétique — cours

Le cours

Théorème de la division euclidienne dans Z

Théorème de Bézout

Lemme de Gauss et divisibilité par un produit

Corollaire

Équations diophantiennes linéaires ax + by = c

Congruence modulo n et propriétés opératoires

Petit théorème de Fermat

Corollaire

Résidus quadratiques modulo 4 et modulo 8

Chapitres liés

Continuer sur Lumio