L’arithmétique A.

KARMIM

L’ARITHMETIQUE
I) REPPEL
1) Divisibilité dans ℤ.
Définition :
Soient 𝑎 et 𝑏 deux entiers relatifs tels que 𝑏 ≠ 0 ; on dit que l’entier relatif 𝑏 divise 𝑎 s’il existe un entier relatif 𝑘
tel que 𝒂 = 𝒌𝒃 ; on écrit : 𝒃|𝒂.
On dit que 𝑎 est divisible par 𝑏 ou 𝑎 est un multiple de 𝑏
Définition :
 Si 𝑏|𝑚 et 𝑏|𝑛 on dit que 𝑏 est un diviseur commun de 𝑚 et 𝑛
 Si 𝑏|𝑚 et 𝑏 ′ |𝑚 , on dit que 𝑚 est un multiple commun de 𝑏 et 𝑏′.

Propriété :
Etant donnés des entiers relatifs non nuls. On a les assertions suivantes :
𝑎|𝑏
 { ⇒ |𝑎| = |𝑏|
𝑏|𝑎
𝑎|𝑏
 { ⇒ 𝑎|𝑐
𝑏|𝑐
𝑎|𝑚
 { ⇒ 𝑎|𝛼𝑚 + 𝛽𝑛 où 𝛼 et 𝛽 sont des entiers relatifs quelconques.
𝑎|𝑛
Application :
Soient 𝑎𝑛 = 2𝑛 + 1 et 𝑏𝑛 = 5𝑛 + 4
1- Montrer que tout diviseur commun de 𝑎𝑛 et 𝑏𝑛 divise 3.
2- Déterminer tous les diviseurs communs de 𝑎𝑛 et 𝑏𝑛
Propriété :
𝑑|𝑎
{ ⇒ 𝑑𝛿|𝑎𝑏
𝛿|𝑏
 𝑎|𝑏 ⟺ 𝑎𝑛 |𝑏 𝑛
𝑑|𝑎
{ ⇒ 𝑑|𝑏
𝑑|𝑎 + 𝑏
2) Division Euclidienne
Propriété :
Considérons 𝑎 et 𝑏 deux entiers relatifs tels que 𝑏 ≠ 0 ils existent un entiers relatif 𝑞 et un entier naturel 𝑟
tels que : 𝑎 = 𝑏𝑞 + 𝑟 où 0 ≤ 𝑟 < |𝑏|
 L’entier 𝑎 s’appelle : Le divisé
 L’entier 𝑏 s’appelle : Le diviseur
 L’entier 𝑞 s’appelle : Le quotient
 L’entier 𝑟 s’appelle : Le reste
Exercice 1 :
Montrer que le reste de la division euclidienne de 𝑛² par 3 ne peut pas être égale à 2.
Exercice 2 :
a) Montrer que tout nombre premier s’écrit de la forme 𝑝 = 6𝑛 + 1 ou 𝑝 = 6𝑛 + 5
b) L’inverse est-il vraie ?
3) Les nombres premiers
Définitions
 On dit que l’entier 𝑑 est un diviseur effectif de l’entier relatif 𝑎 si 𝑑|𝑎 et |𝑑| ≠ 1 et |𝑑| ≠ |𝑎|
 On dit qu’un entier relatif non nul 𝑝 est premier s’il est différent de 1 et s’il n’admet pas de diviseurs
effectifs.
Remarque :
 Un nombre premier 𝑝 admet exactement deux diviseurs positifs 1 et |𝑝|.
1
L’arithmétique A.KARMIM
 Si 𝑝 est un nombre premier positif alors 𝑝 n’admet pas de diviseurs effectifs de même −𝑝 n’admet pas de
diviseurs effectif d’où : −𝑝 est aussi premier ;
Pour l’étude des nombres premiers on se contente d’étudier les nombres premiers positifs.

Propriété :
Soit 𝑎 un entier naturel non nul différent de 1 et non premier, le plus petit diviseur de 𝒂 diffèrent de 1 est un
nombre premier
Propriété :
Soit 𝑛 un entier naturel non nul, diffèrent de 1 et non premier, il existe un nombre premier 𝑝 qui divise l’entier 𝑛
et qui vérifie 𝑝2 ≤ 𝑛.
Remarque :
Cette propriété nous permet de déterminer si un nombre est premier ou non.
Corolaire :
Si un entier 𝑛 n’est divisible par aucun entier premier 𝑝 et qui vérifie 𝑝2 ≤ 𝑛 alors 𝑛 est premier.
Crible d’Eratosthène. Les nombres premiers inferieurs à 100

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

Application : Montrer que le nombre 2003 est premier.

Théorème :
L’ensemble des nombres premiers est infini.
4) Plus grand diviseurs commun
Définition :
On dit que le nombre 𝑑 est le plus grand diviseur commun de deux entiers relatifs 𝑎 et 𝑏 lorsque 𝑑 divise 𝑎 et 𝑑
divise 𝑏 et qu’il n’y a pas d’autre plus grands diviseurs de ces deux nombres. On note 𝑑 = 𝑃𝐺𝐷𝐶(𝑎, 𝑏) = 𝑎 ∧ 𝑏
Propriétés :
 𝑎 ∧ 𝑎 = |𝑎|
 1∧𝑎 =1
 (𝑎 ∧ 𝑏) ∧ 𝑐 = 𝑎 ∧ (𝑏 ∧ 𝑐)
 Si 𝑏|𝑎 alors 𝑎 ∧ 𝑏 = |𝑏|
𝑑|𝑎
 { ⇒ 𝑑|(𝑎 ∧ 𝑏)
𝑑|𝑏
 𝑎 ∧ 𝑏 = 𝑎 ∧ (𝑎 − 𝑏)
Exercice :
1- Montrer que tout diviseur commun de 𝑎 = 2𝑛 + 3 et 𝑏 = 5𝑛 + 1 est un diviseur de 13
2- Déterminer tous les diviseurs commun de 𝑎 et 𝑏.
3- Déterminer les valeurs de 𝑛 pour lesquels 𝑎 ∧ 𝑏 = 13.
Définition :
On dit que deux entier relatifs 𝑎 et 𝑏 sont premiers entre eux si 𝑎 ∧ 𝑏 = 1.
5) L’algorithme d’Euclide.
Théorème :
Soit 𝑎 un entier naturel et 𝑏 un entier naturel non nul on a : 𝑎 = 𝑏𝑞 + 𝑟 où 0 ≤ 𝑟 < 𝑏 on a : 𝑎 ∧ 𝑏 = 𝑏 ∧ 𝑟

2
L’arithmétique A.KARMIM
L’algorithme d’Euclide.
Soient 𝑎 et 𝑏 deux entiers naturels (𝑏 ≠ 0) on a :
𝑎 = 𝑏𝑞1 + 𝑟1 si 𝑟1 ≠ 0 alors :
𝑏 = 𝑟1 𝑞2 + 𝑟2 si 𝑟2 ≠ 0 alors :
𝑟1 = 𝑟2 𝑞3 + 𝑟3 si 𝑟3 ≠ 0 alors :
…….
𝑟𝑛−2 = 𝑟𝑛−1 𝑞𝑛 + 𝑟𝑛 si 𝑟𝑛 ≠ 0 alors :
𝑟𝑛−1 = 𝑟𝑛 𝑞𝑛+1 + 𝑟𝑛+1 si 𝑟𝑛+1 = 0 on arrête le processus.
Et d’après la propriété précédente : 𝑎 ∧ 𝑏 = 𝑏 ∧ 𝑟1 = 𝑟1 ∧ 𝑟2 = ⋯ = 𝑟𝑛−1 ∧ 𝑟𝑛 = 𝑟𝑛 car : 𝑟𝑛 |𝑟𝑛−1
Propriété :
Soient 𝑎 et 𝑏 deux entier naturels non nuls.
Le plus grand diviseur commun de 𝑎 et 𝑏 est le dernier reste non nul dans les divisions euclidiennes successives.
Application :
1- Trouver le 𝑃𝐺𝐷𝐶(362154 , 82350).
2- Déterminer tous les diviseurs commun de 362154 et 82350.
Propriété :
Soient 𝑎 et 𝑏 deux entier relatifs non nuls et 𝛿 = 𝑎 ∧ 𝑏, on a les diviseurs communs de 𝑎 et 𝑏 sont les diviseurs
de 𝛿. On peut dire que : 𝒟𝑎 ∩ 𝒟𝑏 = 𝒟𝑎∧𝑏
6) Le plus petit multiple commun.
Définition :
On dit que le nombre entier naturel 𝑚 est le plus petit multiple commun de deux entiers relatifs 𝑎 et 𝑏 lorsque
𝑚 est un multiple de 𝑎 et de 𝑏 et qu’il n’y a pas d’autre plus petit multiple non nuls de ces deux nombres. On
note : 𝑚 = 𝑃𝑃𝐶𝑀(𝑎, 𝑏) = 𝑎 ∨ 𝑏

Propriétés :
 𝑎 ∨ 𝑎 = |𝑎|
 𝑎∨𝑏 =𝑏∨𝑎
 𝑎 ∨ 1 = |𝑎|
 Si 𝑏|𝑎 alors 𝑎 ∨ 𝑏 = |𝑎|
 𝑎 ∨ (𝑏 ∨ 𝑐) = (𝑎 ∨ 𝑏) ∨ 𝑐
 𝑎|(𝑎 ∨ 𝑏) ; 𝑏|(𝑎 ∨ 𝑏) et (𝑎 ∨ 𝑏)|𝑎𝑏

Propriété :
Considérons 𝑎 et 𝑏 deux entiers relatifs.
Si 𝑎 ∨ 𝑏 = 𝑚 et 𝑀 un multiple commun de 𝑎 et 𝑏 alors 𝑚|𝑀.
7) la congruence modulo 𝒏.
Définition :
Soient 𝑎 et 𝑏 deux entiers relatifs ; et 𝑛 un entier naturel non nul. on dit que : 𝒂 est congrue à 𝒃 modulo 𝒏 si
𝑛|(𝒃 − 𝒂). On écrit : 𝒂 ≡ 𝒃 [𝒏]
Propriété :
Si 𝑎 ≡ 𝑏 [𝑛] alors 𝑎 et 𝑏 ont le même reste de la division euclidienne sur 𝑛
Propriété fondamentale :
 (∀𝑎 ∈ ℤ)(𝑎 ≡ 𝑎 [𝑛]) on dit que la relation de congruence est réflexive.
 (∀(𝑎, 𝑏) ∈ ℤ2 )( 𝑎 ≡ 𝑏 [𝑛] ⟺ 𝑏 ≡ 𝑎 [𝑛] ), on dit que la relation de congruence est symétrique.
𝑎 ≡ 𝑏 [𝑛]
 (∀(𝑎, 𝑏, 𝑐) ∈ ℤ3 ) ( ⇒ 𝑎 ≡ 𝑐 [𝑛]), on dit que la relation de congruence est transitive.
𝑏 ≡ 𝑐 [𝑛]
Définition :
Puisque la relation est de congruence est réflexive, symétrique et transitive on dit que la relation de congruence
est une relation d’équivalence

3
L’arithmétique A.KARMIM
Propriété et définition :
Soit 𝑛 un entier naturel non nul. Si 𝑎 ≡ 𝑏 [𝑛] et 𝑐 ≡ 𝑑 [𝑛] alors ;
 𝑎 + 𝑐 ≡ 𝑏 + 𝑑 [𝑛] ; On dit que la relation de congruence est compatible avec l’addition dans ℤ
 𝑎𝑐 ≡ 𝑏𝑑 [𝑛] ; On dit que la relation de congruence est compatible avec la multiplication dans ℤ
Corolaire :
Si 𝑎 ≡ 𝑏 [𝑛] alors pour tout 𝑘 dans ℕ on a : 𝑎𝑘 ≡ 𝑏 𝑘 [𝑛]
Applications
 Déterminer le reste de la division euclidienne de 45872018 par 9
 Déterminer le reste de la division euclidienne de 256146512 par 13
 Montrer que pour tout 𝑛 entier naturel : 32𝑛+1 + 2𝑛+2 est divisible par 7
 Montrer que pour tout 𝑛 entier naturel, 5𝑛3 + 𝑛 est divisible par 6
 Montrer que si 𝑛 n’est pas un multiple de 7, alors : 𝑛6 − 1 est un multiple de 7
 Montrer que pour tout entier naturel, le nombre 𝑛(𝑛² + 5) est divisible par 6
8) Les classes d’équivalences.
Définition :
Soit 𝑛 un entier naturel non nul. L’ensemble des entiers relatifs qui ont le même reste 𝑟 de la division
euclidienne par 𝑛 s’appelle la classe d’équivalence de 𝒓 et se note : 𝑟̅ ou 𝑟̇
𝑟̅ = {𝑚 ∈ ℤ / 𝑚 ≡ 𝑟 [𝑛]} = {𝑛𝑘 + 𝑟 𝑜ù 𝑘 ∈ ℤ}

Définition :
Soit 𝑛 un entier naturel non nul. On définit dans ℤ⁄𝒏ℤ les deux lois :
 L’addition : On pose : 𝑎̅ + 𝑏̅ = 𝑎̅̅̅̅̅̅̅
+𝑏
 La multiplication : On pose : 𝑎̅ × 𝑏̅ = ̅̅̅̅̅̅̅
𝑎×𝑏
Exemple :
Dans ℤ⁄6ℤ : 3̅ × 4̅ = 0̅ 5̅ + 4̅ = 3̅
Exercice :
1- Dresser les tables des opérations de ℤ⁄7ℤ
2- Résoudre dans ℤ⁄7ℤ les équations :
a) 2̅𝑥 = 1̅ b) 4̅𝑥 + 1̅ = 𝑥 + 3̅ c) 5̅𝑥 2 + 3̅𝑥 + 1̅ = 0̅
9) Décomposition d’un entier en facteurs des nombres premiers
Théorème :
 Chaque entier naturel 𝑚 non nul s’écrit d’une façon unique comme le produit des facteurs premiers
𝛼 𝛼 𝛼 𝛼 𝛼
comme suite : 𝑚 = 𝑝1 1 × 𝑝2 2 × 𝑝3 3 × … .× 𝑝𝑛 𝑛 = ∏𝑛𝑘=1 𝑝𝑘 𝑘
 Chaque entier relatif 𝑚 non nul s’écrit d’une façon unique comme le produit des facteurs premiers
𝛼 𝛼 𝛼 𝛼 𝛼
comme suite : 𝑚 = 𝜀 𝑝1 1 × 𝑝2 2 × 𝑝3 3 × … .× 𝑝𝑛 𝑛 = 𝜀 ∏𝑛𝑘=1 𝑝𝑘 𝑘 où 𝜀 ∈ {−1,1}

Propriété 1:
𝛼 𝛼 𝛼 𝛼
Soit 𝑎 un entier relatif dont la décomposition est de la forme : 𝑎 = 𝜀 𝑝1 1 × 𝑝2 2 × 𝑝3 3 × … .× 𝑝𝑛 𝑛 ; un entier 𝑑
non nul divise l’entier 𝑎 si et seulement si 𝑑 à une décomposition de la forme :
𝛿 𝛿 𝛿 𝛿
𝑑 = 𝜀′ 𝑝1 1 × 𝑝2 2 × 𝑝3 3 × … .× 𝑝𝑛 𝑛 où (∀𝑖 ∈ ⟦1, 𝑛⟧ )(0 ≤ 𝛿𝑖 ≤ 𝛼𝑖 )

𝛼 𝛼 𝛼 𝛼
Soit 𝑎 un entier relatif dont la décomposition est de la forme : 𝑎 = 𝜀 𝑝1 1 × 𝑝2 2 × 𝑝3 3 × … .× 𝑝𝑛 𝑛 et
𝛿 𝛿 𝛿 𝛿
𝑑 = 𝜀′ 𝑝1 1 × 𝑝2 2 × 𝑝3 3 × … .× 𝑝𝑛𝑛 un diviseur de 𝑎 le nombre des valeurs possibles de 𝛿𝑖 est 𝛼𝑖 + 1
On en déduit que :
Propriété 2:
𝛼 𝛼 𝛼 𝛼
Si 𝑎 = 𝜀 𝑝1 1 × 𝑝2 2 × 𝑝3 3 × … .× 𝑝𝑛 𝑛 est un entier, le nombre des diviseurs de 𝑎 est :
2(𝛼1 + 1)(𝛼2 + 1) … (𝛼𝑛 + 1)
Application :
1- Décomposer le nombre 2975 en facteurs des nombres premiers
4
L’arithmétique A.KARMIM
2- Déterminer le nombre des diviseurs de 2975.
3- Déterminer tous les diviseurs positifs de 2975.
Propriété 3 :
𝛼 𝛼 𝛼 𝛼
Soit 𝑎 un entier relatif dont la décomposition est de la forme : 𝑎 = 𝜀 𝑝1 1 × 𝑝2 2 × 𝑝3 3 × … .× 𝑝𝑛 𝑛 ; un entier 𝑚
𝜇 𝜇 𝜇 𝜇
est un multiple de 𝑎 si et seulement si 𝑚 = 𝜀′ 𝑝1 1 × 𝑝2 2 × 𝑝3 3 × … .× 𝑝𝑛 𝑛 où (∀𝑖 ∈ ⟦1, 𝑛⟧ )(𝛼𝑖 ≤ 𝜇𝑖 )

9.1 Le P.G.C.D de deux nombres.

𝛼 𝛽 𝛿
Soient 𝑎 = 𝜀 ∏𝑛𝑘=1 𝑝𝑘 𝑘 et 𝑏 = 𝜀′ ∏𝑛𝑘=1 𝑝𝑘 𝑘 deux entiers ; si 𝑑 = 𝜀" ∏𝑛𝑘=1 𝑝𝑘 𝑘 est un diviseur commun de 𝑎 et 𝑏 alors :
0 ≤ 𝛿𝑘 ≤ 𝛼𝑘
(∀𝑘 ∈ ⟦1, 𝑛⟧ ) {
0 ≤ 𝛿𝑘 ≤ 𝛽𝑘
𝛿
On en déduit que le 𝑃. 𝐺. 𝐷. 𝐶 (𝑎, 𝑏) est l’entier 𝛿 = ∏𝑛𝑘=1 𝑝𝑘 𝑘 où (∀𝑘 ∈ ⟦1, 𝑛⟧ )(𝛿𝑘 = inf(𝛼𝑘 , 𝛽𝑘 ))
Propriété :
𝛼 𝛽 inf(𝛼𝑘 ,𝛽𝑘 )
Si 𝑎 = 𝜀 ∏𝑛𝑘=1 𝑝𝑘 𝑘 et 𝑏 = 𝜀′ ∏𝑛𝑘=1 𝑝𝑘 𝑘 deux entiers alors 𝑎 ∧ 𝑏 = ∏𝑛𝑘=1 𝑝𝑘

Exercice :
1- Décomposer les nombres 362154 et 82350 en produit des facteurs premiers
2- Déterminer le P.G.C.D de 362154 et 82350
3- Déterminer tous les diviseurs communs de 362154 et 82350
9.2 Le P.P.C.M de deux nombres.
𝛼 𝛽 𝜇
Soient 𝑎 = 𝜀 ∏𝑛𝑘=1 𝑝𝑘 𝑘 et 𝑏 = 𝜀′ ∏𝑛𝑘=1 𝑝𝑘 𝑘 deux entiers ; si 𝑚 = 𝜀" ∏𝑛𝑘=1 𝑝𝑘 𝑘 est un multiple commun de 𝑎 et 𝑏 alors :
𝛼 ≤ 𝜇𝑘
(∀𝑘 ∈ ⟦1, 𝑛⟧ ) { 𝑘
𝛽 ≤ 𝜇𝑘
𝜇
On en déduit que le 𝑃. 𝑃. 𝐶. 𝑀 (𝑎, 𝑏) est l’entier 𝜇 = ∏𝑛𝑘=1 𝑝𝑘 𝑘 où (∀𝑘 ∈ ⟦1, 𝑛⟧ )(𝜇𝑘 = sup(𝛼𝑘 , 𝛽𝑘 ))
Propriété :
𝛼 𝛽 sup(𝛼𝑘 ,𝛽𝑘 )
Si 𝑎 = 𝜀 ∏𝑛𝑘=1 𝑝𝑘 𝑘 et 𝑏 = 𝜀′ ∏𝑛𝑘=1 𝑝𝑘 𝑘 deux entiers alors 𝑎 ∨ 𝑏 = ∏𝑛𝑘=1 𝑝𝑘

Propriété :
Soient 𝑎 et 𝑏 deux entiers relatifs non nuls, on a les assertions suivantes :
 (𝑎 ∧ 𝑏) × (𝑎 ∨ 𝑏) = |𝑎𝑏|
 𝑐𝑎 ∨ 𝑐𝑏 = 𝑐(𝑎 ∨ 𝑏)
 𝑐𝑎 ∧ 𝑐𝑏 = 𝑐(𝑎 ∧ 𝑏)
Exercice :
Si 𝑑|𝑎 et 𝑑|𝑏 alors : 𝑑|(𝑎 ∧ 𝑏).

II) THEOREMES PRINCIPAUX.

1) Théorème de Bézout :
Théorème 1 :
Soient 𝑎 et 𝑏 et des entiers relatifs non nuls :
𝑎 = 𝛼𝑑
2
𝑎 ∧ 𝑏 = 𝑑 ⟺ ∃(𝛼, 𝛽) ∈ ℤ ; { 𝑏 = 𝛽𝑑
𝛼∧𝛽 =1
Preuve :
(⇒) On suppose que 𝑎 ∧ 𝑏 = 𝑑
On a 𝑑|𝑎 et 𝑑|𝑏 donc ∃(𝛼, 𝛽) ∈ ℤ2 tel que : 𝑎 = 𝛼𝑑 et 𝑏 = 𝛽𝑑 donc :
𝑑 = 𝛼𝑑 ∧ 𝛽𝑑
= |𝑑|(𝛼 ∧ 𝛽) et puisque 𝑑 ∈ ℕ∗ alors 𝛼 ∧ 𝛽 = 1
𝑎 = 𝛼𝑑
2
(⇐) On suppose que ∃(𝛼, 𝛽) ∈ ℤ ; { 𝑏 = 𝛽𝑑 On a :
𝛼∧𝛽 =1
𝑎 ∧ 𝑏 = 𝛼𝑑 ∧ 𝛽𝑑 = |𝑑|( 𝛼 ∧ 𝛽) = 𝑑 car (|𝑑| = 𝑑 et 𝛼 ∧ 𝛽 = 1)

5
L’arithmétique A.KARMIM
Théorème 2 :
Soient 𝑎 et 𝑏 et des entiers relatifs non nuls : 𝑎 ∧ 𝑏 = 𝑑 ⇒ ∃(𝑢, 𝑣) ∈ ℤ2 ; 𝑑 = 𝑎𝑢 + 𝑏𝑣

Preuve :
1- Si 𝑎|𝑏 alors 𝑎 ∧ 𝑏 = |𝑏|
 si 𝑏 > 0 alors 𝑏 = 0𝑎 + 1𝑏
 si 𝑏 < 0 alors 𝑏 = 0𝑎 + (−1)𝑏
2- Si 𝑏|𝑎 (même raisonnement)
3- On suppose que 𝑏 ∤ 𝑎 tel que 0 < 𝑏 < 𝑎
d’après l’algorithme d’Euclide on a
𝑎 = 𝑏𝑞0 + 𝑟0 si 𝑟0 ≠ 0 alors :
𝑏 = 𝑟0 𝑞1 + 𝑟1 si 𝑟1 ≠ 0 alors :
𝑟0 = 𝑟1 𝑞2 + 𝑟2 si 𝑟2 ≠ 0 alors :
…….
𝑟𝑛−2 = 𝑟𝑛−1 𝑞𝑛 + 𝑟𝑛 si 𝑟𝑛 ≠ 0 alors :
𝑟𝑛−1 = 𝑟𝑛 𝑞𝑛+1 + 𝑟𝑛+1 si 𝑟𝑛+1 = 0 on arrête le processus .
Et d’après la propriété précédente : 𝑎 ∧ 𝑏 = 𝑏 ∧ 𝑟1 = 𝑟1 ∧ 𝑟2 = ⋯ = 𝑟𝑛−1 ∧ 𝑟𝑛 = 𝑟𝑛 car : 𝑟𝑛 |𝑟𝑛−1
et 0 < 𝑟𝑛 < 𝑟𝑛−1 < ⋯ < 𝑟1 < 𝑟0 < 𝑏
On obtient :
𝑟0 = 𝑎 − 𝑏𝑞0 = 𝑢0 𝑎 + 𝑣0 𝑏 où 𝑢0 = 1 et 𝑣0 = −𝑞
𝑟1 = 𝑏 − 𝑟0 𝑞1 = 𝑏 − (𝑎 − 𝑏𝑞0 )𝑞1 = −𝑎𝑞1 + 𝑏(1 + 𝑞0 𝑞1 ) = 𝑢1 𝑎 + 𝑣1 𝑏 où 𝑢1 = −𝑞1 et 𝑣1 = (1 + 𝑞0 𝑞1 )
On répète le processus et à chaque fois on montre que : 𝑟𝑘 = 𝑎𝑢𝑘 + 𝑏𝑢𝑘 cette opération est valable pour tous les reste
𝑟𝑘 en particulier pour le dernier reste 𝑟𝑛 qui est 𝑎 ∧ 𝑏 donc : ∃(𝑢𝑛 , 𝑣𝑛 ) ∈ ℤ2 ; 𝑎 ∧ 𝑏 = 𝑎𝑢𝑛 + 𝑏𝑣𝑛 .
Remarque
 Dans l’écriture ∃(𝑢, 𝑣) ∈ ℤ2 ; 𝑎 ∧ 𝑏 = 𝑎𝑢 + 𝑏𝑣 le couple (𝑢, 𝑣) n’est pas unique.
12 ∧ 9 = 3 on a 3 = 1 × 12 + (−1) × 9 et 3 = (−2) × 12 + 3 × 9
 La réciproque du théorème n’est pas vraie :
2 × 12 + (−2) × 9 = 6 mais 12 ∧ 9 = 3 ≠ 6

Théorème (Théorème de Bézout)

Soient 𝑎 et 𝑏 et des entiers relatifs non nuls : 𝑎 ∧ 𝑏 = 1 ⟺ ∃(𝑢, 𝑣) ∈ ℤ2 ; 1 = 𝑎𝑢 + 𝑏𝑣

(⇒) C’est le théorème précèdent.

(⇐) On suppose que 1 = 𝑎𝑢 + 𝑏𝑣
𝑑|𝑎 𝑑|𝑢𝑎
Soit 𝑑 = 𝑎 ∧ 𝑏 on aura : { donc { par suite 𝑑|𝑢𝑎 + 𝑣𝑏 = 1 donc 𝑑 = 1 (𝑑 ∈ ℕ∗ )
𝑑|𝑏 𝑑|𝑣𝑏
et donc 𝑎 ∧ 𝑏 = 1

Exemples :
 (5𝑛 + 3) ∧ (2𝑛 + 1) = 1 car : 2 × (5𝑛 + 3) + (−5) × (2𝑛 + 1) = 1
 (𝑛 + 2) ∧ (𝑛2 + 2𝑛 − 1) = 1 car 𝑛 × (𝑛 + 2) + (−1) × (𝑛2 + 2𝑛 − 1) = 1

Application :
L’utilisation de l’algorithme d’Euclide pour déterminer les coefficients de 𝐵𝑒𝑧𝑜𝑢𝑡
Montrons que : 360 ∧ 84 = 12 et déterminons 𝑢 et 𝑣 dans ℤ tels que 360𝑢 + 84𝑣 = 12
on a : 360 = 23 . 32 . 5 et 84 = 22 . 3.7 donc 360 ∧ 84 = 22 . 3 = 12
D’autre part :
360 = 84 × 4 + 24 24 = 𝑎 − (𝑏 × 4)

24
84 = 24 × 3 + 12 ⏞− (𝑏 × 4)) × 3 = 12
𝑏 − (𝑎

6
L’arithmétique A.KARMIM
24 = 12 × 2 + 0
Donc : −3𝑎 + 13𝑏 = 12
 Considérons dans ℤ² l’équation (𝐸): 17𝑥 + 36𝑦 = 1 et détérminons une solution particulière de (𝐸).
On a 17 ∧ 36 = 1 donc d’après le théorème de 𝐵é𝑧𝑜𝑢𝑡 ; il existe 𝑢 et 𝑣 tels que : 17𝑢 + 36𝑣 = 1 donc (𝐸) admet une
solution.
On pose 𝑎 = 36 et 𝑏 = 17 on obtient :
𝑎 = 2𝑏 + 2
𝑏 =8×2+1
Donc : 2 = 𝑎 − 2𝑏 et 𝑏 = 8 × (𝑎 − 2𝑏) + 1
D’où : −8𝑎 + 17𝑏 = 1 donc le couple (−8,17) est une solution de l’équation (𝐸).

2) Application du théorème de Bézout :

Théorème de Gauss
𝑐|𝑎𝑏
Soient 𝑎, 𝑏 et 𝑐 des entiers relatifs non nuls : { ⇒ 𝑐|𝑎
𝑐∧𝑏 =1

Preuve :
On a : 𝑐 ∧ 𝑎 = 1 d’après le théorème de Bézout : (∃(𝑢, 𝑣) ∈ ℤ2 )(𝑎𝑢 + 𝑣𝑐 = 1) d’où 𝑏𝑎𝑢 + 𝑏𝑣𝑐 = 𝑏
Et puis que 𝑐|𝑎𝑏 alors 𝑎𝑏 = 𝑘𝑐 (où 𝑘 ∈ ℤ) donc 𝑘𝑐𝑢 + 𝑏𝑣𝑐 = 𝑏 d’où 𝑐(𝑘𝑢 + 𝑏𝑣) = 𝑏 et 𝑘𝑢 + 𝑏𝑣 ∈ ℤ donc 𝑐|𝑏.

Remarque :
La condition 𝑐 ∧ 𝑏 = 1dans le théorème de Gauss est indispensable ; 6|4 × 3 mais 6 ∤ 3 et 6 ∤ 4

Théorème
𝑎|𝑐 et 𝑏|𝑐
Soient 𝑎, 𝑏 et 𝑐 des entiers relatifs non nuls : { ⇒ 𝑎𝑏|𝑐
𝑎∧𝑏 =1

Preuve :
On a : 𝑎|𝑐 et 𝑏|𝑐 donc ils existent 𝑘 et ℎ tels que : 𝑐 = 𝑘𝑎 = ℎ𝑏 et puisque 𝑎 ∧ 𝑏 = 1 alors :
(∃(𝑢, 𝑣) ∈ ℤ2 )(𝑎𝑢 + 𝑣𝑏 = 1)
Donc : (on multipliant par 𝑐) 𝑐 = 𝑐𝑎𝑢 + 𝑐𝑣𝑏
= ℎ𝑏𝑎𝑢 + 𝑘𝑎𝑣𝑏
= 𝑎𝑏(ℎ𝑢 + 𝑘𝑣) et par suite 𝑎𝑏|𝑐
Remarque :
La condition 𝑐 ∧ 𝑏 = 1dans le théorème précèdent est indispensable ; 6|12 et 3|12 mais 6 × 3 = 18 ∤ 12.

Propriétés :
Soient 𝑎, 𝑏 et 𝑐 des entiers relatifs non nuls :
𝑎∧𝑏 =1
{ ⟺ 𝑎 ∧ 𝑏𝑐 = 1  𝑎 ∧ 𝑏 = 1 ⟺ 𝑎 ∧ 𝑏𝑛 = 1  𝑎 ∧ 𝑏 = 1 ⟺ 𝑎𝑛 ∧ 𝑏 𝑚 = 1 (𝑛 ∈ ℕ∗ )
𝑎∧𝑐 =1

Preuve :

𝑎∧𝑏 =1 (∃(𝑢, 𝑣) ∈ ℤ2 )(𝑎𝑢 + 𝑣𝑏 = 1)
(⇒) On suppose que { donc : {
𝑎∧𝑐 =1 (∃(𝛼, 𝛽) ∈ ℤ2 )(𝑎𝛼 + 𝛽𝑐 = 1)
Par le produit on obtient : (𝑎𝑢 + 𝑣𝑏)(𝑎𝛼 + 𝛽𝑐) = 1 ; d’où après développement on obtient :
𝑎2 𝑢𝛼 + 𝑎𝑢𝛽𝑐 + 𝑣𝑏𝑎𝛼 + 𝑣𝑏𝛽𝑐 = 1 et donc (𝑎𝑢𝛼 + 𝑢𝛽𝑐 + 𝑣𝑏𝛼)𝑎 + (𝑣𝛽)𝑏𝑐 = 1 donc et d’après Bézout 𝑎 ∧ 𝑏𝑐 = 1

(⇐) On suppose que 𝑎 ∧ 𝑏𝑐 = 1 donc (∃(𝑢, 𝑣) ∈ ℤ2 )(𝑎𝑢 + 𝑣𝑏𝑐 = 1)

D’où 𝑎𝑢 + (𝑣𝑏)𝑐 = 1 donc 𝑎 ∧ 𝑐 = 1 et 𝑎𝑢 + (𝑣𝑐)𝑏 = 1 donc 𝑎 ∧ 𝑏 = 1

7
L’arithmétique A.KARMIM

(⇒) On suppose que 𝑎 ∧ 𝑏 = 1 et on montre par récurrence que : 𝑎 ∧ 𝑏 𝑛 = 1
 Pour 𝑛 = 1 la propriété est vraie.
 On suppose que la propriété est vraie pour 𝑛
 On montre qu’elle est vraie pour 𝑛 + 1
𝑎 ∧ 𝑏𝑛 = 1
On a : { donc et d’après  on a : 𝑎 ∧ 𝑏𝑏 𝑛 = 1 d’où 𝑎 ∧ 𝑏 𝑛+1 = 1
𝑎∧𝑏 =1
Donc si 𝑎 ∧ 𝑏 = 1 alors 𝑎 ∧ 𝑏 𝑛 = 1 pour tout 𝑛 dans ℕ∗ .
(⇐)
On suppose que 𝑎 ∧ 𝑏 𝑛 = 1 donc et d’près le théorème de Bézout (∃(𝑢, 𝑣) ∈ ℤ2 )(𝑎𝑢 + 𝑣𝑏 𝑛 = 1)
Donc : 𝑎𝑢 + (𝑣𝑏 𝑛−1 )𝑏 = 1 donc (∃(𝑢′ , 𝑣 ′ ) ∈ ℤ2 )(𝑎𝑢′ + 𝑣′𝑏 = 1) et par suite 𝑎 ∧ 𝑏 = 1

 Est un résultat immédiat de .

3) L’équation 𝒂𝒙 + 𝒃𝒚 = 𝒄
Théorème : (fondamental)
L’équation (𝐸) : 𝑎𝑥 + 𝑏𝑦 = 𝑐 admet une solution si et seulement si (𝑎 ∧ 𝑏)|𝑐

Preuve :
 On suppose que 𝑑 = (𝑎 ∧ 𝑏)|𝑐 alors : (∃𝑘 ∈ ℤ)(𝑐 = 𝑘𝑑) et on a : (∃(𝑢, 𝑣) ∈ ℤ2 )(𝑎𝑢 + 𝑣𝑏 = 𝑑)
𝑘𝑑 = 𝑘(𝑎 ∧ 𝑏) = (𝑘𝑢)𝑎 + (𝑘𝑣)𝑏
𝑥 = 𝑘𝑢
C’est-à-dire : 𝑐 = (𝑘𝑢)𝑎 + (𝑘𝑣)𝑏 donc l’équation (𝐸) admet (𝑥0 , 𝑦0 ) comme solution où { 0
𝑦0 = 𝑘𝑣
 In versement : On suppose que : 𝑎𝑥 + 𝑏𝑦 = 𝑐 admet une solution (𝑥0 , 𝑦0 ), donc :
(𝑎 ∧ 𝑏)|𝑎 (𝑎 ∧ 𝑏)|𝑥0 𝑎
𝑎𝑥0 + 𝑏𝑦0 = 𝑐 puisque : { alors { donc (𝑎 ∧ 𝑏)|( 𝑎𝑥0 + 𝑏𝑦0 ) = 𝑐 donc : (𝑎 ∧ 𝑏)|𝑐.
(𝑎 ∧ 𝑏)|𝑏 (𝑎 ∧ 𝑏)|𝑦0 𝑏

Théorème :
Si le couple (𝑥0 , 𝑦0 ) est une solution de l’équation (𝐸) : 𝑎𝑥 + 𝑏𝑦 = 𝑐 alors, l’ensemble des solutions de (𝐸)
𝑘𝑏 𝑘𝑎
est : 𝑆 = {(𝑥0 + 𝑎∧𝑏 , 𝑦0 − 𝑎∧𝑏) / 𝑘 ∈ ℤ}

Démonstration :
𝑘𝑏 𝑘𝑎 𝐴⊂𝑆
On pose : 𝐴 = {(𝑥0 + 𝑎∧𝑏 , 𝑦0 − 𝑎∧𝑏) / 𝑘 ∈ ℤ} et on montre que {
𝑆⊂𝐴
𝑘𝑏 𝑘𝑎
 Montrons que 𝐴 ⊂ 𝑆 : il suffit de montrer que le couple (𝑥0 + 𝑎∧𝑏 , 𝑦0 − 𝑎∧𝑏) est solution de l’équation (𝐸) :
𝑘𝑏 𝑘𝑎 𝑎𝑘𝑏 𝑏𝑘𝑎
On a : 𝑎 (𝑥0 + 𝑎∧𝑏) + 𝑏 (𝑦0 − 𝑎∧𝑏) = 𝑎𝑥0 + 𝑎∧𝑏 + 𝑏𝑦0 − 𝑎∧𝑏
= 𝑎𝑥0 + 𝑏𝑦0 = 𝑐
𝑘𝑏 𝑘𝑎
Donc le couple (𝑥0 + ,𝑦
𝑎∧𝑏 0
− 𝑎∧𝑏) (pour 𝑘 ∈ ℤ) est solution : d’où : 𝐴 ⊂ 𝑆.
 Inversement : On suppose que le couple (𝑥, 𝑦) ∈ 𝑆
Donc (𝑥, 𝑦) es solution de l’équation (𝐸) d’où 𝑎𝑥 + 𝑏𝑦 = 𝑐 ; or : (𝑥0 , 𝑦0 ) est une solution de l’équation (𝐸) ,
donc : 𝑎𝑥0 + 𝑏𝑦0 = 𝑐 donc (différence membre à membre) 𝑎(𝑥 − 𝑥0 ) = −𝑏(𝑦 − 𝑦0 )
𝑎 = 𝛼𝑑 et 𝑏 = 𝛽𝑑
Soit 𝑑 = 𝑎 ∧ 𝑏 on a : (∃(𝛼, 𝛽) ∈ ℤ2 ) {
𝛼∧𝛽 =1
Donc :
(𝑥, 𝑦) ∈ 𝑆 ⟺ 𝑎(𝑥 − 𝑥0 ) = −𝑏(𝑦 − 𝑦0 )
⟺ 𝛼𝑑(𝑥 − 𝑥0 ) = −𝛽𝑑(𝑦 − 𝑦0 )
⟺ 𝛼(𝑥 − 𝑥0 ) = −𝛽(𝑦 − 𝑦0 ) (*) (𝑑 ≠ 0)
On conclut que : 𝛽| 𝛼(𝑥 − 𝑥0 ) et puisque : 𝛼 ∧ 𝛽 = 1 alors (d’après T. Gauss) 𝛽|(𝑥 − 𝑥0 )
Donc (∃𝑘 ∈ ℤ)((𝑥 − 𝑥0 ) = 𝑘𝛽) et par suite : (*) 𝛼𝑘𝛽 = −𝛽(𝑦 − 𝑦0 ) d’où : 𝑦 − 𝑦0 = −𝑘𝛼
𝑎
(𝑦 − 𝑦0 ) = −𝑘𝛼 𝛼 par
𝑑
Par suite : (𝑥, 𝑦) ∈ 𝑆 ⟺ { où 𝑘 ∈ ℤ en remplaçant { 𝑏 on obtient :
(𝑥 − 𝑥0 ) = 𝑘𝛽 𝛽 par
𝑑
8
L’arithmétique A.KARMIM
𝑘𝑏 𝑘𝑎
(𝑥, 𝑦) ∈ 𝑆 ⟺ 𝑥 = 𝑥0 + 𝑑 𝑒𝑡 𝑦 = 𝑦0 − C.Q.F.D.
𝑑

Exemple :
Considérons l’équation (𝐸): 756𝑥 − 245𝑦 = 14
1- Montrer l’équation (𝐸) admet une solution.
2- Déterminer une solution particulière de (𝐸)
3- Résoudre l’équation (𝐸)

Solution :
756 = 22 × 33 × 7 et 245 = 5 × 7²
1- On a : 756 ∧ 245 = 7 et 7|14 donc l’équation (𝐸) admet une solution dans ℤ².
2- En utilisant l’algorithme d’Euclide on obtient 𝑎 = 756 et 𝑏 = 245
𝑎 = 3 × 𝑏 + 21
𝑏 = 11 × 21 + 14
21 = 14 + 7
On a donc :
21 = 𝑎 − 3𝑏
𝑏 = 11 × (𝑎 − 3𝑏) + 14 ⟺ 14 = 34𝑏 − 11𝑎
7 = (𝑎 − 3𝑏) − (34𝑏 − 11𝑎) ⟺ 7 = 12𝑎 − 37𝑏
Finalement :
14 = 24𝑎 − 74𝑏 et donc le couple (24,74) est une solution particulière de (𝐸) d’où
𝑘×245 𝑘×756
𝑆 = {(24 − , 74 − )/ 𝑘 ∈ ℤ} = {(24 − 35𝑘, 74 − 108𝑘)/ 𝑘 ∈ ℤ} = {(24 + 35𝑘, 74 + 108𝑘)/ 𝑘 ∈ ℤ}
7 7

4) La congruence modulo 𝒏 ,complément.

Théorème :
𝑛
Soient 𝑎, 𝑏 et 𝑐 des entiers relatifs non nuls. et 𝑛 ∈ ℕ∗ et 𝑑 = 𝑛 ∧ 𝑐 on a : 𝑎𝑐 ≡ 𝑏𝑐 [𝑛] ⟺ 𝑎 ≡ 𝑏 [𝑑]
Preuve :
(⇒)
𝑛 𝑐 𝑛 𝑐
On suppose : 𝑎𝑐 ≡ 𝑏𝑐 [𝑛], donc 𝑛|(𝑎𝑐 − 𝑏𝑐) = 𝑐(𝑎 − 𝑏) donc | (𝑎 − 𝑏) et comme ∧ = 1
𝑑 𝑑 𝑑 𝑑
Alors :( D’après théorème de Gauss)
𝑛 𝑛
𝑑
|(𝑎 − 𝑏) donc : 𝑎 ≡ 𝑏 [𝑑]
(⇐)
𝑛 𝑛
On suppose que : 𝑎 ≡ 𝑏 [𝑑] donc 𝑎 = 𝑏 + 𝑘 𝑑 (𝑘 ∈ ℤ) donc 𝑑𝑎 = 𝑑𝑏 + 𝑘𝑛 (𝑑 = 𝑛 ∧ 𝑐 ⇒ 𝑐 = 𝛼𝑑 )
Donc : 𝛼𝑑𝑎 = 𝛼𝑑𝑏 + 𝛼𝑘𝑛 d’où 𝑐𝑎 = 𝑐𝑏 + ℎ𝑛 donc 𝑎𝑐 ≡ 𝑏𝑐 [𝑛].

Propriété :
𝑎𝑐 ≡ 𝑏𝑐 [𝑛] 𝑎 ≡ 𝑏 [𝑛] 𝑎𝑐 ≡ 𝑏𝑐 [𝑝]
{ ⇒ 𝑎 ≡ 𝑏 [𝑛]  { ⇒ 𝑎 ≡ 𝑏 [𝑚] { ⇒ 𝑎 ≡ 𝑏 [𝑚]
𝑐∧𝑛 =1 𝑚|𝑛 𝑝 premier et 𝑝 ∤ 𝑐
Preuve :
Ce sont des résultats immédiats du théorème précédent.
5) Le P.G.D.C et le P.P.M.C de plusieurs nombres.
Définition :
Soient 𝑎1 , 𝑎2 , … , 𝑎𝑛 des entiers relatifs non nuls, le plus grand entier naturel 𝑑 qui divise en même temps tous
les nombres 𝑎1 , 𝑎2 , … , 𝑎𝑛 s’appelle le plus grand diviseur commun des nombres 𝑎1 , 𝑎2 , … , 𝑎𝑛 et se note :
𝑑 = 𝑎1 ∧ 𝑎2 ∧ … ∧ 𝑎𝑛

Théorème :
Soient 𝑎1 , 𝑎2 , … , 𝑎𝑛 des entiers relatifs non nuls ; on a :
𝑎1 ∧ 𝑎2 ∧ … ∧ 𝑎𝑛 = (𝑎1 ∧ 𝑎2 ∧ … ∧ 𝑎𝑛−2 ) ∧ (𝑎𝑛−1 ∧ 𝑎𝑛 )

9
L’arithmétique A.KARMIM
Exemple :
756 ∧ 350 ∧ 616 = 756 ∧ (350 ∧ 616) = 756 ∧ 14 = 14
Théorème (𝐺é𝑛é𝑟𝑎𝑙𝑖𝑠𝑎𝑡𝑖𝑜𝑛 𝑑𝑒 𝐵é𝑧𝑜𝑢𝑡)
Si 𝑑 = 𝑎1 ∧ 𝑎2 ∧ … ∧ 𝑎𝑛 alors ∃(𝛼𝑖 )1≤𝑖≤𝑛 telle que : 𝑑 = ∑𝑛𝑖=1 𝛼𝑖 𝑎𝑖
Preuve : par récurrence

Définition :
On dit que les entiers relatifs non nuls 𝑎1 , 𝑎2 , … , 𝑎𝑛 sont premiers entre eux si 𝑎1 ∧ 𝑎2 ∧ … ∧ 𝑎𝑛 = 1

Remarque :
Les entiers relatifs non nuls 𝑎1 , 𝑎2 , … , 𝑎𝑛 sont premiers entre eux ne veut pas dire que les entiers 𝑎1 , 𝑎2 , … , 𝑎𝑛 sont
premiers entre eux deux à deux.

Exemple :
3, 5 et 6 sont premiers entre eux.

Théorème (𝐺é𝑛é𝑟𝑎𝑙𝑖𝑠𝑎𝑡𝑖𝑜𝑛 𝑑𝑒 𝐵é𝑧𝑜𝑢𝑡)

Si 𝑎1 ∧ 𝑎2 ∧ … ∧ 𝑎𝑛 = 1 si et seulement si ∃(𝑢𝑖 )1≤𝑖≤𝑛 telle que : 1 = ∑𝑛𝑖=1 𝑢𝑖 𝑎𝑖

Définition :
Soient 𝑎1 , 𝑎2 , … , 𝑎𝑛 des entiers relatifs non nuls, le plus petit entier naturel 𝑚 qui est multiple en même temps
tous les nombres 𝑎1 , 𝑎2 , … , 𝑎𝑛 s’appelle le plus grand diviseur commun des nombres 𝑎1 , 𝑎2 , … , 𝑎𝑛 et se note :
𝑑 = 𝑎1 ∨ 𝑎2 ∨ … ∨ 𝑎𝑛

6) Propriétés des nombres premiers.

Théorème :
 Si 𝑝 et 𝑞 sont des nombres premiers positifs alors ils sont premier entre eux.
 Si 𝑝 est premier alors il est premier avec tout nombre entier non nul 𝑎 tel que 𝑝 ∤ 𝑎

Preuve : En exercice.
Remarque :
La réciproque de  n’est pas vrais ; 14 et 9 sont premiers entre eux mais aucun d’eux n’est premiers.

Propriétés :
𝑝 premier
𝑝 premier 𝑝 premier
 { 𝑝|𝑎𝑏 ⇒ 𝑝|𝑏 { ⇒ 𝑝|𝑎 ou 𝑝|𝑏 { ⇒ ∃𝑖 ∈ {1,2, . . , 𝑛} 𝑝|𝑎𝑖
𝑝|𝑎𝑏 𝑝|𝑎1 𝑎2 … 𝑎𝑛
𝑝∤𝑎

∀𝑖 ∈ {1,2, … , 𝑛}; 𝑝𝑖 premier

{ 𝑝 premier ⇒ ∃𝑖 ∈ {1,2, . . , 𝑛} 𝑝 = 𝑝𝑖
𝑝|𝑝1 𝑝2 … 𝑝𝑛

Preuve : Résultat du théorème de Gauss.

7) Le petit théorème de Fermat.

Théorème :
Si 𝑝 est un nombre premier et 𝑎 un entier relatif non nul et pas divisible par 𝑝 alors :𝑎𝑝−1 − 1 est divisible par
𝑝 c’est-à-dire 𝑎𝑝−1 ≡ 1 [𝑝] ou encore : 𝑎𝑝 ≡ 𝑎 [𝑝]

10
L’arithmétique A.KARMIM
Preuve :
Soient 𝑝 un nombre premier et 𝑘 un entier naturel tel que 1 ≤ 𝑘 ≤ 𝑝 − 1
On a 𝑝 premier et 𝑝 > 𝑘 donc 𝑝 ∤ 𝑘 et par suite 𝑝 ∧ 𝑘 = 1 d’autre part :
𝑝! 𝑝 × (𝑝 − 1)! 𝑘−1
𝑘𝐶𝑝𝑘 = 𝑘 = = 𝑝𝐶𝑝−1
𝑘! (𝑝 − 𝑘)! (𝑘 − 1)! (𝑝 − 𝑘)!
Donc 𝑝|𝑘𝐶𝑝𝑘 et comme 𝑝 ∧ 𝑘 = 1 alors d’après T. Gauss 𝑝|𝐶𝑝𝑘
Montrons que 𝑝|(𝑎 + 1)𝑝 − 𝑎𝑝 − 1
𝑝−1
On a d’près la formule de binôme On a : (𝑎 + 1)𝑝 = 𝑎𝑝 + 𝐶𝑝1 𝑎𝑝−1 + 𝐶𝑝2 𝑎𝑝−2 + ⋯ + 𝐶𝑝 𝑎 + 1
𝑝−1
Donc (𝑎 + 1)𝑝 − 𝑎𝑝 − 1 = 𝐶𝑝1 𝑎𝑝−1 + 𝐶𝑝2 𝑎𝑝−2 + ⋯ + 𝐶𝑝 𝑎
Et comme 𝑝|𝐶𝑝𝑘 pour 1 ≤ 𝑘 ≤ 𝑝 − 1 alors 𝑝|(𝑎 + 1)𝑝 − 𝑎𝑝 − 1
On a donc : (𝑎 + 1)𝑝 − 1 ≡ 𝑎𝑝 [𝑝].
Montrons par récurrence sur 𝑎 (On prend pour le moment 𝑎 ∈ ℕ) que 𝑎𝑝 ≡ 𝑎 [𝑝]
 Pour 𝑎 = 0 la propriété est vraie car 0𝑝 = 0 ≡ 0 [𝑝]
 On suppose que la propriété est vraie pour 𝑎 c’est-à-dire 𝑎𝑝 ≡ 𝑎 [𝑝]
 Montrons que le propriété est vraie pour (𝑎 + 1) c’est-à-dire (𝑎 + 1)𝑝 ≡ 𝑎 + 1 [𝑝]
On a : d’après les questions précédente (𝑎 + 1)𝑝 ≡ 𝑎𝑝 + 1 [𝑝].
Or d’après H.R 𝑎𝑝 ≡ 𝑎 [𝑝] donc : (𝑎 + 1)𝑝 ≡ 𝑎 + 1 [𝑝].
Donc (∀𝑎 ∈ ℕ)(∀𝑝 ∈ ℙ)(𝑎𝑝 ≡ 𝑎 [𝑝])
Si 𝑎 < 0 alors −𝑎 > 0
o Si 𝑝 = 2 on aura 𝑎2 = (−𝑎)2 ≡ (−𝑎) [2] et −𝑎 ≡ 𝑎 [2] car (2|(𝑎 − (−𝑎)) = 2𝑎)
o si 𝑝 ≥ 3 alors 𝑝 est impaire et (−𝑎)𝑝 = −𝑎𝑝 et (−𝑎)𝑝 ≡ (−𝑎) [𝑝] on en déduit que −𝑎𝑝 ≡ −𝑎 [𝑝] et
finalement 𝑎𝑝 ≡ 𝑎 [𝑝]
D’où le théorème.
Exemple :
Montrons que : (∀𝑛 ≥ 2) 𝑛5 ≡ 𝑛 [30]
On a : d’après le petit théorème de Fermat : 𝑛5 ≡ 𝑛 [5]
Donc 5|𝑛5 − 𝑛
D’autre part : 𝑛5 − 𝑛 = 𝑛(𝑛4 − 1) = 𝑛(𝑛2 − 1)(𝑛2 + 1) = 𝑛(𝑛 − 1)(𝑛 + 1)(𝑛2 + 1)
Donc 2|𝑛(𝑛 − 1) et 3|(𝑛 − 1)𝑛(𝑛 + 1) et puisque 2 et 3 sont premiers alors 6 = (2 × 3)|𝑛5 − 𝑛
Finalement :
5 5
{6|𝑛 − 𝑛 et 5|𝑛 − 𝑛 ⇒ (30|𝑛5 − 𝑛)
6∧5=1

Exercices
 Soient 𝑝 et 𝑞 deux nombres premiers distincts ; montrer que 𝑝𝑞−1 + 𝑞 𝑝−1 ≡ 1 [𝑝𝑞]
 Considérons dans ℤ l’équation (𝐸): 𝑥 4 + 781 = 3𝑦 4 et soit 𝑆 son ensemble de solution :
1- Montrer que (∀𝑥 ∈ ℤ)(𝑥 4 ≡ 1 [5] ou 𝑥 4 ≡ 0 [5])
2- Montrer que (∀𝑥 ∈ ℤ)(𝑥 4 + 781 ≡ 2 [5] ou 𝑥 4 + 781 ≡ 1 [5])
3- Déterminer l’ensemble 𝑆.
Remarque :
La réciproque du théorème de Fermat n’est pas vraie : 725 ≡ 1 [24] mais 25 n’est pas premier.

11
L’arithmétique A.KARMIM

III) SYSTEMES DE NUMERATION

1) Théorème et définition
Théorème :
Soit 𝑏 un entier naturel tel que : 𝑏 > 1
Chaque entier naturel non nul 𝑛 s’écrit d’une façon unique de la forme :
𝑛 = 𝑎𝑚 𝑏 𝑚 + 𝑎𝑚−1 𝑏𝑚−1 + ⋯ + 𝑎1 𝑏 + 𝑎0
Où : les (𝑎𝑖 )1≤𝑖≤𝑛 sont des entiers naturel 0 ≤ 𝑎𝑖 ≤ 𝑏 − 1 et 𝑎𝑚 ≠ 0

Preuve :
En utilisant la division Euclidienne de 𝑛 sur 𝑏 on obtient : 𝑛 = 𝑞1 𝑏 + 𝑎0 où 0 ≤ 𝑎0 < 𝑏
o Si 𝑞1 ≤ 𝑏 − 1 on s’arrête et 𝑎1 = 𝑞1
o si 𝑞1 ≥ 𝑏 , On effectue une autre division Euclidienne de 𝑞1 sur 𝑏 on obtient : 𝑞1 = 𝑞2 𝑏 + 𝑎1
et par suite 𝑛 = (𝑞2 𝑏 + 𝑎1 )𝑏 + 𝑎0 = 𝑞2 𝑏2 + 𝑎1 𝑏 + 𝑎0 .
 Si 𝑞2 ≤ 𝑏 − 1 on s’arrête et 𝑎2 = 𝑞2
 Si non on continue le processus

Notation :
Si 𝑛 = 𝑎𝑚 𝑏 𝑚 + 𝑎𝑚−1 𝑏𝑚−1 + ⋯ + 𝑎1 𝑏 + 𝑎0 on écrit : 𝑛 = ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
𝑎𝑚 𝑎𝑚−1 … . 𝑎 𝑎0 (𝑏) cette écriture s’appelle l’écriture de
l’entier 𝑛 dans la base 𝑏

Exemple :
̅̅̅̅̅̅̅(10) car 𝑛 = 2 × 104 + 9 × 103 + 8 × 102 + 7
Le nombre 𝑛 = 2987 s’écrit 𝑛 = 2987
Essayons d’écrire 𝑛 dans la base 6 :
On a :
2987 = 6 × 497 + 5
497 = 6 × 82 + 5
82 = 6 × 13 + 4
13 = 6 × 2 + 1
2=6×0+2
Donc 2987 = 2 × 64 + 1 × 63 + 4 × 62 + 5 × 6 + 5 = ̅̅̅̅̅̅̅̅̅̅̅̅
21455(6)
Cette succession de divisions Euclidiennes se représente comme ci-contre :
2) Les opérations dans une base de numération
2.1 La somme :
On peut effectuer la somme dans une base donnée 𝑏 par deux façons différentes :
 La décomposition :
̅̅̅̅̅̅̅
2534(7) + ̅̅̅̅̅
631(7) = (2 × 73 + 5 × 72 + 3 × 7 + 4 ) + (6 × 72 + 3 × 7 + 1 )
= 2 × 73 + (5 + 6) × 72 + (3 + 3) × 7 + (4 + 1) 5+6=7+4
= 3 × 73 + 4 × 72 + 6 × 7 + 5
= ̅̅̅̅̅̅̅
3465(7)
 Calcul direct avec le retenu

12
L’arithmétique A.KARMIM
2.2 Le produit :
Il est préférable d’effectuer le produit en utilisant le calcul direct avec le retenu car la décomposition risque d’être
longue :

Pour vérifier :
327(8) × ̅56
̅̅̅̅̅ ̅̅̅(8) = (3 × 82 + 2 × 8 + 7) × (5 × 8 + 6)
= 9890
̅̅̅̅̅̅̅̅̅(8)
= 23242
2.3 Opérations dans différentes bases :
Pour effectuer des opérations dans différentes base on développe les deux nombres dans la base 10 ; on effectue
l’opération et on écrit le résultat dans la base demandée.
Exemple : effectuer dans la base 9
6432(7) × ̅54
̅̅̅̅̅̅̅ ̅̅̅(8) = (6 × 73 + 4 × 72 + 3 × 7 + 2) × (5 × 8 + 4)
= 100188
= 1 × 95 + 6 × 94 + 2 × 93 + 3 × 92 + 8 × 9 + 0
̅̅̅̅̅̅̅̅̅̅(9)
= 162380

IV) CRITERES DE DIVISIBILITE DES NOMBRES 5,25,3,9,11 ET 4

Théorème :
Soit 𝑥 un entier naturel non nul tel que : 𝑥 = 𝑎𝑛 . 10𝑛 + 𝑎𝑛−1 . 10𝑛−1 + ⋯ + 𝑎1 . 10 + 𝑎0 où 0 ≤ 𝑎𝑖 ≤ 9 ; on a :
 𝑥 ≡ 0 [5] ⟺ 𝑎0 = 0 ou 𝑎0 = 5
 𝑥 ≡ 0 [25] ⟺ 𝑎 ̅̅̅̅̅̅
1 𝑎0 ∈ {0,25,50,75}
 𝑥 ≡ 0 [3] ⟺ ∑𝑖=0 𝑎𝑖 ≡ 0 [3]
𝑛

 𝑥 ≡ 0 [9] ⟺ ∑𝑛𝑖=0 𝑎𝑖 ≡ 0 [9]

 𝑥 ≡ 0 [11] ⟺ ∑𝑛𝑖=0(−1)𝑖 𝑎𝑖 ≡ 0 [11]
 𝑥 ≡ 0 [4] ⟺ 𝑎 1 𝑎0 ≡ 0 [4]
̅̅̅̅̅̅

Preuve en exercice :

V) L’ENSEMBLE ℤ/𝑝ℤ OU 𝑝 EST UN NOMBRE PREMIER.

Théorème :
Pour tous entiers relatifs non nuls 𝑎 et 𝑏 ; 𝑎 ∧ 𝑛 = 1 ⟺ (∃𝑚 ∈ ℤ)(𝑎𝑚 = 1 [𝑛] )

Preuve :
(⇒) On suppose que : 𝑎 ∧ 𝑛 = 1, alors d’près T. Bézout (∃(𝑚, 𝑢) ∈ ℤ2 )(𝑚𝑎 + 𝑢𝑛 = 1)
Donc : (∃(𝑚, 𝑢) ∈ ℤ2 )(𝑢𝑛 = 1 − 𝑚𝑎) donc 𝑛|𝑚𝑎 − 1 et finalement : 𝑎𝑚 = 1 [𝑛]
(⇐) On suppose que : (∃𝑚 ∈ ℤ)(𝑎𝑚 = 1 [𝑛]) donc 𝑛|(𝑎𝑚 − 1) donc (∃𝑘 ∈ ℤ)(𝑎𝑚 − 1 = 𝑘𝑛)
donc : 𝑎𝑚 − 𝑘𝑛 = 1 et d’après T. Bézout inverse 𝑎 ∧ 𝑛 = 1

13
L’arithmétique A.KARMIM
Théorème :
Si 𝑝 est un nombre premier positif alors tout élément 𝑥̅ ≠ 0̅ admet un inverse dans ℤ⁄𝑝ℤ − {0̅}

Preuve :
Soit 𝑝 un nombre premier positif ; on pose 𝐸 = ℤ⁄𝑝ℤ − {0̅}
𝑥̇ ∈ 𝐸 ⟺ (∃𝛼 ∈ {1,2, … , 𝑝 − 1})( 𝑥̅ = 𝛼̅)
𝑝 étant, premier donc 𝑝 ne divise aucun nombre de l’ensemble {1,2, … , 𝑝 − 1} d’où 𝑝 ∧ 𝛼 = 1
Et d’après la propriété précédente : (∃𝑦 ∈ ℤ∗ )(𝑦𝛼 ≡ 1[𝑝])
̅̅̅̅ = 1̅
Donc : 𝛼𝑦
D’où : 𝛼̅ 𝑦̅ = 1̅ et comme 𝑥̅ = 𝛼̅ donc 𝑥̅ 𝑦̅ = 1̅

14