Arithmétique dans Z

L'arithmétique dans $\mathbb{Z}$ est un pilier des mathématiques, souvent perçue comme abstraite, mais ses applications sont partout, de la cryptographie (sécurité de tes messages en ligne) à la conception d'algorithmes. Ce chapitre te donne les outils fondamentaux pour manipuler les nombres entiers et comprendre leurs propriétés. C'est un domaine où la rigueur est essentielle, et chaque étape de ton raisonnement doit être justifiée.

L'intuition

Imagine que tu as un paquet de dattes. Si tu peux les partager équitablement entre tes amis, sans qu'il en reste, c'est que le nombre de dattes est un multiple du nombre d'amis. Si tu as 10 dattes et 2 amis, chacun reçoit 5 dattes, sans reste. Si tu as 10 dattes et 3 amis, chacun en reçoit 3 et il en reste 1. C'est ça, la divisibilité et la division euclidienne.

Le PGCD, c'est comme trouver la plus grande taille de sac dans laquelle tu peux ranger deux quantités différentes de dattes sans qu'il n'en reste. Si tu as 12 dattes et 18 dattes, tu peux les mettre dans des sacs de 6 dattes (2 sacs de 6 pour 12, 3 sacs de 6 pour 18). C'est la plus grande taille possible.

Les congruences, c'est penser aux nombres sur une horloge. Sur une horloge de 12 heures, 13h c'est 1h, 14h c'est 2h. On dit que 13 est congru à 1 modulo 12. C'est un moyen de simplifier les calculs avec des grands nombres en ne s'intéressant qu'à leur "position" sur un cycle.

Le cours

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

Définition

Soient $a$ et $b$ deux entiers relatifs. On dit que $a$ divise $b$ (ou $b$ est un multiple de $a$) 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|0$ (car $0 = a \cdot 0$).
2. Pour tout $a \in \mathbb{Z}$, $1|a$ et $-1|a$.
3. Pour tout $a \in \mathbb{Z}$, $a|a$ et $a|-a$.
4. Si $a|b$ et $b|c$, alors $a|c$ (transitivité).
5. Si $a|b$ et $a|c$, alors $a|(b+c)$ et $a|(b-c)$. Plus généralement, pour tous entiers $x, y$, $a|(bx+cy)$.
6. Si $a|b$ et $b|a$, alors $a = b$ ou $a = -b$. C'est-à-dire $|a| = |b|$.
7. Si $a|b$ et $b \neq 0$, alors $|a| \le |b|$.

II. Division euclidienne

Théorème

Soient $a$ un entier relatif et $b$ un entier naturel non nul. Il existe un unique couple d'entiers relatifs $(q, r)$ tel que $a = bq + r$ et $0 \le r < b$. $q$ est le quotient et $r$ est le reste de la division euclidienne de $a$ par $b$.

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

Définition

Soient $a$ et $b$ deux entiers relatifs non nuls.

• 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 se limiter aux entiers naturels.
2. $\text{PGCD}(a, b) = \text{PGCD}(b, a)$.
3. $\text{PGCD}(a, 0) = |a|$ pour $a \neq 0$.
4. Si $a|b$, alors $\text{PGCD}(a, b) = |a|$.
5. $\text{PGCD}(ka, kb) = |k| \text{PGCD}(a, b)$ pour $k \in \mathbb{Z}^*$.
6. $\text{PGCD}(a, b) \cdot \text{PPCM}(a, b) = |a \cdot b|$.

Algorithme d'Euclide

C'est la méthode la plus efficace pour trouver le PGCD de deux nombres. Elle est basée sur la propriété : $\text{PGCD}(a, b) = \text{PGCD}(b, r)$ où $r$ est le reste de la division euclidienne de $a$ par $b$.

1. 1

   Déterminer $\text{PGCD}(105, 30)$

2. 2

   1. Diviser le plus grand par le plus petit.

3. 3

   2. Remplacer le plus grand par le plus petit, et le plus petit par le reste.

4. 4

   3. Répéter l'opération.

5. 5

   4. Le dernier reste non nul est le PGCD.

Étape suivante

Nombres premiers entre eux

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

IV. Théorèmes fondamentaux

Théorème de Bézout

Soient $a$ et $b$ deux entiers relatifs non nuls. Il existe des entiers relatifs $u$ et $v$ tels que $au + bv = \text{PGCD}(a, b)$. De plus, $a$ et $b$ sont premiers entre eux si et seulement si il existe des entiers $u$ et $v$ tels que $au + bv = 1$.

La recherche de $u$ et $v$ se fait en "remontant" l'algorithme d'Euclide.

1. 1

   Trouver $u, v$ tels que $105u + 30v = \text{PGCD}(105, 30)$

2. 2

   1. Appliquer l'algorithme d'Euclide.

3. 3

   $30 = 2 \times 15 + 0$

4. 4

   $\text{PGCD}(105, 30) = 15$

5. 5

   2. Exprimer le PGCD comme combinaison linéaire des nombres précédents.

6. 6

   3. Identifier $u$ et $v$.

Étape suivante

Théorème de Gauss

Soient $a, b, c$ trois entiers relatifs non nuls. Si $a | bc$ et $\text{PGCD}(a, b) = 1$, alors $a | c$.

V. Nombres premiers

Définition

Un entier naturel $p > 1$ est un nombre premier s'il n'admet que deux diviseurs positifs : $1$ et lui-même.

Exemples : $2, 3, 5, 7, 11, 13, 17, 19, \dots$

Propriétés

1. Tout entier naturel $n > 1$ admet au moins un diviseur premier.
2. Tout entier naturel $n > 1$ peut s'écrire de manière unique (à l'ordre des facteurs près) comme un produit de nombres premiers : $n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$. C'est la décomposition en facteurs premiers.
3. Si $p$ est un nombre premier et $p | ab$, alors $p | a$ ou $p | b$. (C'est un cas particulier du théorème de Gauss).

VI. Congruences dans $\mathbb{Z}$

Définition

Soient $a, b$ des entiers relatifs et $n$ un entier naturel non nul. 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}$
   • $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}^*$.

Simplification et résolution de congruences

Si $ax \equiv ay \pmod{n}$, on ne peut pas toujours simplifier par $a$. On peut simplifier par $a$ si $\text{PGCD}(a, n) = 1$. Dans ce cas, $x \equiv y \pmod{n}$. Plus généralement, si $ax \equiv ay \pmod{n}$ et $\text{PGCD}(a, n) = d$, alors $x \equiv y \pmod{n/d}$.

Pour résoudre $ax \equiv b \pmod{n}$ :

1. Calculer $d = \text{PGCD}(a, n)$.
2. S'il $d \nmid b$, alors l'équation n'a pas de solution.
3. Si $d | b$, alors l'équation est équivalente à $\frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{n}{d}}$. On se retrouve avec une nouvelle congruence où $\text{PGCD}(\frac{a}{d}, \frac{n}{d}) = 1$.
4. On peut alors trouver l'inverse de $\frac{a}{d}$ modulo $\frac{n}{d}$ (en utilisant Bézout) pour isoler $x$.

Petit théorème de Fermat

Si $p$ est un nombre premier et $a$ un entier non divisible par $p$ (c'est-à-dire $\text{PGCD}(a, p) = 1$), 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}$.

Exemple résolu

Reprenons un extrait d'annale : "Soit $x$ un entier naturel tel que $10x \equiv 2 \pmod{19}$. 1- a) Vérifier que $10x+1 \equiv 1 \pmod{19}$ b) Montrer que $10^{18} \equiv 1 \pmod{19}$ 2- Soit $d$ le plus grand diviseur commun des deux nombres $18$ et $x+1$. a) Montrer que $10^d \equiv 1 \pmod{19}$ b) Montrer que $d=18$ c) En déduire que $x \equiv 17 \pmod{18}$"

Solution détaillée :

1- a) Vérifier que $10x+1 \equiv 1 \pmod{19}$ L'énoncé donne $10x \equiv 2 \pmod{19}$. On sait que $2 \equiv 20 \pmod{19}$ car $20 = 1 \times 19 + 1$, et $2 = 0 \times 19 + 2$. Non, ce n'est pas $20$. $20 = 1 \times 19 + 1$, donc $20 \equiv 1 \pmod{19}$. On a $10x \equiv 2 \pmod{19}$. On peut ajouter $1$ des deux côtés : $10x+1 \equiv 2+1 \pmod{19}$, donc $10x+1 \equiv 3 \pmod{19}$. L'énoncé demande $10x+1 \equiv 1 \pmod{19}$. Il y a une erreur dans l'énoncé ou ma compréhension. Reprenons l'énoncé original: "Soit x un nombre $entier_naturel$ tel que :10* =2 [19]". Il s'agit de $10^x \equiv 2 \pmod{19}$, pas $10x$.

Reprise de l'exemple avec $10^x \equiv 2 \pmod{19}$

1- a) Vérifier que $10^{x+1} \equiv 1 \pmod{19}$ On a $10^x \equiv 2 \pmod{19}$. Multiplions par $10$ des deux côtés : $10 \cdot 10^x \equiv 10 \cdot 2 \pmod{19}$ $10^{x+1} \equiv 20 \pmod{19}$ Or $20 = 1 \times 19 + 1$, donc $20 \equiv 1 \pmod{19}$. Ainsi, $10^{x+1} \equiv 1 \pmod{19}$.

1- b) Montrer que $10^{18} \equiv 1 \pmod{19}$ $19$ est un nombre premier. $10$ n'est pas divisible par $19$. D'après le petit théorème de Fermat, si $p$ est un nombre premier et $a$ un entier non divisible par $p$, alors $a^{p-1} \equiv 1 \pmod{p}$. Ici, $p=19$ et $a=10$. Donc $10^{19-1} \equiv 1 \pmod{19}$, ce qui donne $10^{18} \equiv 1 \pmod{19}$.

2- Soit $d = \text{PGCD}(18, x+1)$.

2- a) Montrer que $10^d \equiv 1 \pmod{19}$ On sait que $10^{x+1} \equiv 1 \pmod{19}$ (d'après 1-a) et $10^{18} \equiv 1 \pmod{19}$ (d'après 1-b). Soit $k$ l'ordre de $10$ modulo $19$. $k$ est le plus petit entier positif tel que $10^k \equiv 1 \pmod{19}$. On sait que $k$ divise tout entier $m$ tel que $10^m \equiv 1 \pmod{19}$. Donc $k | (x+1)$ et $k | 18$. Par définition, $d = \text{PGCD}(18, x+1)$. Puisque $k$ est un diviseur commun de $18$ et $x+1$, $k$ doit diviser leur plus grand commun diviseur, $d$. Donc $k | d$. Puisque $k | d$, il existe un entier $j$ tel que $d = kj$. Alors $10^d = 10^{kj} = (10^k)^j$. Comme $10^k \equiv 1 \pmod{19}$, on a $(10^k)^j \equiv 1^j \pmod{19}$. Donc $10^d \equiv 1 \pmod{19}$.

2- b) Montrer que $d=18$ On a $10^d \equiv 1 \pmod{19}$. On sait aussi que $d = \text{PGCD}(18, x+1)$, donc $d$ est un diviseur de $18$. Les diviseurs positifs de $18$ sont $1, 2, 3, 6, 9, 18$. Testons ces valeurs pour $d$:

• Si $d=1$, $10^1 = 10 \not\equiv 1 \pmod{19}$.
• Si $d=2$, $10^2 = 100$. $100 = 5 \times 19 + 5$, donc $100 \equiv 5 \pmod{19} \not\equiv 1 \pmod{19}$.
• Si $d=3$, $10^3 = 1000$. $1000 = 52 \times 19 + 12$, donc $1000 \equiv 12 \pmod{19} \not\equiv 1 \pmod{19}$.
• Si $d=6$, $10^6 = (10^3)^2 \equiv 12^2 \equiv 144 \pmod{19}$. $144 = 7 \times 19 + 11$, donc $144 \equiv 11 \pmod{19} \not\equiv 1 \pmod{19}$.
• Si $d=9$, $10^9 = 10^3 \cdot 10^6 \equiv 12 \cdot 11 \equiv 132 \pmod{19}$. $132 = 6 \times 19 + 18$, donc $132 \equiv 18 \pmod{19} \equiv -1 \pmod{19} \not\equiv 1 \pmod{19}$.
• Si $d=18$, $10^{18} \equiv 1 \pmod{19}$ (d'après 1-b). La seule valeur de $d$ parmi les diviseurs de $18$ qui satisfait $10^d \equiv 1 \pmod{19}$ est $d=18$. Donc $d=18$.

2- c) En déduire que $x \equiv 17 \pmod{18}$ On sait que $d = \text{PGCD}(18, x+1) = 18$. Puisque $18$ est le PGCD de $18$ et $x+1$, cela signifie que $18$ divise $x+1$. Donc $x+1 \equiv 0 \pmod{18}$. $x \equiv -1 \pmod{18}$. $x \equiv 17 \pmod{18}$ (car $-1+18 = 17$).

La méthode

La résolution d'exercices d'arithmétique suit souvent une logique précise. Voici les gestes types que tu dois maîtriser.

Geste 1 : Utiliser l'algorithme d'Euclide pour le PGCD et Bézout

1. 1

   Déterminer $\text{PGCD}(a, b)$ et trouver $u, v$ tels que $au + bv = \text{PGCD}(a, b)$

2. 2

   1. Effectuer les divisions euclidiennes successives.

3. 3

   $b = q_2 r_1 + r_2$

4. 4

   ...

5. 5

   $r_{n-1} = q_{n+1} r_n + 0$

6. 6

   Le PGCD est $r_n$.

7. 7

   2. Remonter l'algorithme pour exprimer le PGCD.

8. 8

   Substituer $r_{n-1}$ par son expression en fonction de $r_{n-3}$ et $r_{n-2}$.

9. 9

   Continuer jusqu'à exprimer $r_n$ en fonction de $a$ et $b$.

10. 10

    3. Identifier $u$ et $v$.

Étape suivante

Geste 2 : Manipuler les congruences

1. 1

   Résoudre une congruence linéaire $ax \equiv b \pmod{n}$

2. 2

   1. Calculer $d = \text{PGCD}(a, n)$.

3. 3

   2. Vérifier la condition d'existence des solutions.

4. 4

   3. Simplifier la congruence (si $d|b$).

5. 5

   Soit $a' = \frac{a}{d}$, $b' = \frac{b}{d}$, $n' = \frac{n}{d}$. La nouvelle congruence est $a'x \equiv b' \pmod{n'}$.

6. 6

   Maintenant, $\text{PGCD}(a', n') = 1$.

7. 7

   4. Trouver l'inverse de $a'$ modulo $n'$.

8. 8

   Alors $a'u \equiv 1 \pmod{n'}$, donc $u$ est l'inverse de $a'$ modulo $n'$.

9. 9

   5. Multiplier la congruence par l'inverse.

10. 10

    $x \equiv ub' \pmod{n'}$.

11. 11

    6. Écrire l'ensemble des solutions.

Étape suivante

Geste 3 : Utiliser le petit théorème de Fermat

1. 1

   Appliquer le petit théorème de Fermat

2. 2

   1. Identifier $p$ comme un nombre premier.

3. 3

   2. Vérifier que $a$ n'est pas un multiple de $p$.

4. 4

   3. Appliquer le théorème.

Étape suivante

Pièges classiques

1. Confusion entre $a|b$ et $a < b$ : La divisibilité n'implique pas une relation d'ordre simple, surtout avec les nombres négatifs. $5|-10$ est vrai, mais $5 \not< -10$.
2. Oublier la condition sur le reste de la division euclidienne : Le reste $r$ doit toujours vérifier $0 \le r < b$. Pour $a=-17, b=5$, le reste n'est pas $-2$.
3. Simplifier abusivement les congruences : $ax \equiv ay \pmod{n}$ n'implique $x \equiv y \pmod{n}$ que si $\text{PGCD}(a, n) = 1$. Contre-exemple : $2x \equiv 2 \pmod{4}$. Si on simplifie par $2$, on obtient $x \equiv 1 \pmod{4}$. Les solutions seraient $1, 5, 9, \dots$. Pourtant, $x=3$ est aussi une solution car $2 \times 3 = 6 \equiv 2 \pmod{4}$. La règle correcte est : $2x \equiv 2 \pmod{4} \implies x \equiv 1 \pmod{4/\text{PGCD}(2,4)}$, soit $x \equiv 1 \pmod{2}$. Les solutions sont $1, 3, 5, 7, \dots$.
4. Erreur dans l'application du théorème de Gauss : La condition $\text{PGCD}(a, b) = 1$ est cruciale. Si $a|bc$ et $\text{PGCD}(a, b) \neq 1$, tu ne peux pas conclure $a|c$. Contre-exemple : $6 | (4 \times 3)$, car $6|12$. Mais $\text{PGCD}(6, 4) = 2 \neq 1$. Et $6 \nmid 3$.
5. Ne pas vérifier que le module est premier pour Fermat : Le petit théorème de Fermat ne s'applique que si le module $p$ est un nombre premier.

Ce qui tombe à l'examen

L'arithmétique représente environ 7% du poids total de l'examen, ce qui est significatif. Les questions sont souvent regroupées dans un exercice dédié (généralement l'exercice 4 ou 5), avec un barème de 2.5 à 3.5 points.

Le format est celui d'un exercice indépendant, découpé en plusieurs sous-questions (a, b, c...). La progression est souvent guidée, chaque question s'appuyant sur la précédente.

Capacités évaluées :

• Application directe des connaissances (environ 40%) :
  • Calcul de PGCD/PPCM (souvent avec Euclide).
  • Application du petit théorème de Fermat.
  • Vérification de congruences.
  • Résolution d'équations diophantiennes simples (type $ax+by=c$) ou de congruences linéaires.
• Mobilisation en situation familière (environ 40%) :
  • Démonstrations utilisant Bézout ou Gauss.
  • Résolution de systèmes de congruences (théorème des restes chinois, même si non explicitement au programme, les exercices sont construits pour y mener).
  • Étude de propriétés de divisibilité dans des contextes légèrement plus complexes.
  • Utilisation de l'ordre d'un élément modulo $n$.
• Situations non familières (synthèse, environ 20%) :
  • Questions plus ouvertes nécessitant de combiner plusieurs théorèmes ou techniques.
  • Problèmes où l'arithmétique est un outil pour prouver une propriété plus générale.
  • Questions de type "montrer que l'équation n'admet pas de solution" en utilisant les propriétés de congruences.

Conseils pour l'examen :

• Rédaction rigoureuse : Chaque étape de ton raisonnement doit être justifiée par une définition, une propriété ou un théorème. Ne saute pas d'étapes.
• Maîtrise de l'algorithme d'Euclide : C'est la base de beaucoup de questions (PGCD, Bézout, inverses modulo $n$).
• Théorème de Bézout et Gauss : Comprends bien leurs conditions d'application et sache les utiliser pour des démonstrations.
• Congruences : Entraîne-toi à manipuler les propriétés (addition, multiplication, puissance) et à résoudre les équations. Le petit théorème de Fermat est très fréquent.
• Gestion du temps : L'exercice d'arithmétique est souvent l'un des plus courts. Vise la précision et la clarté pour maximiser tes points.

Les extraits d'annales montrent bien cette diversité :

• Le premier extrait teste Fermat, l'ordre d'un élément, et la déduction à partir du PGCD.
• Le deuxième extrait utilise l'algorithme d'Euclide pour trouver un inverse, puis manipule les congruences pour résoudre un système.
• Le troisième extrait combine Bézout, Fermat et les propriétés des congruences pour montrer l'absence de solution d'une équation diophantienne.

Prépare-toi à ces types de questions en t'entraînant régulièrement.