Le cours

Résumé en cinq points

La division euclidienne de $a$ par $b$ non nul donne un unique couple $(q, r)$ avec $0 \leqslant r < \abs{b}$ , reste toujours positif.
L'algorithme d'Euclide calcule $a \wedge b$ et, remonté, fournit une relation de Bézout $au + bv = a \wedge b$ .
Théorème de Bézout : $a \wedge b = 1$ équivaut à l'existence de $u$ et $v$ avec $au + bv = 1$ . Lemme de Gauss : $a \mid bc$ et $a \wedge b = 1$ entraînent $a \mid c$ .
Tout entier $n \geqslant 2$ se décompose de façon unique en produit de facteurs premiers, ce que traduisent les valuations $p$ -adiques, avec min pour le PGCD et max pour le PPCM.
Les congruences sont compatibles avec l'addition et la multiplication, pas avec la simplification, sauf si le facteur simplifié est premier avec le module. Petit théorème de Fermat : $a^{p-1} \equiv 1\ [p]$ si $p$ est premier et ne divise pas $a$ .

Pourquoi ce chapitre

L'arithmétique est le premier chapitre où l'on démontre des théorèmes d'existence et d'unicité à partir de presque rien. Elle sert de banc d'essai aux modes de raisonnement vus en début d'année :

la récurrence forte ;
la disjonction de cas ;
l'absurde.

Elle fournit aussi un modèle que l'on reproduira presque à l'identique dans le chapitre sur les polynômes, où division euclidienne, PGCD, Bézout et Gauss réapparaissent mot pour mot. Aux concours, elle apparaît dans les exercices de dénombrement, dans les problèmes de suites d'entiers, et comme source d'exercices courts en khôlle. Le chapitre est court en contenu mais dense en techniques.

1Divisibilité et division euclidienne

1.1Divisibilité

Définition 1.1Divisibilité

Soient $a$ et $b$ deux entiers relatifs. On dit que $a$ divise $b$ , et on note $a \mid b$ , s'il existe un entier $k$ tel que $b = ka$ . On dit aussi que $b$ est un multiple de $a$ .

Propriété 1.2Propriétés immédiates

Tout entier divise $0$ .
Le seul entier divisible par tous les entiers est $0$ .
Si $a \mid b$ et $b \mid c$ , alors $a \mid c$ .
Si $a \mid b$ et $a \mid c$ , alors $a$ divise toute combinaison $ub + vc$ , avec $u$ et $v$ entiers.

Cette dernière propriété est l'outil le plus utilisé du chapitre.

Définition 1.3Entiers associés

Si $a \mid b$ et $b \mid a$ , alors $b = a$ ou $b = -a$ . On dit que $a$ et $b$ sont associés.

Deux entiers se divisent mutuellement si et seulement s'ils ont la même valeur absolue. Ce défaut d'unicité oblige à choisir le représentant positif quand on définit le PGCD.

Propriété 1.4Remarque de taille

Hypothèses

$a \mid b$ ;
$b \neq 0$ .

Alors $\abs{a} \leqslant \abs{b}$ .

Un entier non nul n'a donc qu'un nombre fini de diviseurs, ce qui légitime la définition du PGCD.

1.2Division euclidienne

Théorème 1.5Division euclidienne

Hypothèses

$a$ est un entier relatif ;
$b$ est un entier non nul.

Alors il existe un unique couple $(q, r)$ d'entiers relatifs tel que $a = bq + r \quad \text{et} \quad 0 \leqslant r < \abs{b}.$ L'entier $q$ est le quotient, $r$ est le reste.

Démonstration

Existence pour $b > 0$ : l'ensemble des entiers $k$ tels que $bk \leqslant a$ est non vide et majoré, donc il admet un plus grand élément $q$ . Alors $bq \leqslant a < b(q+1)$ , et $r = a - bq$ vérifie $0 \leqslant r < b$ .

Unicité : si $bq + r = bq' + r'$ avec deux restes dans $[0, b[$ , alors $b(q - q') = r' - r$ . Donc $b$ divise $r' - r$ , qui est de valeur absolue strictement inférieure à $b$ . Ainsi $r = r'$ puis $q = q'$ .

Propriété 1.6Lien avec la divisibilité

$b$ divise $a$ si et seulement si le reste de la division euclidienne de $a$ par $b$ est nul.

Attention

Le reste est toujours positif ou nul, même quand $a$ est négatif. La division euclidienne de $-7$ par $3$ donne $q = -3$ et $r = 2$ , pas $q = -2$ et $r = -1$ .

2PGCD, algorithme d'Euclide, PPCM

2.1Définition du PGCD

Définition 2.1PGCD

Soient $a$ et $b$ deux entiers naturels non tous les deux nuls. L'ensemble de leurs diviseurs communs positifs est non vide, car il contient $1$ , et fini, car l'un au moins de $a$ et $b$ est non nul. Il admet donc un plus grand élément pour l'ordre naturel de $\N$ . C'est le PGCD de $a$ et $b$ , noté $a \wedge b$ .

On étend la définition à deux entiers relatifs en posant $a \wedge b = \abs{a} \wedge \abs{b}$ . On convient que $0 \wedge 0 = 0$ .

2.2Algorithme d'Euclide

Lemme 2.2Lemme fondamental

Si $a = bq + r$ , alors l'ensemble des diviseurs communs à $a$ et $b$ est égal à l'ensemble des diviseurs communs à $b$ et $r$ . En particulier $a \wedge b = b \wedge r$ .

Démonstration

Un diviseur commun à $a$ et $b$ divise $a - bq = r$ . Réciproquement, un diviseur commun à $b$ et $r$ divise $bq + r = a$ .

MéthodeAlgorithme d'Euclide

Remplacer le couple $(a, b)$ par $(b, r)$ , où $r$ est le reste de la division de $a$ par $b$ .
Recommencer tant que le second terme n'est pas nul.
Le dernier reste non nul est $a \wedge b$ .

Les restes forment une suite d'entiers naturels strictement décroissante, donc l'algorithme s'arrête.

Exemple 2.3Calcul de $252 \wedge 198$

$\begin{aligned} 252 &= 1 \times 198 + 54,\\ 198 &= 3 \times 54 + 36,\\ 54 &= 1 \times 36 + 18,\\ 36 &= 2 \times 18 + 0. \end{aligned}$ Donc $252 \wedge 198 = 18$ .

Propriété 2.4Homogénéité

Pour tout entier $k \geqslant 1$ , $(ka) \wedge (kb) = k(a \wedge b)$ .

On le lit directement sur l'algorithme d'Euclide, dont toutes les lignes sont multipliées par $k$ .

2.3Deux caractérisations du PGCD

Théorème 2.5Diviseurs communs

L'ensemble des diviseurs communs à $a$ et $b$ est exactement l'ensemble des diviseurs de $a \wedge b$ .

Ainsi $a \wedge b$ est aussi le plus grand élément de l'ensemble des diviseurs communs pour la relation de divisibilité, et pas seulement pour l'ordre naturel. Tout diviseur commun à $a$ et $b$ divise $a \wedge b$ .

2.4Relation de Bézout

Théorème 2.6Relation de Bézout

Pour tous entiers $a$ et $b$ , il existe des entiers $u$ et $v$ tels que $au + bv = a \wedge b$ .

Démonstration

On remonte l'algorithme d'Euclide. Chaque reste s'écrit comme combinaison des deux termes précédents, donc de proche en proche comme combinaison de $a$ et $b$ . En pratique on utilise l'algorithme d'Euclide étendu, qui calcule $u$ et $v$ en même temps que le PGCD.

Attention

Le couple $(u, v)$ n'est jamais unique. Si $au + bv = d$ , alors pour tout entier $k$ les entiers $u + k(b/d)$ et $v - k(a/d)$ conviennent aussi.

Exemple 2.7Sur l'exemple précédent

$\begin{aligned} 18 &= 54 - 36\\ &= 54 - (198 - 3 \times 54)\\ &= 4 \times 54 - 198\\ &= 4(252 - 198) - 198\\ &= 4 \times 252 - 5 \times 198. \end{aligned}$

2.5PPCM

Définition 2.8PPCM

Le PPCM de deux entiers non nuls $a$ et $b$ , noté $a \vee b$ , est le plus petit élément strictement positif de l'ensemble de leurs multiples communs. L'ensemble des multiples communs à $a$ et $b$ est exactement l'ensemble des multiples de $a \vee b$ .

Propriété 2.9Lien avec le PGCD

Pour $a$ et $b$ entiers non nuls, $(a \wedge b)(a \vee b) = \abs{ab}$ .

2.6PGCD d'un nombre fini d'entiers

On définit de même le PGCD de $a_1, \dots, a_n$ , avec une relation de Bézout : il existe des entiers $u_1, \dots, u_n$ tels que $u_1 a_1 + \dots + u_n a_n$ vaille ce PGCD.

3Entiers premiers entre eux

3.1Définition et théorème de Bézout

Définition 3.1Entiers premiers entre eux

Deux entiers $a$ et $b$ sont premiers entre eux si $a \wedge b = 1$ , c'est-à-dire si leurs seuls diviseurs communs sont $1$ et $-1$ .

Théorème 3.2Théorème de Bézout

$a$ et $b$ sont premiers entre eux si et seulement s'il existe des entiers $u$ et $v$ tels que $au + bv = 1$ .

Démonstration

Le sens direct vient de la relation de Bézout. Pour la réciproque, si $au + bv = 1$ , tout diviseur commun à $a$ et $b$ divise $1$ , donc vaut $\pm 1$ .

Attention

La relation de Bézout, $au + bv = a \wedge b$ , existe toujours. Le théorème de Bézout est une équivalence, et il concerne le cas où le second membre vaut $1$ . Écrire $au + bv = 5$ ne prouve pas que $a \wedge b = 5$ : cela prouve seulement que $a \wedge b$ divise $5$ .

Propriété 3.3Forme irréductible

Hypothèses

$a$ et $b$ sont non tous nuls ;
$d = a \wedge b$ .

Alors $a = da'$ et $b = db'$ avec $a' \wedge b' = 1$ .

C'est la mise sous forme irréductible d'un rationnel : tout rationnel s'écrit $p/q$ avec $q > 0$ et $p \wedge q = 1$ , et cette écriture est unique.

3.2Lemme de Gauss

Théorème 3.4Lemme de Gauss

Hypothèses

$a$ divise $bc$ ;
$a \wedge b = 1$ .

Alors $a$ divise $c$ .

Démonstration

Il existe $u$ et $v$ avec $au + bv = 1$ . On multiplie par $c$ : $acu + bcv = c$ . Or $a$ divise $acu$ , et $a$ divise $bc$ donc $bcv$ . Donc $a$ divise $c$ .

Conséquences classiques :

si $b$ et $c$ divisent $a$ et si $b \wedge c = 1$ , alors $bc$ divise $a$ ;
si $a \wedge b = 1$ et $a \wedge c = 1$ , alors $a \wedge bc = 1$ .

3.3Entiers premiers entre eux dans leur ensemble ou deux à deux

Définition 3.5Dans leur ensemble, deux à deux

Les entiers $a_1, \dots, a_n$ sont premiers entre eux dans leur ensemble si leur PGCD vaut $1$ . Ils sont premiers entre eux deux à deux si $a_i \wedge a_j = 1$ dès que $i \neq j$ .

La seconde condition est strictement plus forte.

Exemple 3.6Contre-exemple

Les entiers $6$ , $10$ , $15$ sont premiers entre eux dans leur ensemble, car aucun entier supérieur à $1$ ne les divise tous, mais aucun couple n'est formé d'entiers premiers entre eux.

4Nombres premiers

4.1Définition et infinité

Définition 4.1Nombre premier

Un entier $p$ est premier s'il est supérieur ou égal à $2$ et si ses seuls diviseurs positifs sont $1$ et $p$ .

L'entier $1$ n'est pas premier, par convention qui rend l'unicité de la décomposition vraie.

Propriété 4.2Diviseur premier

Tout entier $n \geqslant 2$ admet un diviseur premier.

Démonstration

Récurrence forte, ou prendre le plus petit diviseur de $n$ supérieur ou égal à $2$ .

Théorème 4.3Infinité des nombres premiers

L'ensemble des nombres premiers est infini.

Démonstration

Par l'absurde. Si $p_1, \dots, p_r$ étaient tous les nombres premiers, l'entier $N = p_1 \cdots p_r + 1$ serait supérieur ou égal à $2$ , donc aurait un diviseur premier $p_i$ . Mais $p_i$ divise aussi le produit, donc $p_i$ diviserait $1$ . Contradiction.

Propriété 4.4Test de primalité

Hypothèses

$n \geqslant 2$ ;
$n$ n'est divisible par aucun entier $d$ tel que $2 \leqslant d \leqslant \sqrt{n}$ .

Alors $n$ est premier.

Le crible d'Ératosthène applique la même idée pour lister les premiers jusqu'à $N$ : on raye de proche en proche les multiples de chaque entier non encore rayé.

4.2Lemme d'Euclide et décomposition

Lemme 4.5Lemme d'Euclide

Hypothèses

$p$ est premier ;
$p$ divise un produit $ab$ .

Alors $p$ divise $a$ ou $p$ divise $b$ .

Démonstration

Si $p$ ne divise pas $a$ , alors $p \wedge a = 1$ car les seuls diviseurs de $p$ sont $1$ et $p$ , et le lemme de Gauss donne $p \mid b$ .

Théorème 4.6Théorème fondamental de l'arithmétique

Tout entier naturel $n \geqslant 2$ s'écrit comme produit de nombres premiers, et cette écriture est unique à l'ordre des facteurs près.

L'existence se démontre par récurrence forte, l'unicité par le lemme d'Euclide.

4.3Valuation p-adique

Définition 4.7Valuation $p$ -adique

Pour $p$ premier et $n$ entier non nul, la valuation $p$ -adique de $n$ , notée $v_p(n)$ , est l'exposant de $p$ dans la décomposition de $n$ . C'est le plus grand entier $k$ tel que $p^k$ divise $n$ .

On a $v_p(n) = 0$ pour tous les $p$ sauf un nombre fini, et $n$ s'écrit au signe près comme le produit des $p^{v_p(n)}$ .

Propriété 4.8Propriétés des valuations

$v_p(ab) = v_p(a) + v_p(b)$ ;
$a$ divise $b$ si et seulement si $v_p(a) \leqslant v_p(b)$ pour tout $p$ premier ;
$v_p(a \wedge b) = \min(v_p(a), v_p(b))$ ;
$v_p(a \vee b) = \max(v_p(a), v_p(b))$ .

La relation $(a \wedge b)(a \vee b) = \abs{ab}$ s'en déduit, puisque min plus max vaut la somme.

Attention

La décomposition en facteurs premiers coûte cher. Pour un PGCD de grands nombres, l'algorithme d'Euclide reste bien plus efficace.

5Congruences

5.1Définition et règles de calcul

Définition 5.1Congruence

Soit $n$ un entier naturel. On dit que $a$ est congru à $b$ modulo $n$ , et on note $a \equiv b\ [n]$ , si $n$ divise $b - a$ .

C'est une relation d'équivalence sur $\Z$ : elle est réflexive, symétrique et transitive.

Propriété 5.2Compatibilité

Hypothèses

$a \equiv b\ [n]$ ;
$c \equiv d\ [n]$ .

Alors $a + c \equiv b + d\ [n]$ et $ac \equiv bd\ [n]$ . Par récurrence, $a^k \equiv b^k\ [n]$ pour tout entier naturel $k$ .

Attention

On ne simplifie pas librement. De $2 \times 3 \equiv 2 \times 0\ [6]$ on ne peut pas déduire $3 \equiv 0\ [6]$ . La simplification par $a$ est licite quand $a \wedge n = 1$ , grâce au lemme de Gauss.

Exemple 5.3Reste de $3^{100}$ modulo $7$

On remarque que $3^3 = 27 \equiv 6 \equiv -1\ [7]$ . Donc $3^{99} \equiv (-1)^{33} \equiv -1\ [7],$ puis $3^{100} \equiv -3 \equiv 4\ [7]$ .

5.2Inverse modulo n

Définition 5.4Inverse modulo $n$

Un entier $a$ est inversible modulo $n$ s'il existe un entier $u$ tel que $au \equiv 1\ [n]$ .

Cela se produit si et seulement si $a \wedge n = 1$ . L'entier $u$ s'obtient par l'algorithme d'Euclide étendu : d'une relation $au + nv = 1$ on tire $au \equiv 1\ [n]$ .

Pour résoudre $ax \equiv b\ [n]$ avec $a \wedge n = 1$ , on multiplie par un inverse $u$ de $a$ et on obtient l'unique solution $x \equiv ub\ [n]$ .

Exemple 5.5Résoudre $5x \equiv 3\ [7]$

Comme $5 \times 3 = 15 \equiv 1\ [7]$ , l'inverse de $5$ est $3$ . Donc $x \equiv 9 \equiv 2\ [7]$ .

5.3Petit théorème de Fermat

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

Hypothèses

$p$ est un nombre premier ;
$a$ est un entier.

Alors $a^p \equiv a\ [p]$ . Si de plus $p$ ne divise pas $a$ , alors $a^{p-1} \equiv 1\ [p]$ .

Les deux formes sont équivalentes. La seconde se déduit de la première en simplifiant par $a$ , ce qui est permis car $a \wedge p = 1$ .

Attention

La réciproque est fausse. Il existe des entiers $n$ non premiers tels que $a^{n-1} \equiv 1\ [n]$ pour tout $a$ premier avec $n$ . Le petit théorème de Fermat sert donc à prouver qu'un nombre n'est pas premier, pas à prouver qu'il l'est.

Méthodes

MéthodeMontrer que $a$ divise $b$

Écrire $b$ comme combinaison d'expressions dont $a$ est facteur,
ou raisonner modulo $a$ en montrant que $b \equiv 0\ [a]$ .

MéthodeRésoudre une équation diophantienne $ax + by = c$

Calculer $d = a \wedge b$ . Il y a des solutions si et seulement si $d$ divise $c$ .
Trouver une solution particulière par l'algorithme d'Euclide étendu.
Décrire toutes les solutions en soustrayant deux solutions et en appliquant le lemme de Gauss.

MéthodeProuver qu'une fraction est irréductible

Exhiber une relation de Bézout entre le numérateur et le dénominateur.

MéthodeÉtudier un reste de division par $n$

Travailler modulo $n$ .
Chercher la période des puissances.
Une disjonction de cas sur le reste est souvent décisive.

MéthodeDivisibilité par plusieurs entiers premiers entre eux deux à deux

Traiter chaque module à part.
Conclure par le lemme de Gauss.

Ce qu'il faut savoir refaire en khôlle

Énoncer et démontrer le théorème de la division euclidienne, existence et unicité.
Dérouler l'algorithme d'Euclide sur deux entiers de trois chiffres, puis remonter pour obtenir une relation de Bézout.
Démontrer le lemme de Gauss à partir du théorème de Bézout.
Résoudre entièrement une équation diophantienne du type $17x + 5y = 3$ .
Démontrer que l'ensemble des nombres premiers est infini.
Démontrer l'unicité de la décomposition en facteurs premiers en utilisant le lemme d'Euclide.
Calculer un reste de puissance modulo un entier, avec ou sans le petit théorème de Fermat.
Donner un exemple d'entiers premiers entre eux dans leur ensemble mais pas deux à deux.

Méthodes et exercices

Les résultats à connaître

Si a | b et b | a alors |a| = |b| : exigible avec démonstration. Si a | b et b ≠ 0 alors |a| ≤ |b|.
Division euclidienne : pour a ∈ Z et b ≠ 0, il existe un unique couple (q, r) avec a = bq + r et 0 ≤ r < |b|. Exigible avec démonstration.
Les diviseurs communs à a et b sont exactement les diviseurs de a ∧ b : exigible avec démonstration par l'algorithme d'Euclide. En conséquence a ∧ b est le plus grand diviseur commun aussi au sens de la divisibilité.
Lemme d'Euclide : si a = bq + r alors a ∧ b = b ∧ r. Exigible avec démonstration. L'algorithme d'Euclide se termine car les restes décroissent strictement.
Relation de Bézout : il existe u et v dans Z avec au + bv = a ∧ b. Exigible avec démonstration par remontée de l'algorithme.
PPCM : les multiples communs à a et b non nuls sont les multiples de a ∨ b, et (a ∧ b)(a ∨ b) = |ab|. Exigible.
Théorème de Bézout : a ∧ b = 1 si et seulement s'il existe u et v avec au + bv = 1. Exigible avec démonstration. Forme irréductible d'un rationnel en conséquence.
Lemme de Gauss : si a | bc et a ∧ b = 1 alors a | c. Exigible avec démonstration.
Conséquences : si b | a, c | a et b ∧ c = 1 alors bc | a. Si a ∧ b = 1 et a ∧ c = 1 alors a ∧ bc = 1. Exigibles.
PGCD de plusieurs entiers, relation de Bézout, entiers premiers entre eux dans leur ensemble et deux à deux : exigibles.
Tout entier n ≥ 2 admet un diviseur premier, et l'ensemble des nombres premiers est infini : exigibles avec démonstration.
Lemme d'Euclide pour les premiers : si p premier divise ab alors p | a ou p | b. Exigible avec démonstration.
Existence et unicité de la décomposition en facteurs premiers : exigible avec démonstration.
Valuations p-adiques : v_p(ab) = v_p(a) + v_p(b), a | b si et seulement si v_p(a) ≤ v_p(b) pour tout p, et v_p(a ∧ b) = min, v_p(a ∨ b) = max. Exigibles.
Congruences : compatibilité avec la somme et le produit, donc avec les puissances. Exigible avec démonstration.
Inverse modulo n : a est inversible modulo n si et seulement si a ∧ n = 1. Exigible, c'est Bézout.
Petit théorème de Fermat : pour p premier, a^p ≡ a [p], et a^p−1 ≡ 1 [p] si p ne divise pas a. Exigible, démonstration classique par le binôme et récurrence.
Hors programme signalé : anneaux Z/nZ, idéaux de Z, théorème chinois comme énoncé général, indicatrice d'Euler, théorème de Wilson. Les exercices qui en approchent se traitent à la main avec Bézout et Gauss.

Clés de démonstration

Division euclidienne. Pour b > 0, l'ensemble des entiers k tels que bk ≤ a est non vide et majoré, il a un plus grand élément q, et r = a − bq vérifie 0 ≤ r < b. Pour l'unicité, deux écritures donnent b(q − q') = r' − r avec |r' − r| < b, donc r = r'. L'astuce : un multiple de b de valeur absolue strictement inférieure à b est nul.

Lemme d'Euclide. Un diviseur commun à a et b divise a − bq = r. Un diviseur commun à b et r divise bq + r = a. L'astuce : la propriété « d divise toute combinaison ub + vc » fait tout.

Bézout. Le dernier reste non nul de l'algorithme s'écrit comme combinaison des deux restes précédents, qui sont eux-mêmes combinaisons des deux d'avant, et ainsi de suite jusqu'à a et b. L'astuce : remonter en remplaçant à chaque étape le reste le plus récent, sans jamais développer les produits trop tôt.

Théorème de Bézout, sens réciproque. Si au + bv = 1, tout diviseur commun à a et b divise 1. L'astuce : le sens direct est la relation de Bézout, le sens réciproque est une ligne.

Gauss. On multiplie au + bv = 1 par c : acu + bcv = c. Chaque terme est divisible par a. L'astuce : faire apparaître c à partir de 1.

Infinité des premiers. Si p₁, …, p_r étaient tous les premiers, N = p₁⋯p_r + 1 aurait un diviseur premier p_i, qui diviserait aussi N − p₁⋯p_r = 1. L'astuce : N n'est pas forcément premier, il a seulement un diviseur premier nouveau.

Unicité de la décomposition. Si p₁⋯p_r = q₁⋯q_s, alors p₁ divise le produit des q_j, donc l'un d'eux par le lemme d'Euclide itéré, donc lui est égal. On simplifie et on recommence par récurrence. L'astuce : le lemme d'Euclide est la seule chose qui distingue les premiers des autres entiers.

Fermat. Pour 1 ≤ k ≤ p − 1, p divise k!(p − k)! C(p, k) = p! mais p est premier avec k!(p − k)!, donc p | C(p, k) par Gauss. Alors (a + 1)^p ≡ a^p + 1 [p], et une récurrence sur a ≥ 0 donne a^p ≡ a. Pour a < 0 on utilise (−a)^p ≡ −a et la parité de p ou le cas p = 2. L'astuce : le binôme modulo p ne garde que les deux termes extrêmes.

Exemples et contre-exemples à connaître

La division euclidienne de −7 par 3 donne q = −3 et r = 2, pas q = −2 et r = −1. Le reste est toujours dans [0, |b|[.
6, 10 et 15 sont premiers entre eux dans leur ensemble, aucun couple ne l'est. Les deux notions ne coïncident pas.
3 × 3 + 2 × (−2) = 5 alors que 3 ∧ 2 = 1. Une relation au + bv = d prouve seulement que a ∧ b divise d, sauf si d = 1.
2 × 3 ≡ 2 × 0 [6] et pourtant 3 ≢ 0 [6]. On ne simplifie une congruence que par un entier premier avec le module.
2¹⁰ = 1024 = 3 × 341 + 1, donc 2³⁴⁰ ≡ 1 [341], et pourtant 341 = 11 × 31 n'est pas premier. La réciproque du petit théorème de Fermat est fausse.
Le couple de Bézout n'est pas unique : 3 × (−1) + 2 × 2 = 1 et 3 × 1 + 2 × (−1) = 1. On passe de l'un à l'autre en ajoutant (b, −a).
1 n'est pas premier. Sans cette convention, 6 = 2 × 3 = 1 × 2 × 3 et l'unicité de la décomposition serait fausse.
n² + n + 41 est premier pour n allant de 0 à 39, mais 40² + 40 + 41 = 41². Aucune liste de cas ne démontre une primalité.
a ∧ 0 = |a| pour tout a, et 0 ∧ 0 = 0 par convention. Les cas dégénérés sont à vérifier avant d'écrire un quotient a/(a ∧ b).

Techniques du chapitre

Technique 1, Euclide étendu. Mini-exercice : relation de Bézout pour 17 et 5. 17 = 3 × 5 + 2, puis 5 = 2 × 2 + 1. Remontée : 1 = 5 − 2 × 2 = 5 − 2 × (17 − 3 × 5) = 7 × 5 − 2 × 17. Vérification : 35 − 34 = 1.

Technique 2, équation diophantienne ax + by = c. Mini-exercice : résoudre 17x + 5y = 3 dans Z². Solution particulière : (x, y) = (−6, 21), obtenue en multipliant la relation précédente par 3. Si (x, y) est solution, 17(x + 6) = 5(21 − y), donc 5 | 17(x + 6), et 5 ∧ 17 = 1 donne 5 | x + 6. Solutions : x = −6 + 5k, y = 21 − 17k, k ∈ Z, et l'on vérifie qu'elles conviennent.

Technique 3, reste d'une puissance par périodicité. Mini-exercice : reste de 2¹⁰⁰ modulo 7. 2³ = 8 ≡ 1 [7], et 100 = 3 × 33 + 1, donc 2¹⁰⁰ = (2³)³³ × 2 ≡ 2 [7].

Technique 4, Fermat pour réduire un exposant. Mini-exercice : reste de 3¹⁰⁰ modulo 13. 13 est premier et ne divise pas 3, donc 3¹² ≡ 1 [13]. Comme 100 = 8 × 12 + 4, 3¹⁰⁰ ≡ 3⁴ = 81 = 6 × 13 + 3 ≡ 3 [13].

Technique 5, disjonction sur les restes. Mini-exercice : montrer qu'un carré est congru à 0 ou 1 modulo 4. Si n = 2k, n² = 4k². Si n = 2k + 1, n² = 4(k² + k) + 1. Conséquence : un entier congru à 3 modulo 4 n'est pas somme de deux carrés.

Technique 7, valuations pour PGCD et PPCM. Mini-exercice : 360 = 2³ × 3² × 5 et 84 = 2² × 3 × 7. Le PGCD prend les minimums des exposants, 2² × 3 = 12, le PPCM les maximums, 2³ × 3² × 5 × 7 = 2520. Contrôle : 12 × 2520 = 30240 = 360 × 84.

Technique 8, fraction irréductible par Bézout. Mini-exercice : montrer que (n + 1)/(2n + 3) est irréductible pour tout entier n ≥ 0. On a (2n + 3) − 2(n + 1) = 1, relation de Bézout, donc (n + 1) ∧ (2n + 3) = 1.

Exercices classiques corrigés

Choisis ton niveau. Difficulté indicative ; les exercices qui se suivent restent dans l'ordre.

Exercice 1

Classiques de khôlle et concours · Khôlle

Soient a et b des entiers premiers entre eux. Montrer que a + b et ab sont premiers entre eux.

Technique raisonner avec un diviseur premier commun, ou avec Gauss.

Voir le corrigé

Soit p un nombre premier qui divise a + b et ab. Par le lemme d'Euclide, p | a ou p | b.
Si p | a, alors p divise (a + b) − a = b. De même dans l'autre cas. Donc p divise a et b, ce qui contredit a ∧ b = 1.
Aucun premier ne divise à la fois a + b et ab, donc leur PGCD, qui n'a aucun diviseur premier, vaut 1.

piège : Écrire « a ∧ b = 1 donc a ∧ (a + b) = 1 » sans le justifier. C'est vrai, et cela se justifie par la même idée, un diviseur commun à a et a + b divise b.

Exercice 2. Résoudre dans Z² l'équation 21x + 15y = 9

Classiques de khôlle et concours · Khôlle

Technique réduire par le PGCD, solution particulière, Gauss pour la solution générale.

Voir le corrigé

21 ∧ 15 = 3, et 3 | 9, donc il y a des solutions. L'équation équivaut à 7x + 5y = 3.
7 × (−1) + 5 × 2 = 3, donc (−1, 2) est solution.
Si (x, y) est solution, 7(x + 1) = 5(2 − y). Donc 5 | 7(x + 1), et 5 ∧ 7 = 1 donne 5 | x + 1, soit x = −1 + 5k. En reportant, 7 × 5k = 5(2 − y), donc y = 2 − 7k.
Réciproquement 7(−1 + 5k) + 5(2 − 7k) = 3. Solutions : (−1 + 5k, 2 − 7k), k ∈ Z.

piège : Oublier de vérifier que le PGCD divise le second membre, ce qui pour 21x + 15y = 10 donne immédiatement l'absence de solution.

Exercice 3

Classiques de khôlle et concours · Khôlle

Soit n ≥ 1 un entier. Montrer que √n est rationnel si et seulement si n est un carré parfait.

Technique valuations p-adiques et parité.

Voir le corrigé

Si n = m², √n = m est rationnel.
Supposons √n = p/q avec p, q entiers strictement positifs. Alors nq² = p². Pour tout nombre premier l, v_l(n) + 2v_l(q) = 2v_l(p).
Donc v_l(n) est pair pour tout l. En posant m égal au produit des l^v_l(n)/2, on obtient n = m².

piège : Vouloir refaire la preuve par parité de √2, qui ne se généralise pas telle quelle. Les valuations rendent la preuve uniforme.

Exercice 4. Montrer que pour tout entier n, 30 divise n⁵ − n

Classiques de khôlle et concours · Khôlle

Technique divisibilité par 2, 3 et 5 séparément, puis Gauss.

Voir le corrigé

Modulo 5 : 5 est premier, donc n⁵ ≡ n [5] par Fermat.
n⁵ − n = n(n − 1)(n + 1)(n² + 1). Parmi deux entiers consécutifs l'un est pair, parmi trois consécutifs l'un est multiple de 3. Donc 2 et 3 divisent n⁵ − n.
2, 3 et 5 sont premiers entre eux deux à deux. Par Gauss, 2 × 3 = 6 divise n⁵ − n, puis 6 ∧ 5 = 1 donne 30 | n⁵ − n.

piège : Conclure 30 | n⁵ − n dès que 2, 3, 5 divisent, sans invoquer la primalité deux à deux. L'argument est faux avec 4 et 6.

Exercice 5. Soit n ≥ 2. Montrer que si 2ⁿ − 1 est premier, alors n est premier

Classiques de khôlle et concours · Khôlle vers écrit

Technique contraposée et factorisation de x^b − 1.

Voir le corrigé

Supposons n non premier : n = ab avec 1 < a < n.
Avec x = 2^a, on a 2ⁿ − 1 = x^b − 1 = (x − 1)(x^b−1 + … + x + 1). Donc 2^a − 1 divise 2ⁿ − 1.
Comme 1 < a < n, on a 1 < 2^a − 1 < 2ⁿ − 1 : diviseur strict, donc 2ⁿ − 1 n'est pas premier.
La réciproque est fausse : 2¹¹ − 1 = 2047 = 23 × 89.

piège : Oublier de vérifier que le diviseur exhibé est différent de 1 et de 2ⁿ − 1, ce qui est le cœur de l'argument.

Exercice 6. Trouver tous les entiers x tels que x ≡ 2 [5] et x ≡ 3 [7]

Classiques de khôlle et concours · Écrit, type CCINP

Technique paramétrer par la première congruence, inverser modulo 7, conclure avec Gauss.

Voir le corrigé

x ≡ 2 [5] équivaut à x = 2 + 5k avec k ∈ Z. La seconde condition devient 5k ≡ 1 [7].
5 × 3 = 15 ≡ 1 [7], donc 3 est un inverse de 5 modulo 7. En multipliant par 3 : k ≡ 3 [7], soit k = 3 + 7m.
x = 2 + 5(3 + 7m) = 17 + 35m. Vérification : 17 = 3 × 5 + 2 = 2 × 7 + 3.
Réciproquement ces entiers conviennent. Les solutions sont les x ≡ 17 [35].

piège : Écrire x ≡ 17 [12] en additionnant les modules, ou diviser 5k ≡ 1 par 5 sans passer par un inverse. Le théorème chinois n'est pas au programme, on refait ce calcul à chaque fois.

Exercice 7. Montrer qu'il existe une infinité de nombres premiers congrus à 3 modulo 4

Classiques de khôlle et concours · Écrit, type CCINP

Technique variante de la preuve d'Euclide avec un entier bien choisi.

Voir le corrigé

Supposons qu'il n'y en ait qu'un nombre fini, p₁, …, p_r, et posons N = 4p₁⋯p_r − 1. N ≥ 3 est impair, il admet une décomposition en facteurs premiers impairs, chacun congru à 1 ou à 3 modulo 4.
Un produit d'entiers congrus à 1 modulo 4 est congru à 1 modulo 4, par compatibilité du produit. Or N ≡ −1 ≡ 3 [4]. Donc l'un des facteurs premiers de N est congru à 3 modulo 4.
Ce facteur est l'un des p_i, donc il divise 4p₁⋯p_r, donc il divise 4p₁⋯p_r − N = 1. Contradiction.

piège : Prendre N = 4p₁⋯p_r + 1, qui est congru à 1 modulo 4 et ne force aucun facteur à être congru à 3. Le choix du signe est le point clé.

Exercice 8. Soit p un nombre premier. Montrer que (p − 1)! ≡ −1 [p]

Classiques de khôlle et concours · Type oral

Technique inverses modulo p, appariement, cas des éléments égaux à leur inverse.

Voir le corrigé

Pour 1 ≤ a ≤ p − 1, a ∧ p = 1, donc a admet un inverse modulo p, que l'on peut choisir dans {1, …, p − 1}, et il est unique dans cet ensemble.
a est son propre inverse si et seulement si a² ≡ 1 [p], soit p | (a − 1)(a + 1), soit par Euclide a ≡ 1 ou a ≡ −1 [p], c'est à dire a = 1 ou a = p − 1.
Les entiers de 2 à p − 2 se regroupent en paires d'inverses distincts, chaque paire ayant un produit congru à 1. Donc 2 × 3 × ⋯ × (p − 2) ≡ 1 [p].
(p − 1)! ≡ 1 × 1 × (p − 1) ≡ −1 [p]. Les cas p = 2 et p = 3 se vérifient à la main.

piège : Oublier que 1 et p − 1 sont leurs propres inverses et les inclure dans les paires. Ce résultat, dit théorème de Wilson, n'est pas au programme, sa preuve l'est.

Exercice 9

Approfondissement · Écrit, type Centrale

Soit p premier et n ≥ 1. Montrer que v_p(n!) est la somme des parties entières de n/p^k pour k ≥ 1. Par combien de zéros se termine l'écriture décimale de 100! ?

Technique compter les contributions étage par étage.

Voir le corrigé

v_p(n!) est la somme des v_p(m) pour m de 1 à n, par multiplicativité de la valuation.
Un entier m de valuation exactement j est compté une fois par chaque puissance p^k avec k ≤ j. Donc la somme des v_p(m) est la somme, sur k ≥ 1, du nombre de multiples de p^k dans {1, …, n}, qui vaut la partie entière de n/p^k. La somme est finie car p^k > n à partir d'un certain rang.
Pour 100! : v₅ = 20 + 4 + 0 = 24 et v₂ = 50 + 25 + 12 + 6 + 3 + 1 = 97. Le nombre de zéros terminaux est v₁₀(100!) = min(v₂, v₅) = 24.

piège : Compter seulement les multiples de 5, qui donnent 20, et oublier que 25, 50, 75 et 100 apportent un facteur 5 supplémentaire.

Erreurs fréquentes

Écrire un reste négatif ou supérieur au diviseur. Le reste vit dans [0, |b|[, et c'est ce qui donne l'unicité.
Conclure a ∧ b = d à partir de au + bv = d. Cela ne marche que pour d = 1. Sinon on sait seulement que a ∧ b divise d.
Simplifier une congruence par un facteur non premier avec le module, ou ajouter des modules quand on combine deux congruences.
Confondre premiers entre eux dans leur ensemble et deux à deux. Gauss et la divisibilité par un produit exigent la version deux à deux.
Utiliser la réciproque du petit théorème de Fermat, ou prouver qu'un nombre est premier en testant quelques cas. Le seul test complet est la recherche de diviseurs jusqu'à la racine carrée.

Fiche de cours rédigée à partir du programme officiel de MPSI (2021), partie « Arithmétique dans l'ensemble des entiers relatifs ». Elle couvre la divisibilité, la division euclidienne, le PGCD et l'algorithme d'Euclide, les entiers premiers entre eux, les nombres premiers et les congruences. L'approche reste élémentaire : elle n'utilise pas le langage des structures algébriques. Les anneaux $\Z/n\Z$ sont explicitement hors programme.

Arithmétique dans Z

Résumé en cinq points

1Divisibilité et division euclidienne

1.1Divisibilité

1.2Division euclidienne

2PGCD, algorithme d'Euclide, PPCM

2.1Définition du PGCD

2.2Algorithme d'Euclide

2.3Deux caractérisations du PGCD

2.4Relation de Bézout

2.5PPCM

2.6PGCD d'un nombre fini d'entiers

3Entiers premiers entre eux

3.1Définition et théorème de Bézout

3.2Lemme de Gauss

3.3Entiers premiers entre eux dans leur ensemble ou deux à deux

4Nombres premiers

4.1Définition et infinité

4.2Lemme d'Euclide et décomposition

4.3Valuation p-adique

5Congruences

5.1Définition et règles de calcul

5.2Inverse modulo n

5.3Petit théorème de Fermat

Méthodes

Ce qu'il faut savoir refaire en khôlle

Les résultats à connaître

Clés de démonstration

Exemples et contre-exemples à connaître

Techniques du chapitre

Exercices classiques corrigés

Exercice 1

Exercice 2. Résoudre dans Z² l'équation 21x + 15y = 9

Exercice 3

Exercice 4. Montrer que pour tout entier n, 30 divise n⁵ − n

Exercice 5. Soit n ≥ 2. Montrer que si 2n − 1 est premier, alors n est premier

Exercice 6. Trouver tous les entiers x tels que x ≡ 2 [5] et x ≡ 3 [7]

Exercice 7. Montrer qu'il existe une infinité de nombres premiers congrus à 3 modulo 4

Exercice 8. Soit p un nombre premier. Montrer que (p − 1)! ≡ −1 [p]

Exercice 9

Erreurs fréquentes

Au concours

Exercice 5. Soit n ≥ 2. Montrer que si 2ⁿ − 1 est premier, alors n est premier