Chapitre XIV – Arithmétique (Maths expertes)

Bacomathiques — https://bacomathiqu.es

TABLE DES MATIÈRES

I- Divisibilité et congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1. Divisibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2. Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
3. Congruences dans ℤ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
II - PGCD et théorème de Bézout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1. Plus Grand Commun Diviseur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Théorème de Bézout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3. Lemme de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4. Équations diophantiennes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
III - Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1. Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2. Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3. Décomposition de nombres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
I - Divisibilité et congruence 1

I - Divisibilité et congruence
1. Divisibilité
Dans toute la suite de cette section, on notera par ℤ l’ensemble des nombres entiers relatifs (i.e. ℤ =
{… , −2, −1, 0, 1, 2, … }) et par ℕ l’ensemble des nombres entiers naturels (i.e. ℕ = {0, 1, 2, … }).
À RETENIR

Définition
Soient 𝑎 et 𝑏 deux entiers relatifs. On dit que 𝑏 divise 𝑎 (ou que 𝑎 est un multiple de 𝑏) s’il existe 𝑘 ∈ ℤ
tel que 𝑎 = 𝑘𝑏. On note ceci par 𝑏 ∣ 𝑎.

À LIRE

Si on a 𝑏 divise 𝑎, alors −𝑏 divise 𝑎. Par exemple, comme 6 divise 12, alors −6 divise également 12.

À RETENIR

Propriétés
— Tout entier relatif 𝑏 divise 0 (car 0 = 0 × 𝑏).
— 1 divise tout entier relatif 𝑎 (car 𝑎 = 𝑎 × 1).
— Si 𝑐 ∣ 𝑎 et 𝑐 ∣ 𝑏 alors 𝑐 ∣ (𝑎𝑢 + 𝑏𝑣) pour tout 𝑢, 𝑣 ∈ ℤ.

2. Division euclidienne
La division euclidienne est une notion mathématique que l’on aborde très tôt au cours de notre scolarité
(dès la classe de CM1). Nous allons tenter de formaliser ceci :
À RETENIR

Théorème de la division euclidienne

Soient 𝑎, 𝑏 ∈ ℤ. On suppose 𝑏 ≠ 0. On appelle division euclidienne de 𝑎 par 𝑏, l’opération qui à (𝑎, 𝑏),
associe le couple d’entiers relatifs (𝑞, 𝑟) tel que 𝑎 = 𝑏𝑞 + 𝑟 où 0 ≤ 𝑟 < |𝑏|. Un tel couple existe forcément
et est unique.

À RETENIR

Vocabulaire
En reprenant les notations du théorème, 𝑎 s’appelle le dividende, 𝑏 le diviseur, 𝑞 le quotient et 𝑟 le reste
de la division euclidienne.

bacomathiqu.es
I - Divisibilité et congruence 2

À LIRE

Exemple
On souhaite effectuer la division euclidienne de 314 par 7. Posons-la :
3 1 4 7
3 4 4 4
6

— On cherche combien de fois 7 est contenu dans 31 (cela ne sert à rien de commencer par 3 car
3 < 7). On a 4 × 7 = 28 et 5 × 7 = 35 donc on écrit 4 sous le diviseur et le reste 31 − 28 = 3. Puis, on
abaisse le chiffre des unités qui est 4.
— On recommence : combien de fois 7 est-il contenu dans 34 ? Comme 4 × 7 = 28 et 5 × 7 = 35, 7 est
contenu 4 fois dans 34 et il reste 34 − 28 = 6.
— Comme 6 < 7, la division euclidienne est terminée : on a 314 = 7 × 44 + 6.

Donnons enfin une propriété qui nous sera utile dans la section suivante.
À RETENIR

Propriété
Soit 𝑛 ∈ ℕ tel que 𝑛 ≠ 0. Deux entiers relatifs 𝑎 et 𝑏 ont le même reste dans la division euclidienne par 𝑛
si et seulement si 𝑎 − 𝑏 est un multiple de 𝑛.

3. Congruences dans ℤ
À RETENIR

Définition
On dit que deux entiers relatifs 𝑎 et 𝑏 sont congrus modulo 𝑛 (où 𝑛 est un entier naturel supérieur ou
égal à 2) si 𝑎 et 𝑏 ont le même reste dans la division euclidienne par 𝑛. On note alors 𝑎 ≡ 𝑏 mod 𝑛.

À LIRE

On remarque que 𝑎 est un multiple de 𝑛 si et seulement si 𝑎 ≡ 0 mod 𝑛.

bacomathiqu.es
I - Divisibilité et congruence 3

À LIRE

Exemple
Par exemple, 1 ≡ 4 ≡ 7 mod 3.

0 1 2 3 4 5 6 7 8 9

On signale que la congruence est une relation d’équivalence.

À RETENIR

Propriétés
Soit 𝑛 ≥ 2. Pour tout 𝑎, 𝑏, 𝑐 ∈ ℤ :
— 𝑎 ≡ 𝑎 mod 𝑛 (réflexivité)
— Si 𝑎 ≡ 𝑏 mod 𝑛, alors 𝑏 ≡ 𝑎 mod 𝑛 (symétrie)
— Si 𝑎 ≡ 𝑏 mod 𝑛, et si 𝑏 ≡ 𝑐 mod 𝑛, alors 𝑎 ≡ 𝑐 mod 𝑛 (transitivité)

De plus, la congruence est compatible avec les opérations usuelles sur les entiers relatifs.
À RETENIR

Propriétés
Soit 𝑛 ≥ 2. Soient 𝑎, 𝑏, 𝑐 et 𝑑 ∈ ℤ tels que 𝑎 ≡ 𝑏 mod 𝑛 et 𝑐 ≡ 𝑑 mod 𝑛. Alors on a la compatibilité avec :
— L’addition : 𝑎 + 𝑐 ≡ 𝑏 + 𝑑 mod 𝑛.
— La multiplication : 𝑎𝑐 ≡ 𝑏𝑑 mod 𝑛.
— Les puissances : pour tout 𝑘 ∈ ℕ, 𝑎 𝑘 ≡ 𝑏 𝑘 mod 𝑛.

À LIRE

Exemple
Comme 7 ≡ 3 mod 4, et 5 ≡ 1 mod 4, on a 35 = 5 × 7 ≡ 1 × 5 mod 4.

bacomathiqu.es
II - PGCD et théorème de Bézout 4

II - PGCD et théorème de Bézout

1. Plus Grand Commun Diviseur
À RETENIR

Définition
Soient 𝑎, 𝑏 ∈ ℤ non tous nuls. Le Plus Grand Commun Diviseur de 𝑎 et 𝑏 (noté PGCD(𝑎; 𝑏)) est le plus
grand entier positif qui les divise simultanément.

Avec cette définition, on peut dégager quelques propriétés.

À RETENIR

Propriétés
Soient 𝑎, 𝑏 ∈ ℤ non tous nuls.
— PGCD(𝑎; 𝑏) = PGCD(𝑏; 𝑎)
— PGCD(𝑎; 1) = 1
— PGCD(𝑎; 0) = 𝑎
— Pour tout 𝑘 ∈ ℕ, PGCD(𝑘𝑎; 𝑘𝑏) = 𝑘 PGCD(𝑎; 𝑏)
— Si 𝑏 ∣ 𝑎, alors PGCD(𝑎; 𝑏) = |𝑏|

Il existe une manière de déterminer le PGCD de deux entiers naturels non nuls 𝑎 et 𝑏 avec 𝑏 < 𝑎 appelée
Algorithme d’Euclide.
À RETENIR

Algorithme d’Euclide
Soient 𝑎, 𝑏 ∈ ℤ non tous nuls. Pour obtenir PGCD(𝑎; 𝑏), on procède comme suit :
1. On fait la division euclidienne de 𝑎 par 𝑏 et on appelle 𝑟 le reste.
2. Si 𝑟 = 0, alors PGCD(𝑎; 𝑏) = 𝑏.
3. Sinon on recommence l’étape 1 en remplaçant 𝑎 par 𝑏 et 𝑏 par 𝑟.

Terminons cette section par une définition.

À RETENIR

Nombres premiers entre eux

On dit que deux nombres sont premiers entre eux si leur PGCD est égal à 1.

À LIRE

𝑎 𝑏
Petite remarque : si on note 𝑑 le PGCD de deux nombres 𝑎 et 𝑏, alors 𝑑
et 𝑑
sont deux nombres premiers
entre eux.

bacomathiqu.es
II - PGCD et théorème de Bézout 5

2. Théorème de Bézout
Un résultat fondamental de l’arithmétique est le théorème de Bachet-Bézout (que l’on rencontre parfois
sous le nom d’identité de Bézout).
À RETENIR

Théorème de Bachet-Bézout
Soient 𝑎 et 𝑏 deux entiers relatifs non nuls. On note 𝑑 leur PGCD. Alors il existe deux entiers relatifs 𝑢 et 𝑣
tels que 𝑢𝑎 + 𝑣𝑏 = 𝑑.

À RETENIR

Théorème de Bézout
Une conséquence de ce théorème est que 𝑎 et 𝑏 sont premiers entre eux si et seulement s’il existe deux
entiers relatifs 𝑢 et 𝑣 tels que 𝑢𝑎 + 𝑣𝑏 = 1.

À LIRE

Exemple
Calculons PGCD(250; 150) et déduisons-en deux entiers relatifs 𝑢 et 𝑣 tels que 50 = 250𝑢 + 150𝑣. Com-
mençons par calculer le PGCD de 250 et 150 par l’algorithme d’Euclide :
La division euclidienne de 250 par 150 donne 250 = 150 × 1 + 100.
La division euclidienne de 150 par 100 donne 150 = 100 × 1 + 50.
La division euclidienne de 100 par 50 donne 100 = 5 × 2 + 0.
On a PGCD(250; 150) = 50. Déterminons 𝑢 et 𝑣 :
250 = 150 × 1 + 100 ⟺ 150 = 1 × 250 − 1 × 100
150 = 1 × 100 + 50 ⟺ 50 = 150 − 1 × 100
Donc 50 = 1 × 250 − 1 × 100 − 1 × 100 = 1 × 250 − 2 × 100.
On a par conséquent 𝑢 = 1 et 𝑣 = −2. L’algorithme que l’on vient d’utiliser pour trouver 𝑢 et 𝑣 s’appelle
l’algorithme d’Euclide étendu.

À RETENIR

Résolution d’une congruence simple

Supposons que l’on souhaite résoudre une congruence du type 𝑎𝑥 ≡ 𝑏 mod 𝑛 d’inconnue 𝑥. On pose
𝑑 = PGCD(a; n). Alors :
1. Si 𝑑 ne divise pas 𝑏, on cherche deux entiers 𝑢 et 𝑣 tels que 𝑎𝑢 + 𝑛𝑣 = 1 (avec l’algorithme
d’Euclide étendu par exemple). Les solutions de la congruence sont alors les entiers 𝑥 vérifiant
𝑥 ≡ 𝑢𝑏 mod 𝑛.
2. Si 𝑑 ∣ 𝑏, cela revient à résoudre la congruence 𝑑𝑎 𝑥 ≡ 𝑑𝑏 mod 𝑛𝑑 , et on se ramène au cas 1 (avec la
nouvelle congruence à résoudre).

bacomathiqu.es
II - PGCD et théorème de Bézout 6

À LIRE

Exemple
On souhaite résoudre la congruence 6𝑥 ≡ 6 mod 9. Alors, comme 𝑑 = PGCD(6; 9) = 3, on a 𝑑 ∣ 6. On se
ramène donc à résoudre 2𝑥 ≡ 2 mod 3 (où 2 et 3 sont premiers entre eux).
On écrit l’identité de Bézout appliquée à 2 et 3 : 2 × 2 + 3 × −1 = 1. Donc les solutions à la congruence du
début sont les entiers 𝑥 vérifiant 𝑥 ≡ 4 mod 3 ≡ 1 mod 3 (i.e. les 𝑥 de la forme 𝑥 = 3𝑘 + 1 où 𝑘 ∈ ℤ).

3. Lemme de Gauss
À RETENIR

Lemme de Gauss
Soient 𝑎, 𝑏 et 𝑐 trois entiers non nuls. Si 𝑐 ∣ 𝑎𝑏 et 𝑐 est premier avec 𝑎, alors 𝑐 ∣ 𝑏.

À RETENIR

Corollaire
Soient 𝑎, 𝑏 et 𝑐 trois entiers non nuls. Si 𝑏 ∣ 𝑎, 𝑐 ∣ 𝑎 et que 𝑏 et 𝑐 sont premiers entre eux, alors 𝑏𝑐 ∣ 𝑎.

4. Équations diophantiennes
À RETENIR

Définition
Une équation diophantienne linéaire en deux variables 𝑥 et 𝑦 est une équation de la forme (𝐸) ∶
𝑎𝑥 + 𝑏𝑦 = 𝑐 où les coefficients 𝑎, 𝑏 et 𝑐 sont des entiers relatifs et où les solutions sont également des
entiers relatifs.

À RETENIR

Solutions de (𝐸)
En reprenant les notations précédentes, on pose 𝑑 = PGCD(𝑎; 𝑏). Alors :
— Si 𝑑 ∣ 𝑐, on cherche une solution particulière à (𝐸) que l’on note (𝑥0 ; 𝑦0 ). Alors les solutions de (𝐸)
sont les couples (𝑥𝑘 ; 𝑦𝑘 ) où 𝑥𝑘 = 𝑥0 + 𝑘 𝑑𝑏 et 𝑦𝑘 = 𝑦0 − 𝑘 𝑑𝑎 .
— Sinon, (𝐸) n’a pas de solution.

bacomathiqu.es
II - PGCD et théorème de Bézout 7

À LIRE

Exemple
On cherche à résoudre l’équation diophantienne (𝐸) ∶ 25𝑥 + 10𝑦 = 15. Commençons par chercher une
solution particulière (𝑥0 ; 𝑦0 ).
Comme 𝑑 = PGCD(25; 10) = 5, on a 𝑑 ∣ 15. En divisant les deux côtés de l’égalité par 5, on a (𝐸) ⟺
5𝑥 + 2𝑦 = 3.
Cherchons une solution particulière à (𝐸). On écrit l’identité de Bézout appliquée à 5 et 2 : 5×1+2×−2 = 1.
Ainsi, en multipliant les deux côtés de l’égalité par 3, on obtient : 5 × 3 + 2 × −6 = 3.
On a trouvé une solution particulière à (𝐸) qui est le couple (𝑥0 ; 𝑦0 ) où 𝑥0 = 3 et 𝑦0 = −6. On pourrait
appliquer la formule pour donner la forme générale des solutions de (𝐸), mais essayons de ne pas
l’utiliser.
Soit (𝑥; 𝑦) une autre solution de (𝐸). On a 3 = 5𝑥 + 2𝑦 = 5𝑥0 + 2𝑦0 . D’où 5(𝑥 − 𝑥0 ) = 2(𝑦0 − 𝑦) (en passant
les 𝑥 et 𝑥0 du même côté de l’égalité et en faisant de même pour 𝑦 et 𝑦0 , puis en factorisant).
Ainsi, on a 5 ∣ 2(𝑦0 − 𝑦). Or, 5 et 2 sont premiers entre eux, donc par le lemme de Gauss, 5 ∣ 𝑦0 − 𝑦. Il existe
donc 𝑞1 tel que 5𝑞1 = 𝑦0 − 𝑦, d’où 𝑦 = 𝑦0 − 5𝑞1 .
De même, 2 ∣ 5(𝑥 − 𝑥0 ) avec 2 et 5 premiers entre eux, donc par le lemme de Gauss, 2 ∣ 𝑥 − 𝑥0 . Il existe
donc 𝑞2 tel que 2𝑞2 = 𝑥 − 𝑥0 , d’où 𝑥 = 𝑥0 + 2𝑞2 .
En réinjectant tout ça dans (𝐸), on obtient 5(𝑥0 + 2𝑞2 ) + 2(𝑦0 + −5𝑞1 ) = 3 ⟺ 5𝑥 0 + 2𝑦0 +10𝑞2 − 10𝑞1 =
⏟⏟⏟⏟⏟⏟⏟⏟⏟
=3
3 ⟺ 𝑞1 = 𝑞2 .
Les solutions de (𝐸) sont donc les couples (𝑥𝑘 ; 𝑦𝑘 ) où 𝑥𝑘 = 𝑥0 + 2𝑘 et 𝑦𝑘 = 𝑦0 − 5𝑘 (et on a bien les mêmes
résultats qu’avec la formule).

bacomathiqu.es
III - Nombres premiers 8

III - Nombres premiers

1. Définition
Commençons cette section par définir ce qu’est un nombre premier. Il s’agit là d’une notion dont entend
parler très tôt au cours de notre scolarité, sans pour autant vraiment rentrer dans le sujet. Détaillons donc un
peu tout ceci.
À RETENIR

Nombre premier
Un nombre entier 𝑝 ≥ 2 est dit premier si ses seuls diviseurs positifs sont 1 et lui-même.

À LIRE

Exemple
2, 3, 5, 7, 11 et 13 sont des nombres premiers.

2. Propriétés
Voici quelques propriétés basiques que possèdent les nombres premiers.
À RETENIR

Propriétés
Soit 𝑛 ∈ ℕ supérieur ou égal à 2, alors on a les propriétés suivantes :
— Si 𝑛 n’admet aucun diviseur premier inférieur ou égal à √𝑛, alors 𝑛 est premier.
— Si 𝑛 n’est pas premier alors 𝑛 admet au moins un diviseur premier inférieur ou égal à √𝑛.
— Si 𝑛 est premier et 𝑛 ne divise pas un entier 𝑚, alors 𝑛 et 𝑚 sont premiers entre eux.

À RETENIR

Lemme d’Euclide
Soit 𝑝 un nombre premier et 𝑎 et 𝑏 deux entiers. Si 𝑝 ∣ 𝑎𝑏 alors 𝑝 ∣ 𝑎 ou 𝑝 ∣ 𝑏.

On donne enfin un résultat fondamental (mais qui reste très simple) sur l’ensemble des nombres premiers.
À RETENIR

Infinité de nombres premiers

Il existe une infinité de nombres premiers.

bacomathiqu.es
III - Nombres premiers 9

DÉMONSTRATION

Infinité de nombres premiers

Supposons par l’absurde que l’ensemble des nombres premiers soit un ensemble fini. On note par 𝑃 cet
ensemble et par 𝑟 sont cardinal. On a donc 𝑃 = {𝑝1 , 𝑝2 , … , 𝑝𝑟 } où 𝑝1 , 𝑝2 , ... , 𝑝𝑟 sont premiers.
Soit 𝑁 = 𝑝1 × 𝑝2 × ⋯ × 𝑝𝑟 + 1. Alors, 𝑁 ∉ 𝑃 donc 𝑁 n’est pas premier (et est strictement supérieur à 1). Il
existe donc un nombre premier qui divise 𝑁.
En d’autres mots, il existe 𝑖 ∈ {1, … , 𝑟} tel que 𝑝𝑖 ∣ 𝑁. De plus, 𝑝𝑖 ∣ 𝑝1 × 𝑝2 × ⋯ × 𝑝𝑟 .
Donc 𝑝𝑖 ∣ 𝑁 − 𝑝1 × 𝑝2 × ⋯ × 𝑝𝑟 ⟺ 𝑝𝑖 ∣ 1, donc 𝑝𝑖 = 1 ou 𝑝𝑖 = 0 : c’est absurde car 𝑝𝑖 ≥ 2.
Pour la petite histoire, c’est Euclide qui a fourni une première version de cette preuve en 300 av. J.-C !

À RETENIR

Petit théorème de Fermat

Soit 𝑝 un nombre premier et 𝑎 un entier non divisible par 𝑝. Alors 𝑎 𝑝−1 ≡ 1 mod 𝑝.

À LIRE

Cela revient au même de dire que si 𝑎 est un entier quelconque et que 𝑝 est un nombre premier, alors
𝑎 𝑝 ≡ 𝑎 mod 𝑝.

3. Décomposition de nombres
Passons maintenant à un résultat fondamental de l’arithmétique : le principe de décomposition en produit
de facteurs premiers (il s’agit même là d’un théorème qui est sobrement intitulé théorème fondamental de
l’arithmétique).
À RETENIR

Théorème fondamental de l’arithmétique

Soit 𝑛 ∈ ℕ supérieur ou égal à 2, alors 𝑛 peut s’écrire de la façon suivante :
𝛼 𝛼 𝛼
𝑛 = 𝑝1 1 × 𝑝2 2 × ⋯ × 𝑝𝑛 𝑛

où 𝑝1 , 𝑝2 , ... , 𝑝𝑛 des nombres premiers tels que 𝑝1 < 𝑝2 < ⋯ < 𝑝𝑛 et 𝛼1 , 𝛼2 , ... , 𝛼𝑛 des entiers naturels
non nuls.

bacomathiqu.es
III - Nombres premiers 10

À LIRE

Exemple
Décomposons 200 en produit de facteurs premiers.
— 200 = 2 × 100 (2 est le plus petit nombre premier qui divise 200).
— 100 = 2 × 50 (2 est le plus petit nombre premier qui divise 100).
— 50 = 2 × 25 (2 est le plus petit nombre premier qui divise 50).
— 25 = 5 × 5 (5 est le plus petit nombre premier qui divise 25).
— 5 = 5 × 1 (5 est un nombre premier, c’est terminé).
On a donc 200 = 2 × 100 = 2 × (2 × 50) = ⋯ = 23 × 52 .

bacomathiqu.es