Arithmétique dans ℤ

Vue d'ensemble

L'arithmétique dans ℤ est le chapitre où la rigueur logique rencontre la beauté la plus classique des mathématiques : tu y apprends à manier la divisibilité, la division euclidienne, le PGCD, les nombres premiers et les congruences avec la même précision que pour les ε de l'analyse. Cette fiche regroupe les 9 théorèmes incontournables, les 4 démonstrations à savoir refaire (algorithme d'Euclide, Bachet-Bézout, Gauss, infinité des premiers) et les pièges classiques qui font perdre des points en DS comme aux concours.

Au programme MPSI (officiel) — Arithmétique dans ℤ : divisibilité, division euclidienne, PGCD (algorithme d'Euclide), PPCM, théorème de Bachet-Bézout, théorème de Gauss, nombres premiers entre eux, nombres premiers, théorème fondamental de l'arithmétique (décomposition primaire), congruences modulo n, anneau ℤ/nℤ, petit théorème de Fermat.

Prérequis

Récurrence (simple, double, forte) et raisonnement par l'absurde
Quantificateurs $\forall, \exists, \exists!$ et négation logique
Structure d'anneau de $(Z, +, \times)$ et propriétés élémentaires
Manipulation des inégalités larges et de la valeur absolue dans $Z$

🎯 Accompagnement Majorant

Tu confonds PGCD, PPCM, Bézout et Gauss après deux semaines ? C'est le chapitre où l'ordre logique des théorèmes (Euclide → Bézout → Gauss → Fermat) bloque 1 élève de MPSI sur 2 — alors qu'une fois compris, il devient le plus facile de l'année. Nos mentors alumni X · Centrale · Mines t'apprennent à le restituer dans le bon ordre, avec exos type DS sur tes propres copies.

Trouver un mentor MPSI →

1. Divisibilité dans ℤ

Définition 1.1 — Divisibilité

Soient $a, b \in Z$ . On dit que $a$ divise $b$ , et on note $a ∣ b$ , s'il existe $k \in Z$ tel que $b = k a$ . On dit alors aussi que $b$ est un multiple de $a$ , ou que $a$ est un diviseur de $b$ . L'ensemble des diviseurs de $b$ dans ℤ est noté $D (b)$ , celui des multiples est $b Z = {k b, k \in Z}$ .

📝 Cas particuliers. Pour tout

a \in Z

1 ∣ a

a ∣ a

a ∣ 0

. En revanche,

0 ∣ a

seulement si

a = 0

. Tout entier divise

0

, mais

0

ne divise que

0

Proposition 1.2 — Propriétés élémentaires

Pour tous $a, b, c \in Z$ :

Transitivité : si $a ∣ b$ et $b ∣ c$ , alors $a ∣ c$ .
Combinaison linéaire : si $a ∣ b$ et $a ∣ c$ , alors pour tous $u, v \in Z$ , $a ∣ (u b + v c)$ .
Antisymétrie au signe près : si $a ∣ b$ et $b ∣ a$ , alors $a = \pm b$ .
Encadrement : si $a ∣ b$ et $b \neq = 0$ , alors $∣ a ∣ \leq ∣ b ∣$ .

⚠ Piège #1 — La divisibilité n'est PAS une relation d'ordre sur ℤ. Sur

Z

, elle n'est qu'un préordre : on a

2 ∣ - 2

- 2 ∣ 2

sans que

2 = - 2

. Pour récupérer une relation d'ordre, il faut restreindre à

N

— c'est la convention implicite quand on parle de « plus petit » diviseur ou multiple. À l'écrit, précise toujours « dans

N

» si tu invoques l'ordre.

Définition 1.3 — Division euclidienne dans ℤ

Pour tout $a \in Z$ et tout $b \in N^{*}$ , il existe un unique couple $(q, r) \in Z \times Z$ tel que :

a = b q + r avec 0 \leq r < b .

L'entier $q$ est le quotient, $r$ le reste de la division euclidienne de $a$ par $b$ . Notation : $q = a \div b$ , $r = a mod b$ .

Théorème 1.4 — Caractérisation par le reste

Soient $a \in Z$ et $b \in N^{*}$ . Alors $b ∣ a$ si et seulement si le reste de la division euclidienne de $a$ par $b$ est nul ( $r = 0$ ).

💡 Exemple — Division avec a < 0. Pour

a = - 17

b = 5

: on n'écrit PAS

q = - 3, r = - 2

(le reste doit être positif). On a

- 17 = 5 \times (- 4) + 3

donc

q = - 4

r = 3

. Vérifie toujours

0 \leq r < b

2. PGCD, PPCM et algorithme d'Euclide

Définition 2.1 — PGCD

Soient $a, b \in Z$ non tous deux nuls. Le plus grand commun diviseur de $a$ et $b$ , noté $a \land b$ (ou $pgcd (a, b)$ ), est le plus grand entier positif qui divise à la fois $a$ et $b$ :

a \land b = max {d \in N^{*}, d ∣ a et d ∣ b} .

Par convention, $0 \land 0 = 0$ et $a \land 0 = ∣ a ∣$ .

Définition 2.2 — PPCM

Soient $a, b \in Z^{*}$ . Le plus petit commun multiple de $a$ et $b$ , noté $a \lor b$ (ou $ppcm (a, b)$ ), est le plus petit entier strictement positif multiple à la fois de $a$ et de $b$ :

a \lor b = min {m \in N^{*}, a ∣ m et b ∣ m} .

Théorème 2.3 — Algorithme d'Euclide ★ À savoir démontrer

Soient $a \in Z$ et $b \in N^{*}$ . Soit $r$ le reste de la division euclidienne de $a$ par $b$ . Alors :

a \land b = b \land r .

En itérant cette identité jusqu'à obtenir un reste nul, on calcule le PGCD en un nombre fini d'étapes : c'est l'algorithme d'Euclide.

Démonstration (égalité des ensembles de diviseurs communs)

Écrivons la division euclidienne : $a = b q + r$ avec $0 \leq r < b$ . On montre que l'ensemble des diviseurs communs de $a$ et $b$ est exactement celui des diviseurs communs de $b$ et $r$ — ce qui force l'égalité des plus grands.

Sens direct. Soit $d \in N^{*}$ tel que $d ∣ a$ et $d ∣ b$ . Alors $d ∣ (a - b q) = r$ par combinaison linéaire (Prop. 1.2), donc $d ∣ b$ et $d ∣ r$ .

Sens réciproque. Soit $d \in N^{*}$ tel que $d ∣ b$ et $d ∣ r$ . Alors $d ∣ (b q + r) = a$ par combinaison linéaire, donc $d ∣ a$ et $d ∣ b$ .

Les diviseurs communs de $(a, b)$ et de $(b, r)$ sont identiques ; le plus grand est donc le même : $a \land b = b \land r$ .

Terminaison. En posant $r_{0} = a$ , $r_{1} = b$ , puis $r_{n + 1}$ = reste de la division de $r_{n - 1}$ par $r_{n}$ , la suite $(r_{n})$ est une suite strictement décroissante d'entiers positifs : elle s'annule en un nombre fini d'étapes. Le dernier reste non nul est $a \land b$ .

📐 Méthode-type — Calcul de PGCD par algorithme d'Euclide. Pour calculer

a \land b

avec

a \geq b > 0

Effectuer la division euclidienne $a = b q_{1} + r_{1}$ avec $0 \leq r_{1} < b$ .
Si $r_{1} = 0$ , alors $a \land b = b$ . STOP.
Sinon, remplacer $(a, b)$ par $(b, r_{1})$ et recommencer à l'étape 1.
Le PGCD est le dernier reste non nul de la chaîne.

Exemple chiffré. Calculons

252 \land 105

252 = 2 \times 105 + 42, 105 = 2 \times 42 + 21, 42 = 2 \times 21 + 0.

Le dernier reste non nul est

21

, donc

252 \land 105 = 21

. C'est mécanique, rapide, et ça marche toujours — y compris quand la décomposition en facteurs premiers serait pénible.

Théorème 2.4 — Théorème de Bachet-Bézout ★ À savoir démontrer

Soient $a, b \in Z$ non tous deux nuls et $d = a \land b$ . Alors il existe $u, v \in Z$ tels que :

a u + b v = d .

Les entiers $u, v$ sont appelés coefficients de Bézout. Ils ne sont pas uniques, mais une solution particulière peut toujours se calculer par l'algorithme d'Euclide étendu.

Démonstration (par l'algorithme d'Euclide étendu, par récurrence sur le nombre d'étapes)

On note $(r_{n})$ la suite des restes de l'algorithme d'Euclide appliqué à $(a, b)$ : $r_{0} = a$ , $r_{1} = b$ , $r_{n + 1}$ = reste de la division de $r_{n - 1}$ par $r_{n}$ . Soit $N$ l'indice du dernier reste non nul, on a $r_{N} = a \land b = d$ .

Idée. Démontrer par récurrence forte sur $n \in {0, \dots, N}$ que chaque $r_{n}$ s'écrit $r_{n} = u_{n} a + v_{n} b$ avec $u_{n}, v_{n} \in Z$ — en particulier $d = r_{N} = u_{N} a + v_{N} b$ , CQFD.

Initialisation. $r_{0} = a = 1 \cdot a + 0 \cdot b$ (prendre $(u_{0}, v_{0}) = (1, 0)$ ) ; $r_{1} = b = 0 \cdot a + 1 \cdot b$ (prendre $(u_{1}, v_{1}) = (0, 1)$ ).

Hérédité. Supposons que pour deux indices consécutifs $n - 1$ et $n$ , on ait $r_{n - 1} = u_{n - 1} a + v_{n - 1} b$ et $r_{n} = u_{n} a + v_{n} b$ . La division euclidienne donne $r_{n - 1} = r_{n} q_{n} + r_{n + 1}$ , donc :

r_{n + 1} = r_{n - 1} - q_{n} r_{n} = (u_{n - 1} - q_{n} u_{n}) a + (v_{n - 1} - q_{n} v_{n}) b .

En posant $u_{n + 1} = u_{n - 1} - q_{n} u_{n}$ et $v_{n + 1} = v_{n - 1} - q_{n} v_{n}$ (tous deux entiers), on a bien $r_{n + 1} = u_{n + 1} a + v_{n + 1} b$ . Par récurrence, $d = r_{N} = u_{N} a + v_{N} b$ .

🧑‍🏫 Décortique Bézout avec un mentor

Bachet-Bézout est LA démo qui apparaît partout en arithmétique. L'algorithme d'Euclide étendu, c'est aussi la compétence concours : RSA, équations diophantiennes, classes inversibles dans ℤ/nℤ — tout passe par là. En 1 séance avec un mentor Majorant alumni de l'X, tu maîtrises l'algorithme étendu et tu sais l'appliquer sur un cas chiffré en 2 minutes.

Réserver une séance Bézout →

Proposition 2.5 — Caractérisation du PGCD

Soient $a, b \in Z$ non tous deux nuls. L'entier $d \in N^{*}$ est le PGCD de $a$ et $b$ si et seulement si :

$d ∣ a$ et $d ∣ b$ ( $d$ est un diviseur commun),
tout diviseur commun $d^{'}$ de $a$ et $b$ vérifie $d^{'} ∣ d$ ( $d$ est le plus grand au sens de la divisibilité).

Proposition 2.6 — Lien PGCD-PPCM

Pour tous $a, b \in Z^{*}$ :

(a \land b) \cdot (a \lor b) = ∣ a b ∣.

Conséquence pratique : on calcule presque toujours le PPCM via le PGCD (Euclide est rapide).

3. Nombres premiers entre eux et théorème de Gauss

Définition 3.1 — Premiers entre eux

Deux entiers $a, b \in Z$ (non tous deux nuls) sont dits premiers entre eux (ou copremiers) si $a \land b = 1$ .

Théorème 3.2 — Caractérisation de Bézout

Soient $a, b \in Z$ . Alors $a$ et $b$ sont premiers entre eux si et seulement si il existe $u, v \in Z$ tels que :

a u + b v = 1.

Sens direct : par Bachet-Bézout avec $d = 1$ . Sens réciproque : si $a u + b v = 1$ et $d ∣ a, d ∣ b$ , alors $d ∣ 1$ donc $d = 1$ .

Théorème 3.3 — Théorème de Gauss ★ À savoir démontrer

Soient $a, b, c \in Z$ . Si $a ∣ b c$ et $a \land b = 1$ , alors :

a ∣ c .

Démonstration (à partir de Bézout)

Supposons $a ∣ b c$ et $a \land b = 1$ . Par le théorème de Bachet-Bézout (caractérisation des copremiers), il existe $u, v \in Z$ tels que :

a u + b v = 1.

Multiplions cette identité par $c$ :

a u c + b v c = c, soit c = a (u c) + (b c) v .

Or $a ∣ a (u c)$ trivialement, et $a ∣ b c$ par hypothèse, donc $a ∣ (b c) v$ . Par combinaison linéaire (Prop. 1.2), $a$ divise leur somme, c'est-à-dire $a ∣ c$ . CQFD.

⚠ Piège #2 — L'hypothèse de coprimalité est INDISPENSABLE. Sans

a \land b = 1

, Gauss est faux : prends

a = 6

b = 4

c = 9

. Alors

b c = 36

6 ∣ 36

, mais

6 ∤ 9

. La raison :

6 \land 4 = 2 \neq = 1

. Vérifie TOUJOURS la coprimalité avant d'invoquer Gauss — c'est l'erreur la plus sanctionnée du chapitre.

Corollaire 3.4 — Variante utile de Gauss

Si $a ∣ c$ , $b ∣ c$ et $a \land b = 1$ , alors $a b ∣ c$ .

Proposition 3.5 — Lemme d'Euclide (cas premier)

Si $p$ est un nombre premier et $p ∣ a b$ , alors $p ∣ a$ ou $p ∣ b$ .

Justification : si $p ∤ a$ , comme $p$ est premier ses seuls diviseurs positifs sont $1$ et $p$ , donc $p \land a = 1$ . Par Gauss, $p ∣ b$ .

📐 Méthode-type — Équation diophantienne $a x + b y = c$ .

Existence : solutions ssi $(a \land b) ∣ c$ .
Solution particulière : calcule $a \land b$ par Euclide, remonte pour obtenir $u_{0}, v_{0}$ tels que $a u_{0} + b v_{0} = a \land b$ , puis multiplie par $c / (a \land b)$ pour avoir $(x_{0}, y_{0})$ .
Solution générale : pose $a^{'} = a / (a \land b)$ , $b^{'} = b / (a \land b)$ . Les solutions sont ${(x_{0} + k b^{'}, y_{0} - k a^{'}), k \in Z}$ (preuve par Gauss : si $a^{'} (x - x_{0}) = - b^{'} (y - y_{0})$ avec $a^{'} \land b^{'} = 1$ , alors $b^{'} ∣ (x - x_{0})$ ).

4. Nombres premiers

Définition 4.1 — Nombre premier

Un entier $p \in N$ est premier si $p \geq 2$ et si ses seuls diviseurs positifs sont $1$ et $p$ . On note $P$ l'ensemble des nombres premiers : $P = {2, 3, 5, 7, 11, 13, 17, 19, 23, \dots}$ .

📝 Pourquoi exclure 0 et 1 ?

0

a une infinité de diviseurs.

1

n'a qu'un seul diviseur positif — l'exclure préserve l'unicité de la décomposition primaire (sinon

6 = 1 \times 2 \times 3 = 1 \times 1 \times 2 \times 3

…).

Théorème 4.2 — Infinité des nombres premiers (Euclide) ★ À savoir démontrer

L'ensemble $P$ des nombres premiers est infini.

Démonstration (par l'absurde — preuve d'Euclide, IIIe siècle av. J.-C.)

Supposons par l'absurde que $P$ soit fini. Notons alors $P = {p_{1}, p_{2}, \dots, p_{n}}$ la liste exhaustive des nombres premiers. Considérons l'entier :

N = p_{1} p_{2} \dots p_{n} + 1.

On a $N \geq 2$ (puisque $p_{1} p_{2} \dots p_{n} \geq 2$ ). Tout entier $\geq 2$ admet au moins un diviseur premier (admis ici, mais démontrable par récurrence forte ou descente infinie). Donc il existe $p_{i} \in P$ tel que $p_{i} ∣ N$ .

Or $p_{i} ∣ p_{1} p_{2} \dots p_{n}$ (trivialement, puisque $p_{i}$ figure dans le produit). Par combinaison linéaire :

p_{i} ∣ N - p_{1} p_{2} \dots p_{n} = 1.

Donc $p_{i} ∣ 1$ , ce qui force $p_{i} = 1$ . Contradiction, car $p_{i} \geq 2$ en tant que nombre premier.

L'hypothèse « $P$ fini » est donc absurde : $P$ est infini.

Théorème 4.3 — Théorème fondamental de l'arithmétique

Tout entier $n \in N$ , $n \geq 2$ , s'écrit de manière unique (à l'ordre des facteurs près) sous la forme :

n = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{k}^{α_{k}},

où $p_{1} < p_{2} < \dots < p_{k}$ sont des nombres premiers deux à deux distincts et $α_{1}, α_{2}, \dots, α_{k} \in N^{*}$ . C'est la décomposition primaire de $n$ .

Idée de preuve : l'existence s'obtient par récurrence forte sur $n$ (si $n$ est premier, terminé ; sinon $n = a b$ avec $2 \leq a, b < n$ , on applique l'hypothèse à $a$ et $b$ ). L'unicité s'obtient par le lemme d'Euclide (Prop. 3.5).

💡 Exemple — Décomposition primaire.

360 = 2^{3} \times 3^{2} \times 5

;

2024 = 2^{3} \times 11 \times 23

;

2025 = 3^{4} \times 5^{2}

. La décomposition primaire est l'outil de référence pour calculer PGCD et PPCM par min/max des exposants :

a \land b = p \prod p^{m i n (α_{p}, β_{p})}, a \lor b = p \prod p^{m a x (α_{p}, β_{p})},

où

p

parcourt l'union des facteurs premiers de

a

b

, et

α_{p}, β_{p}

sont les exposants respectifs (éventuellement nuls).

Proposition 4.4 — Crible d'Ératosthène (test de primalité)

Un entier $n \geq 2$ est premier si et seulement si il n'admet aucun diviseur premier $p$ vérifiant $p \leq n$ .

Justification : si $n = a b$ avec $2 \leq a \leq b$ , alors $a \leq n$ (sinon $a b > n$ ). Tester la divisibilité par les premiers jusqu'à $n$ suffit donc à conclure.

5. Congruences modulo n et anneau ℤ/nℤ

Définition 5.1 — Congruence modulo n

Soit $n \in N^{*}$ . Pour $a, b \in Z$ , on dit que $a$ est congru à $b$ modulo $n$ , et on note $a \equiv b [n]$ , si :

n ∣ (a - b), c.- \overset{a}{ˋ} -d. \exists k \in Z, a - b = k n .

De manière équivalente : $a$ et $b$ ont le même reste dans la division euclidienne par $n$ .

Proposition 5.2 — La congruence est une relation d'équivalence

Pour tout $n \in N^{*}$ , la relation $\equiv [n]$ est :

Réflexive : $a \equiv a [n]$ (car $n ∣ 0$ ).
Symétrique : si $a \equiv b [n]$ , alors $b \equiv a [n]$ .
Transitive : si $a \equiv b [n]$ et $b \equiv c [n]$ , alors $a \equiv c [n]$ .

Théorème 5.3 — Compatibilité avec les opérations

Soient $a, b, c, d \in Z$ et $n \in N^{*}$ . Si $a \equiv b [n]$ et $c \equiv d [n]$ , alors :

Somme : $a + c \equiv b + d [n]$ .
Produit : $a c \equiv b d [n]$ .
Puissance : pour tout $m \in N$ , $a^{m} \equiv b^{m} [n]$ .
Combinaison linéaire : pour tous $λ, μ \in Z$ , $λ a + μ c \equiv λ b + μ d [n]$ .

⚠ Piège #3 — On ne peut PAS simplifier une congruence par division.

6 \equiv 0 [4]

ne donne PAS

3 \equiv 0 [4]

en divisant par

2

. La règle correcte est : on peut simplifier

a c \equiv b c [n]

par

c

seulement si

c \land n = 1

(utilise alors Gauss). Sinon, il faut adapter le module :

a c \equiv b c [n] \Rightarrow a \equiv b [n / (c \land n)]

. Méconnaître cette règle est une perte sèche de points au DS.

Définition 5.4 — Classes modulo n et anneau ℤ/nℤ

La classe de $a$ modulo $n$ est l'ensemble :

\overline{a} = {b \in Z, a \equiv b [n]} = a + n Z .

L'ensemble $Z / n Z = {\overline{0}, \overline{1}, \dots, \overline{n - 1}}$ des classes a exactement $n$ éléments. Muni des opérations $\overline{a} + \overline{b} = \overline{a + b}$ et $\overline{a} \cdot \overline{b} = \overline{a b}$ (bien définies par la compatibilité du Thm 5.3), c'est un anneau commutatif.

Proposition 5.5 — Éléments inversibles de ℤ/nℤ

Soit $a \in Z$ . La classe $\overline{a}$ est inversible dans $Z / n Z$ si et seulement si $a \land n = 1$ . Le groupe des inversibles est noté $(Z / n Z)^{\times}$ .

Conséquence : $Z / n Z$ est un corps si et seulement si $n$ est premier.

Théorème 5.6 — Petit théorème de Fermat

Soit $p$ un nombre premier. Alors pour tout $a \in Z$ :

Forme courte : $a^{p} \equiv a [p]$ .
Forme classique (si $p ∤ a$ , c'est-à-dire $a \land p = 1$ ) : $a^{p - 1} \equiv 1 [p] .$

Idée de preuve : dans $(Z / p Z)^{\times}$ , qui est un groupe à $p - 1$ éléments, l'ordre de tout élément divise $p - 1$ (théorème de Lagrange, souvent admis en MPSI). Donc $\overline{a}^{p - 1} = \overline{1}$ , soit $a^{p - 1} \equiv 1 [p]$ . On en déduit $a^{p} \equiv a [p]$ (vrai aussi quand $p ∣ a$ car alors les deux membres sont $\equiv 0 [p]$ ).

💡 Exemple — Fermat en pratique. Pour calculer

7^{222} mod 11

: par Fermat,

7^{10} \equiv 1 [11]

. Or

222 = 22 \times 10 + 2

, donc

7^{222} = (7^{10})^{22} \cdot 7^{2} \equiv 1^{22} \cdot 49 \equiv 49 \equiv 5 [11]

. Réflexe : dès qu'on calcule

a^{N} mod p

avec

p

premier et

a \land p = 1

, réduire

N

modulo

p - 1

avec Fermat.

6. Erreurs classiques en copie (vues par les correcteurs)

Ces erreurs sont relevées chaque année dans les rapports de jury (CCINP, Mines-Ponts, Centrale, X-ENS) sur les épreuves comportant de l'arithmétique. Elles coûtent typiquement entre 0,5 et 2 points par occurrence — c'est le chapitre où la rigueur sur les hypothèses est la plus rentable.

⚠ Erreur 1 — Invoquer Gauss sans vérifier la coprimalité. «

a ∣ b c

donc

a ∣ c

» est FAUX en général. Il faut écrire explicitement « comme

a \land b = 1

, par théorème de Gauss,

a ∣ c

». Si l'hypothèse

a \land b = 1

n'est pas dans l'énoncé, c'est à toi de la prouver — souvent en exhibant une relation de Bézout

a u + b v = 1

⚠ Erreur 2 — Confondre $a \land b$ (entier positif) et « $u, v$ tels que $a u + b v = a \land b$ » (couple non unique). Le PGCD est unique, les coefficients de Bézout ne le sont PAS : si

(u_{0}, v_{0})

convient, alors

(u_{0} + k b / (a \land b), v_{0} - k a / (a \land b))

convient aussi pour tout

k \in Z

. Toujours préciser « une solution » ou « toutes les solutions ».

⚠ Erreur 3 — Diviser une congruence sans précaution.

2 \cdot 5 \equiv 2 \cdot 1 [8]

ne donne PAS

5 \equiv 1 [8]

(faux :

5 - 1 = 4 \neq \equiv 0 [8]

). La simplification n'est licite que si le facteur simplifié est premier au module (

2 \land 8 = 2 \neq = 1

ici, d'où l'échec). Cette erreur tombe à chaque DS.

⚠ Erreur 4 — Croire que tout entier $\geq 2$ est premier ou composé. Vrai (c'est exactement la dichotomie), mais beaucoup d'élèves oublient le test $p \leq n$ et déclarent prématurément un entier composé. Pour

n = 97

97 \approx 9, 85

, donc tester

2, 3, 5, 7

suffit : aucun ne divise

97

, donc

97

est premier.

⚠ Erreur 5 — Appliquer Fermat sans vérifier $p$ premier et $a \land p = 1$ . Le petit théorème de Fermat exige les deux hypothèses pour la forme

a^{p - 1} \equiv 1 [p]

. Avec

p = 4

(non premier),

3^{3} = 27 \equiv 3 [4]

, pas

1

. Avec

p = 5

a = 10

(

a \land p = 5 \neq = 1

1 0^{4} \equiv 0 [5]

, pas

1

. Toujours écrire les deux hypothèses avant d'invoquer Fermat.

7. Pour aller plus loin

L'arithmétique dans ℤ est l'infrastructure de plusieurs chapitres de spé et de domaines entiers de mathématiques. Les chapitres qui la réinvestissent directement :

Polynômes — la division euclidienne dans $K [X]$ imite celle de ℤ, et Bézout + Gauss s'y étendent (irréductibilité = primalité).
Structures algébriques — $Z / n Z$ est l'exemple-type d'anneau quotient ; $(Z / p Z)^{\times}$ est le groupe cyclique fini de référence.
Cryptographie RSA (culture) — repose sur Euclide étendu, Fermat et la difficulté de factoriser un grand entier.
Théorie des nombres en spé — théorème chinois, indicateur d'Euler — partent tous des outils de cette fiche.

Récap final — Ce qu'il faut absolument retenir

À la veille d'une khôlle ou d'un DS, parcours cette checklist : tu dois pouvoir répondre « oui, sans hésiter » à chaque question.

Sais-tu énoncer la division euclidienne de $a \in Z$ par $b \in N^{*}$ avec la condition $0 \leq r < b$ ?
Sais-tu démontrer que $a \land b = b \land r$ (algorithme d'Euclide) ?
Sais-tu calculer un PGCD chiffré (par exemple $252 \land 105$ ) en moins de 90 secondes ?
Sais-tu énoncer ET démontrer le théorème de Bachet-Bézout via l'algorithme d'Euclide étendu ?
Sais-tu énoncer ET démontrer le théorème de Gauss à partir de Bézout ?
Sais-tu donner un contre-exemple à « $a ∣ b c \Rightarrow a ∣ c$ » sans l'hypothèse de coprimalité ?
Sais-tu écrire la relation $(a \land b) (a \lor b) = ∣ a b ∣$ et l'utiliser dans les deux sens ?
Sais-tu démontrer l'infinité des nombres premiers par la preuve d'Euclide ( $N = p_{1} \dots p_{n} + 1$ ) ?
Sais-tu énoncer le théorème fondamental de l'arithmétique (existence + unicité de la décomposition primaire) ?
Sais-tu manipuler les congruences (somme, produit, puissance) ET dire quand la simplification par un facteur est licite ?
Sais-tu énoncer le petit théorème de Fermat dans ses deux formes et l'utiliser pour calculer $a^{N} mod p$ ?
Connais-tu la méthode-type pour résoudre une équation diophantienne $a x + b y = c$ (existence + solution particulière + générale) ?

Démonstrations à savoir refaire

Algorithme d'Euclide — égalité $a \land b = b \land r$ via égalité des ensembles de diviseurs communs
Théorème de Bachet-Bézout — par récurrence forte sur les restes de l'algorithme d'Euclide étendu
Théorème de Gauss — multiplier $a u + b v = 1$ par $c$ , puis combinaison linéaire
Infinité des nombres premiers — preuve d'Euclide par l'absurde, $N = p_{1} \dots p_{n} + 1$

Vue d'ensemble

Prérequis

1. Divisibilité dans ℤ

2. PGCD, PPCM et algorithme d'Euclide

3. Nombres premiers entre eux et théorème de Gauss

4. Nombres premiers

5. Congruences modulo n et anneau ℤ/nℤ

6. Erreurs classiques en copie (vues par les correcteurs)

7. Pour aller plus loin

Récap final — Ce qu'il faut absolument retenir

Démonstrations à savoir refaire

Fiches associées

Nombres réels

Suites numériques

Généralités sur les fonctions

Limites et continuité

Fonctions dérivables

Logarithmes, exponentielles et puissances

Tu veux aller plus loin sur ce chapitre ?