Arithmétique dans Z

L'intuition

L'arithmétique dans $\mathbb{Z}$ est l'étude des propriétés des nombres entiers. Tu as déjà manipulé ces nombres depuis toujours, mais ce chapitre formalise les règles qui les régissent. C'est comme si tu avais toujours joué au football, et maintenant on te donne les règles officielles du jeu.

Imagine que tu as un certain nombre de dattes et que tu veux les partager équitablement. Si tu as $10$ dattes et $2$ amis, chacun aura $5$ dattes, et il ne restera rien. On dit que $10$ est divisible par $2$. Si tu as $10$ dattes et $3$ amis, chacun aura $3$ dattes et il en restera $1$. C'est la division euclidienne.

Le Plus Grand Commun Diviseur (PGCD), c'est le plus grand nombre de paniers identiques que tu peux faire avec deux quantités de dattes différentes. Le Plus Petit Commun Multiple (PPCM), c'est le plus petit nombre de dattes que tu devrais avoir pour pouvoir faire des paniers de deux tailles différentes sans qu'il n'en reste.

Les congruences, c'est comme l'horloge. Quand il est $10$h, dans $3$h il sera $13$h, mais sur une horloge, il sera $1$h. On travaille "modulo $12$". C'est l'idée derrière les congruences.

Le cours

I. Divisibilité dans $\mathbb{Z}$

Définition 1 : Soient $a$ et $b$ deux entiers relatifs. On dit que $a$ divise $b$ (ou $b$ est un multiple de $a$, ou $a$ est un diviseur de $b$) s'il existe un entier relatif $k$ tel que $b = ak$. On note $a|b$.

Propriétés :

1. Pour tout $a \in \mathbb{Z}$, $a|a$ et $a|-a$.
2. Pour tout $a \in \mathbb{Z}$, $1|a$ et $-1|a$.
3. Pour tout $a \in \mathbb{Z}$, $a|0$.
4. Si $a|b$ et $b|c$, alors $a|c$ (transitivité).
5. Si $a|b$ et $a|c$, alors $a|(xb+yc)$ pour tous $x,y \in \mathbb{Z}$.
6. Si $a|b$ et $b \ne 0$, alors $|a| \le |b|$.
7. Si $a|b$ et $b|a$, alors $a = b$ ou $a = -b$ (c'est-à-dire $|a|=|b|$).

II. Division euclidienne dans $\mathbb{Z}$

Théorème 1 (Division euclidienne) : Soient $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$. Il existe un unique couple d'entiers $(q, r)$ tel que $a = bq + r$ et $0 \le r < b$. $q$ est le quotient et $r$ est le reste.

Exemple :

• Division de $17$ par $5$ : $17 = 5 \times 3 + 2$. Ici $a=17, b=5, q=3, r=2$.
• Division de $-17$ par $5$ : $-17 = 5 \times (-4) + 3$. Ici $a=-17, b=5, q=-4, r=3$. Le reste doit toujours être positif ou nul.

III. Plus Grand Commun Diviseur (PGCD) et Plus Petit Commun Multiple (PPCM)

Définition 2 : Soient $a, b \in \mathbb{Z}^*$.

• Le PGCD de $a$ et $b$, noté $\text{PGCD}(a, b)$ ou $a \wedge b$, est le plus grand des diviseurs communs positifs de $a$ et $b$.
• Le PPCM de $a$ et $b$, noté $\text{PPCM}(a, b)$ ou $a \vee b$, est le plus petit des multiples communs positifs de $a$ et $b$.

Propriétés :

1. $\text{PGCD}(a, b) = \text{PGCD}(|a|, |b|)$. On peut donc travailler avec des nombres positifs.
2. $\text{PGCD}(a, 0) = |a|$ pour $a \ne 0$.
3. Si $b|a$, alors $\text{PGCD}(a, b) = |b|$.
4. $\text{PGCD}(a, b) = \text{PGCD}(b, a-bq)$ pour tout $q \in \mathbb{Z}$. C'est la base de l'algorithme d'Euclide.
5. $\text{PGCD}(a, b) \times \text{PPCM}(a, b) = |a \times b|$.

Algorithme d'Euclide : Pour calculer le PGCD de deux entiers $a$ et $b$ ($a > b > 0$), on effectue une succession de divisions euclidiennes : $a = bq_1 + r_1$ $b = r_1q_2 + r_2$ $r_1 = r_2q_3 + r_3$ ... Le PGCD est le dernier reste non nul.

Exemple : Calculons $\text{PGCD}(195, 143)$. $195 = 143 \times 1 + 52$ $143 = 52 \times 2 + 39$ $52 = 39 \times 1 + 13$ $39 = 13 \times 3 + 0$ Le dernier reste non nul est $13$. Donc $\text{PGCD}(195, 143) = 13$.

1. 1

   Calculer PGCD(231, 105)

2. 2

   1. Diviser le plus grand par le plus petit

3. 3

   2. Diviser le diviseur par le reste

4. 4

   3. Le dernier reste non nul est le PGCD

Étape suivante

Définition 3 : Deux entiers $a$ et $b$ sont dits premiers entre eux si $\text{PGCD}(a, b) = 1$.

IV. Théorèmes de Bézout et de Gauss

Théorème 2 (Bézout) : Soient $a, b \in \mathbb{Z}^*$. $a$ et $b$ sont premiers entre eux si et seulement s'il existe des entiers relatifs $u$ et $v$ tels que $au + bv = 1$. Plus généralement, l'équation $ax + by = c$ admet des solutions entières si et seulement si $\text{PGCD}(a, b)$ divise $c$.

Démonstration (sens direct) : Soit $d = \text{PGCD}(a, b)$. L'ensemble $E = \{ax + by \mid x, y \in \mathbb{Z}\}$ contient des entiers positifs. Soit $d_0$ le plus petit entier positif de $E$. On montre que $d_0$ divise tous les éléments de $E$. On montre que $d_0$ divise $a$ et $b$. Puisque $d$ est le plus grand diviseur commun, $d_0 \le d$. On sait que $d$ divise $a$ et $b$, donc $d$ divise $ax+by$ pour tout $x,y$. En particulier, $d$ divise $d_0$. Puisque $d$ et $d_0$ sont positifs, $d \le d_0$. Donc $d_0 = d$. Ainsi, $\text{PGCD}(a, b)$ peut s'écrire sous la forme $au+bv$. Si $\text{PGCD}(a, b) = 1$, alors $au+bv=1$.

Démonstration (sens réciproque) : Supposons qu'il existe $u, v \in \mathbb{Z}$ tels que $au + bv = 1$. Soit $d = \text{PGCD}(a, b)$. Alors $d|a$ et $d|b$. Donc $d|(au+bv)$, ce qui signifie $d|1$. Puisque $d$ est un entier positif, $d=1$. Donc $a$ et $b$ sont premiers entre eux.

Théorème 3 (Gauss) : Soient $a, b, c \in \mathbb{Z}^*$. Si $a | bc$ et $\text{PGCD}(a, b) = 1$, alors $a | c$.

Démonstration : Puisque $\text{PGCD}(a, b) = 1$, d'après le théorème de Bézout, il existe $u, v \in \mathbb{Z}$ tels que $au + bv = 1$. Multiplions cette égalité par $c$ : $auc + bvc = c$. On sait que $a | bc$. Donc $bc = ak$ pour un certain entier $k$. En remplaçant $bc$ dans l'équation : $auc + (ak)v = c$. $a(uc + kv) = c$. Puisque $(uc + kv)$ est un entier, cela signifie que $a | c$.

V. Nombres premiers

Définition 4 : Un entier naturel $p \ge 2$ est dit premier s'il n'admet que deux diviseurs positifs : $1$ et lui-même.

Propriétés :

1. Tout entier naturel $n \ge 2$ admet au moins un diviseur premier.
2. Tout entier naturel $n \ge 2$ est soit premier, soit il peut s'écrire comme un produit de nombres premiers (décomposition en facteurs premiers). Cette décomposition est unique à l'ordre des facteurs près.
3. Il existe une infinité de nombres premiers.

Théorème 4 (Petit Théorème de Fermat) : Si $p$ est un nombre premier et $a$ est un entier non divisible par $p$, alors $a^{p-1} \equiv 1 \pmod{p}$. Si $p$ est un nombre premier, alors pour tout entier $a$, $a^p \equiv a \pmod{p}$.

VI. Congruences dans $\mathbb{Z}$

Définition 5 : Soient $a, b \in \mathbb{Z}$ et $n \in \mathbb{N}^*$. On dit que $a$ est congru à $b$ modulo $n$, noté $a \equiv b \pmod{n}$, si $n$ divise $(a-b)$. Cela signifie que $a$ et $b$ ont le même reste dans la division euclidienne par $n$.

Propriétés :

1. $a \equiv a \pmod{n}$ (réflexivité).
2. Si $a \equiv b \pmod{n}$, alors $b \equiv a \pmod{n}$ (symétrie).
3. Si $a \equiv b \pmod{n}$ et $b \equiv c \pmod{n}$, alors $a \equiv c \pmod{n}$ (transitivité).
4. Si $a \equiv b \pmod{n}$ et $c \equiv d \pmod{n}$, alors :
   • $a+c \equiv b+d \pmod{n}$
   • $ac \equiv bd \pmod{n}$
   • $a^k \equiv b^k \pmod{n}$ pour tout $k \in \mathbb{N}^*$.
5. Si $ac \equiv bc \pmod{n}$ et $\text{PGCD}(c, n) = 1$, alors $a \equiv b \pmod{n}$.

Inverse modulaire : Un entier $a$ admet un inverse modulo $n$ s'il existe un entier $x$ tel que $ax \equiv 1 \pmod{n}$. Cet inverse existe si et seulement si $\text{PGCD}(a, n) = 1$.

Exemple résolu

Reprenons un extrait d'annale : "1- En utilisant l'algorithme d'Euclide, déterminer l'entier $u\in\{12,22\}$ tel que : $10u\equiv1\ [23]$. 2- Soient $n$ un entier naturel et $q$ et $r$, respectivement, le quotient et le reste de la division euclidienne de $n$ par 10. a) Montrer que : $n\equiv 10(q+ur)\ [23]$. b) Montrer que : $23$ divise $n$ si et seulement si $23$ divise $(q+ur)$. 3- On considère dans $\mathbb{N}$ le système $(S) : \begin{cases} x\equiv1\ [23]\\ x\equiv2\ [10]\end{cases}$. a) Montrer que si $x$ est une solution du système $(S)$ alors il existe $g \in \mathbb{N}$ tel que $x=10g+2$ et $23$ divise $(g+7)$. b) Résoudre dans $\mathbb{N}$ le système $(S)$."

Solution :

1. Déterminer $u \in \{12, 22\}$ tel que $10u \equiv 1 \pmod{23}$. On cherche l'inverse de $10$ modulo $23$. On utilise l'algorithme d'Euclide pour trouver $\text{PGCD}(10, 23)$. $23 = 2 \times 10 + 3$ $10 = 3 \times 3 + 1$ $3 = 3 \times 1 + 0$ Le PGCD est $1$. Donc $10$ et $23$ sont premiers entre eux, et $10$ admet un inverse modulo $23$. On remonte l'algorithme pour trouver $u$ et $v$ tels que $10u + 23v = 1$. $1 = 10 - 3 \times 3$ $1 = 10 - (23 - 2 \times 10) \times 3$ $1 = 10 - 3 \times 23 + 6 \times 10$ $1 = 7 \times 10 - 3 \times 23$ Donc $7 \times 10 \equiv 1 \pmod{23}$. L'entier $u=7$ est un inverse de $10$ modulo $23$. On nous demande $u \in \{12, 22\}$. On sait que $7 \equiv 7 \pmod{23}$. $7+23 = 30 \pmod{23}$. $7-23 = -16 \pmod{23}$. On cherche un $u$ dans l'intervalle donné. $10u \equiv 1 \pmod{23}$. Si $u=12$, $10 \times 12 = 120$. $120 = 5 \times 23 + 5$. Donc $120 \equiv 5 \pmod{23}$. Ce n'est pas $1$. Si $u=22$, $10 \times 22 = 220$. $220 = 9 \times 23 + 13$. Donc $220 \equiv 13 \pmod{23}$. Ce n'est pas $1$. Il y a une erreur dans l'énoncé de l'annale ou dans ma compréhension de l'intervalle. L'inverse est $7 \pmod{23}$. Si l'énoncé voulait dire $u \in \{12, 22\}$ comme des valeurs possibles pour l'inverse, alors il n'y en a pas. Reprenons la question: "déterminer l'entier $u\in\{12,22\}$ tel que : $10u\equiv1\ [23]$". L'inverse de $10$ modulo $23$ est $7$. Tous les inverses sont de la forme $7 + 23k$. Pour $k=0$, $u=7$. Pour $k=1$, $u=30$. Pour $k=-1$, $u=-16$. Aucun de ces $u$ n'est dans $\{12, 22\}$. Il est possible que l'énoncé ait une faute de frappe et que l'intervalle soit par exemple $\{7, 30\}$ ou que $u$ soit un $x$ dans l'équation $10x \equiv 1 \pmod{23}$. Si on suppose que l'énoncé attendait $u=7$, alors on a trouvé. Si l'énoncé voulait dire trouver $u$ dans l'ensemble des restes modulo $23$, alors $u=7$. Dans un examen, si tu rencontres ce genre de situation, tu dois indiquer que l'inverse est $7$ et que les valeurs proposées ne conviennent pas, ou qu'il y a une erreur dans l'énoncé. Pour la suite de l'exercice, je vais utiliser $u=7$.

2. Soient $n$ un entier naturel, $q$ et $r$ le quotient et le reste de la division euclidienne de $n$ par $10$. a) Montrer que $n \equiv 10(q+ur) \pmod{23}$. On a $n = 10q + r$ avec $0 \le r < 10$. On sait que $10u \equiv 1 \pmod{23}$. Multiplions par $r$ : $10ur \equiv r \pmod{23}$. Donc $n = 10q + r \equiv 10q + 10ur \pmod{23}$. $n \equiv 10(q+ur) \pmod{23}$.

b) Montrer que $23$ divise $n$ si et seulement si $23$ divise $(q+ur)$. On a $n \equiv 10(q+ur) \pmod{23}$. Si $23$ divise $n$, alors $n \equiv 0 \pmod{23}$. Donc $10(q+ur) \equiv 0 \pmod{23}$. Puisque $\text{PGCD}(10, 23) = 1$ (on l'a montré en 1.), on peut simplifier par $10$. Donc $q+ur \equiv 0 \pmod{23}$, ce qui signifie que $23$ divise $(q+ur)$. Réciproquement, si $23$ divise $(q+ur)$, alors $q+ur \equiv 0 \pmod{23}$. Donc $10(q+ur) \equiv 10 \times 0 \pmod{23}$, soit $10(q+ur) \equiv 0 \pmod{23}$. Puisque $n \equiv 10(q+ur) \pmod{23}$, on a $n \equiv 0 \pmod{23}$, ce qui signifie que $23$ divise $n$. D'où l'équivalence.

3. Résoudre dans $\mathbb{N}$ le système $(S) : \begin{cases} x\equiv1\ [23]\\ x\equiv2\ [10]\end{cases}$. a) Montrer que si $x$ est une solution du système $(S)$ alors il existe $g \in \mathbb{N}$ tel que $x=10g+2$ et $23$ divise $(g+7)$. La deuxième congruence $x \equiv 2 \pmod{10}$ signifie que $x$ s'écrit sous la forme $10g+2$ pour un certain entier $g$. Puisque $x \in \mathbb{N}$, et $x \equiv 2 \pmod{10}$, $x$ est au moins $2$. Donc $10g+2 \ge 0$, ce qui implique $10g \ge -2$, donc $g \ge -0.2$. Puisque $g$ est un entier, $g \ge 0$. Donc $g \in \mathbb{N}$. Maintenant, utilisons la première congruence : $x \equiv 1 \pmod{23}$. On remplace $x$ par $10g+2$ : $10g+2 \equiv 1 \pmod{23}$ $10g \equiv 1-2 \pmod{23}$ $10g \equiv -1 \pmod{23}$ On sait que $10u \equiv 1 \pmod{23}$, avec $u=7$. Multiplions la congruence par $7$ : $7 \times 10g \equiv 7 \times (-1) \pmod{23}$ $70g \equiv -7 \pmod{23}$ On sait que $70 = 3 \times 23 + 1$, donc $70 \equiv 1 \pmod{23}$. $1g \equiv -7 \pmod{23}$ $g \equiv -7 \pmod{23}$ $g \equiv -7+23 \pmod{23}$ $g \equiv 16 \pmod{23}$ Donc $23$ divise $(g-16)$. L'énoncé demande de montrer que $23$ divise $(g+7)$. On a $g \equiv -7 \pmod{23}$, ce qui est équivalent à $g+7 \equiv 0 \pmod{23}$. Donc $23$ divise $(g+7)$.

b) Résoudre dans $\mathbb{N}$ le système $(S)$. D'après la question précédente, $g \equiv 16 \pmod{23}$. Donc $g = 23k + 16$ pour un certain entier $k$. Puisque $g \in \mathbb{N}$, $23k+16 \ge 0$, donc $23k \ge -16$, $k \ge -16/23$. Puisque $k$ est un entier, $k \ge 0$. On a $x = 10g+2$. $x = 10(23k+16)+2$ $x = 230k + 160 + 2$ $x = 230k + 162$. L'ensemble des solutions dans $\mathbb{N}$ est $S = \{230k + 162 \mid k \in \mathbb{N}\}$.

La méthode

Pour aborder les exercices d'arithmétique, suis ces étapes :

1. Identifier les notions clés : Divisibilité, division euclidienne, PGCD, PPCM, Bézout, Gauss, nombres premiers, congruences. Chaque problème utilise une ou plusieurs de ces notions.
2. Traduire l'énoncé en langage mathématique : Par exemple, "$a$ divise $b$" devient $b=ak$, "$a$ est congru à $b$ modulo $n$" devient $a \equiv b \pmod{n}$ ou $n|(a-b)$.
3. Appliquer les définitions et théorèmes :
   • PGCD : Utilise l'algorithme d'Euclide pour le calculer.
   • Bézout : Si tu dois montrer que deux nombres sont premiers entre eux, cherche $u,v$ tels que $au+bv=1$. Si tu as une équation diophantienne $ax+by=c$, vérifie si $\text{PGCD}(a,b)$ divise $c$.
   • Gauss : Si tu as $a|bc$ et $\text{PGCD}(a,b)=1$, tu peux en déduire $a|c$. C'est très utile pour simplifier des congruences.
   • Congruences : Manipule-les comme des égalités (addition, multiplication, puissance) mais sois vigilant lors de la division (il faut que le nombre par lequel tu divises soit premier avec le module).
   • Nombres premiers : Utilise le petit théorème de Fermat ou la décomposition en facteurs premiers.
4. Rédiger clairement chaque étape : Chaque déduction doit être justifiée par une définition, une propriété ou un théorème. C'est essentiel pour le barème.

1. 1

   Résoudre l'équation $143x - 195y = 52$ dans $\mathbb{Z}^2$.

2. 2

   1. Calculer $\text{PGCD}(143, 195)$ avec l'algorithme d'Euclide.

3. 3

   2. Vérifier si l'équation admet des solutions.

4. 4

   3. Simplifier l'équation en divisant par le PGCD.

5. 5

   4. Trouver une solution particulière $(x_0, y_0)$ pour l'équation simplifiée.

6. 6

   5. Écrire la solution générale.

7. 7

   6. Donner l'ensemble des solutions.

Étape suivante

Pièges classiques

1. Le reste de la division euclidienne : Il doit toujours être positif ou nul. Pour $a=bq+r$, on a $0 \le r < |b|$. Si $b$ est négatif, on prend $|b|$. Exemple : Division de $-20$ par $7$. Le reste n'est pas $-6$. On écrit $-20 = 7 \times (-3) + 1$, le reste est $1$.
2. Simplification dans les congruences : Tu ne peux diviser par un nombre $c$ dans $ac \equiv bc \pmod{n}$ que si $\text{PGCD}(c, n) = 1$. Sinon, il faut diviser le module par $\text{PGCD}(c, n)$. Exemple : $2x \equiv 2 \pmod{4}$. Si tu divises par $2$, tu obtiens $x \equiv 1 \pmod{4}$. Or, $x=3$ est aussi une solution ($2 \times 3 = 6 \equiv 2 \pmod{4}$). La bonne simplification est $x \equiv 1 \pmod{2}$.
3. Théorème de Gauss : N'oublie pas la condition $\text{PGCD}(a, b) = 1$. Sans cette condition, le théorème ne s'applique pas. Exemple : $6 | (4 \times 3)$. Ici $a=6, b=4, c=3$. $\text{PGCD}(6, 4) = 2 \ne 1$. Et $6$ ne divise pas $3$.
4. Équations diophantiennes $ax+by=c$ : La condition d'existence de solutions est que $\text{PGCD}(a,b)$ divise $c$. Si cette condition n'est pas remplie, il n'y a pas de solution.

Ce qui tombe à l'examen

L'arithmétique représente environ $7\%$ du poids total de l'examen, soit environ $3$ points sur $20$. Les questions sont souvent intégrées dans un exercice plus large ou constituent un exercice indépendant de $3$ à $4$ points.

Formats de questions réels :

• Calcul de PGCD et PPCM : Souvent via l'algorithme d'Euclide.
• Équations diophantiennes : Résolution d'équations de type $ax+by=c$ dans $\mathbb{Z}^2$. Cela implique souvent l'utilisation de Bézout et Gauss.
• Congruences :
  • Calculs modulaires (trouver un reste, prouver une congruence).
  • Résolution d'équations de type $ax \equiv b \pmod{n}$.
  • Résolution de systèmes de congruences (Théorème des restes chinois, bien que non explicitement au programme, les méthodes de substitution sont suffisantes).
  • Application du Petit Théorème de Fermat.
• Nombres premiers : Questions sur la divisibilité, la primarité, ou l'utilisation de la décomposition en facteurs premiers.
• Démonstrations : Appliquer les théorèmes de Bézout et Gauss pour prouver des propriétés de divisibilité.

Attendus de correction :

• Rigueur : Chaque étape de calcul ou de raisonnement doit être justifiée.
• Clarté : La rédaction doit être logique et facile à suivre.
• Maîtrise des définitions et théorèmes : Utilise les termes exacts et cite les théorèmes lorsque tu les appliques.
• Calculs exacts : Une erreur de calcul peut entraîner la perte de points même si la méthode est bonne.