Chapitre 1 : Arithmétique des entiers :

1 ¿ lesnombres entiers :
'
a ¿ l ensemble N des entiers naturels

On connaît deux ensembles de nombres entiers qui sont les suivants :

∎ l’ensemble des entiers naturels N = {0 ,1 , 2 ,3 … }
∎ l’ensemble des entiers relatifs Z = {−1 , 0 ,1 … }

Axiomes de Peano : il existe un ensemble noté N dont les éléments sont appelés les entiers naturels qui
vérifie
1 ¿ N contient un élément noté 0
.≤ premier axiome de Peano nous fournit un premier entier naturel qui correspond à 0
2 ¿ il existe une application de N dans N que l’on appelle l’application successeur et que l’on note s
.≤deuxième axiome , nous dit alors que cet entier 0 est un successeur ,qui est lui aussi un entier naturel
3 ¿ 0 n’est le successeur d’aucun entier il n’existe pas d’élément n ∈ N tel que 0 = s ( n )
. comme≤troisième axiome nous dit que ce successeur ne peut pas être 0lui -
'
même donc onl appelle 1
4 ¿ deux éléments qui ont le même successeur sont égaux pour tout (m , n)∈ N 2 tel que s(n) = s(n) ainsi n
=n
'
.≤successeur de 1 est donc encore un nouvel entier naturel , que l on peut appeler 2 , et on peut reproduire
'
cette procédure à l infini , et ainsi définir 3 , 4 , etc pour retrouver les entiers auxquels nous sommeshabitués .
5 ¿ toute partie de N qui contient 0 et le successeur de chacun de ses éléments est égale à N tout entier :
.si A est une partie de N telle que 0 ⊂ A et ∀ n ∈ N , n ∈ A cela veut dire que s(n)∈ A on obtient donc A
=N
'
. il reste bien sûr à savoir si , en procédant de cette manière , on atteint bientous les éléments de l ensemble N

Proposition: tout entier différent de 0 est le successeur d’un entier pour tout n ∈ N , il existe ainsi n = s(n)
Démonstration : posons A = { n ∈ N| n = 0 ou ∃ n∈ N , n = s(n)}
.0∈ A
. soit n ∈ N tel que n ∈ A , il est clair que s(n)∈ A
Donc d’après le 5ème axiome de Peano , A = N ainsi on obtient N = { n ∈ N| n = 0 ou s ( n ) ∈ N ∨n = s(n)}
On peut donc conclure, suite à cette démonstration que pour tout n ∈ N ¿ 0 } il existe n ∈ N tel que n = s(n)

Définition : on retrouve la suite des entiers naturels telle qu’on la connaît à partir des axiomes de Peano :
. par exemple pour le successeur de 1 on obtient s(0)
. par exemple pour le successeur de 2 on obtient s(1)
. par exemple pour le successeur de 3 on obtient s(2)
. par exemple pour le successeur de 4 on obtient s(3)
Ainsi de suite, pour n’importe quel successeur choisi, on obtient toujours un même exemple de ce résultat

2 ¿ Opérations sur les entiers naturels:

a ¿ addition des entiers naturels

Définition : on définit l’addition des entiers naturels en posant les assertions qui sont les suivantes :
∎ pour tout n ∈ N , on obtient n + 0 = n
∎ pour tout n ∈ N et tout p ∈ N on obtient n + s( p) = s ¿ + p ¿
Remarque : il faudrait normalement vérifier que cette définition soit complète, plus précis c’est-à-dire que
les égalités données suffisent à définir la somme de tout couple d’entiers

Exemple : que vaut n + 1 si n ∈ N ? Exemple : que vaut 2 + 2 ?

= n + s(0) = 2 + s(1)
= s¿ + 0¿ = s¿ + 1¿
= s(n) = s(3) = 4
On peut donc en conclure, suite à cette exemple que n + 1 vaut s(n) et pour 2 + 2 on a obtenu s(3) = 4
Remarque : l’intérêt de cette définition formelle est qu’elle nous permet de démontrer les propriétés de
l’addition que l’on considère sinon comme évidentes par exemple que ∀( m, n)∈ N 2 m + n = n + m
Proposition : l’addition des entiers naturels vérifie les propriétés suivantes :
1 ¿ pour tout (a ,b ,c )∈ N 3 alors ¿ + b ¿ + c = a + ¿ + c ¿
2 ¿ pour tout(a ,b) ∈ N 2 alors a + b = b + a
3 ¿ pour tout (a ,b ,c )∈ N 3 alors a + b = a + c donc on en déduit que b = c
4 ¿ pour tout (a ,b) ∈ N 2 alors si a + b = 0 alors a = b = 0
Démonstration : démontrons, dans l’ordre chacune des quatre propositions citées précédemment :
1 ¿ soit ( a , b ) ∈ N 2 , posons A = { c ∈ N|¿ + b ¿ + c = a + ¿ + c ¿ }
. par définition ¿ + b ¿ + 0 = a + b = a + ¿ + 0 ¿ donc 0 ∈ A
. soit c ∈ A , en utilisant la définition de l’addition et la définition de l’ensemble A , on obtient comme
résultat :
= ¿ + b ¿ + s(c) = s ¿ + b ¿ + c ¿ = s ¿ + ¿ + c ¿ ¿ = a + s ¿ + c ¿ = a + ¿ + s(c)¿
On peut donc en conclure, que s(c)∈ A ainsi d’après le cinquième axiome de Peano , A = N
2 ¿ pour démontrer le deuxième point, commençons par prouver deux lemmes, ainsi ce qui nous donne :
∎ lemme 1: pour tout n ∈ N , 0 + n = n donc posons A = { n ∈ N| n + 0 = n }
. par définition 0 + 0 = 0 donc 0 ∈ A
. pour tout n ∈ A , 0 + s(n) = s ¿ + n ¿ = s(n)
∎ lemme 2: pour tout n ∈ N , s(n) = 1 + n donc posons A = { n ∈ N| s (n) = 1 + n }
. d’après la définition s(0) = 1 = 1 + 0 donc 0 ∈ A
. pour tout n ∈ A , s( s ( n )) = s ¿ + n ¿ = 1 + s(n)
Revenons maintenant à la propriété, fixons a ∈ N et posons A = { b ∈ N| a + b = b + a } ainsi on obtient :
. on a a + 0 = a = 0 + a comme nous l’avons démontré précédemment d’après le lemme 1 , donc 0 ∈ A
. soit b ∈ A , alors d’après le lemme 2 et la première propriété de l’addition, on obtient comme résultat :
= a + s(b) = s ¿ + b ¿ = s ¿ + a ¿ = b + s(a) = b + ¿ + a ¿ = ¿ + 1 ¿ + a = s(b) + a
On peut donc en conclure, que s(b)∈ A ainsi d’après le cinquième axiome de Peano , A = N
3 ¿ posons A = { a ∈ N |∀ ( b , c ) ∈ N 2 , a + b = a + c →b = c }
. pour tout ( b , c ) ∈ N 2 tel que 0 + b = 0 + c , d’après la propriété de l’addition b + 0 = c + 0 c’est-à-dire b = c
. soit a ∈ A , soit (b , c )∈ N 2 tel que s(a) + b = s(a) + c alors d’après la deuxième propriété on obtient :
= b + s(a) = c + s(a) donc s ¿ + a ¿ = s ¿ + a ¿
. d’après le quatrième axiome de Peano , cela implique que b + a = c + a , c’est-à-dire que a + b = a + c
. en utilisant à nouveau la deuxième propriété, comme a ∈ A , il en découle que b = c
On peut donc en conclure, que s(a)∈ A ainsi d’après le cinquième axiome de Peano , A = N
4 ¿ soit (a ,b) ∈ N 2 tel que a + b = 0 , nous allons raisonner par l’absurde
. supposons que b ≠ 0 ,d’après la première proposition qu’on a démontrée, il existe c ∈ N tel que b = s(c)
0 = a + b = a + s(c) = s ¿ + c ¿
. on remarque, que cela contredit le deuxième axiome de Peano donc en en conclut que b = 0
. si l’on suppose que a ≠ 0 , on obtient alors la même contradiction, et on obtient donc aussi a = 0
b ¿ multiplication des entiersnaturels
Définition : on définit la multiplication des entiers naturels en posant les assertions qui sont les suivantes :
∎ pour tout n ∈ N , on obtient n × 0 = 0
∎ pour tout n ∈ N et tout p ∈ N on obtient n × s (p) = n × p + n

Exemple : que vaut n ×1 si n ∈ N ? Exemple : que vaut 2 × 2 ?

= n × s (0) = 2 × s(1)
= s¿ + n¿ = s¿ + 2¿
=n+0=0 =2+2=4

Proposition: la multiplication des nombres entiers naturels vérifie les propriétés suivantes :
1 ¿ pour tout ( a , b , c ) ∈ N 3 alors (a × b)× c = a ×(b × c)
2 ¿ pour tout ( a , b ) ∈ N 2 alors a × b = b × a
3 ¿ pour tout ( a , b , c ) ∈ N 3 alors a × ¿ + c ¿ = a × b + a × c
4 ¿ pour tout ( a , b ) ∈ N 2 alors si a × b = 0 alors a = 0 ou b = 0
5 ¿ pour tout ( a , b , c ) ∈ N 3 alors si a × b = a × c et a ≠ 0 alors b = c
Remarque : on s’aperçoit en utilisant dans les démonstrations le cinquième axiome de Peano , est une
façon particulière d’énoncer la propriété connu généralement sous la forme du principe de récurrence
3 ¿ Théorème: soit P un prédicat (une propriété ) sur N ,on suppose les assertions qui sont les suivantes :
. P(0) est vraie
. que pour tout n ∈ N tel que P(n) soit vraie P ¿ + 1 ¿ l’est aussi ainsi P(n) est vraie pour tout n ∈ N
Démonstration : posons A = { n ∈ N| P(n) est vraie}
. 0 ∈ A ou P(0) est vraie
.soit n ∈ A alors P(n) est vraie par définition de A donc P ¿ + 1 ¿ est vraie par hypothèse donc n + 1 ∈ A
On peut conclure, que s(n)∈ A donc d’après le cinquième axiome de Peano , A = N donc P(n) est vraie

Exemple : soit x ∈ R+¿¿ démontrer que pour tout n ∈ N , ¿ + x ¿¿ n ≥ 1 + nx ainsi on obtient comme résultat :
. Initialisation: pour tout n ∈ N , notons P(n) l’assertion ( + x ¿¿ n ≥ 1 + nx
∎ on remarque que ¿ + x ¿¿ 0 = 1 et 1 + 0 x = 1 , donc on a bien ¿ + x ¿0 ≥ 1 + 0 x
On peut donc conclure, suite à cette démonstration que P(0) est vraie
. Hérédité : soit n ∈ N tel que P(n) soit vraie, alors ¿ + x ¿¿ n ≥ 1 + nx ainsi on obtient ¿ + x ¿¿ n+1 par la
suite :
= ¿ + x ¿¿ n × ¿ + x ¿ par définition des puissances
≥ ¿ + nx ¿ ¿ + x ¿ '
par l hypothèse et car 1+ x ≥ 0
2
≥ 1 + x + nx + nx en développant
2
≥ 1 + nx + x car n x ≥ 0
≥ 1 + ¿ + 1¿ x en factorisant
On peut conclure, d’après le principe de récurrence, P(n) est vraie pour tout n ∈ N , et on a ¿ + x ¿¿ n ≥ 1 +
nx

4 ¿ ordre sur les entiers naturels:

Nous aurons besoin de munir l’ensemble N des entiers naturels de l’ordre que nous utilisons habituellement
C’est justement l’objet de la définition, que nous allons énoncer à présent et qui est la suivante

Définition : soit (n , p)∈ N 2 ainsi on obtient les quatre assertions qui sont les suivantes :
. on dit que n est supérieur à p , et l’on note n ≥ p , lorsqu’il existe q ∈ N tel que n = p + q
. on dit que n est strictement supérieur à p , et l’on note n > p, lorsque n ≥ p et n ≠ p
. on dit que n est inférieur à p , et l’on note n ≤ p , lorsqu’il existe q ∈ N tel que p = n + q
. on dit que n est strictement inférieur à p , et l’on note n < p , lorsque n ≤ p et n ≠ p

Exemple : démontrer avec les conditions citées précédemment, que 5 ≥ 3

. on a bien 5 ≥ 3 puisque 5 = 3 + 2 avec 2 ∈ N
. on a en fait en même 5 > 3 puisque l’on a de plus 5 ≠ 3
Remarque : comme pour les opérations, cette définition permet de démontrer les propriétés évidentes
Nous verrons dans le deuxième chapitre du cours, que ces conditions définissent des relations d’ordre sur N
En attendant, nous pouvons d’ores et déjà remarquer que nous avons les propriétés qui sont les suivantes

Proposition: soit (a ,b ,c )∈ N 3 ainsi on obtient les quatre conditions qui sont les suivantes :
1 ¿ si a ≤ b et b ≤ a alors a = b ¿ ≥¿
2 ¿ si a ≤ b et b ≤ c alors a ≤ c ¿ ≥¿
3 ¿ si a ≤ b ou b ≤ a alors a = b ¿ ≥¿
4 ¿ si b ≤ c , a + b ≤ a + c ¿ ≥¿
5 ¿ si b ≤ c , a ×b ≤ a × c ¿ ≥¿

Proposition: (caractère discret et non borné de N)

1 ¿ il n’existe pas d’entier n ∈ N tel que 0 < n < 1
2 ¿ il n’existe pas d’entier n ∈ N tel que n ≥ p pour tout p ∈ N
Enfin, l’ordre que nous avons défini sur N vérifie les deux propriétés essentielles qui sont les suivantes :

Théorème :(caractère bien ordonné de N )

1 ¿ toute partie non vide de N admet un plus petit élément : si A est une partie non vide de N , alors il existe :
p ∈ A tel que p ≤ q pour tout q ∈ A
2 ¿ toute partie non vide et finie de N admet un plus grand élément : si A est une partie non vide et finie de
N:
p ∈ A tel que p ≥ q pour tout q ∈ A
'
5 ¿ l ensemble Z des entiersrelatifs :
Maintenant que nous avons défini l’ensemble N des entiers naturels, on aimerait faire pareil pour l’ensemble :
Z = {−1 , 0 ,1 … } des entiers relatifs, que nous allons considérer en arithmétique.
Il existe ainsi plusieurs manières de formaliser la définition de Z à partir de celle de N qui sont les suivantes :
. la plus courante est d’utiliser la notion de classes d'équivalences qu’on verra dans le
deuxième chapitre
. on peut définir Z comme un ensemble formé d’une copie de N dont les éléments sont assortis d’un sign -

Définition : on définit l’ensemble Z des entiers relatifs en posant l’assertion qui est la suivante:
Z = { ( n , 0 ) , n ∈ N } ∪{ ( 0 , n ) , n∈ N }
¿

. on identifie alors les entiers relatifs de la forme (n , 0) avec les entiers naturels n correspondants
. de l’autre côté on note -n les entiers relatifs de la forme (0 , n) qui correspond à une copie de N
On pose enfin Z+ ¿¿ = { ( n , 0 ) , n ∈ N } (qui s identifie à N ) et Z−¿ ¿ = { ( 0 ,n ) , n ∈ N }
' ¿
¿

Exemple : le couple (3 , 0) est identifié avec l’entier naturel 3 , tandis que le couple (0 , 3) est noté -3
On peut alors définir sur l’ensemble Z une addition qui prolonge celle définie sur l’ensemble de N

Définition : on appelle addition des entiers relatifs l’application de Z × Z dans Z définie comme suit :
. si (m , n)∈ ¿ + n est pris au sens de l’addition des entiers naturels
. si (−m ,−n)∈¿ ¿ on pose (−m) + (−n ) = −¿+ n ¿
. si m ∈ Z+¿ ¿ et −n ∈ Z−¿ ¿¿

¿ si m ≥ n , il existe p ∈ N tel que m = n + p , et l’on pose m + (−n) = p

¿si m ≤ n , il existe p ∈ N tel que n = m + p et l’on pose m + (−n) = − p
. si −m ∈ Z−¿ ¿ et n ∈ Z +¿¿
¿

¿ si m ≥ n , il existe p ∈ N tel que m = n + p , et l’on pose (−m) + n = − p

¿si m ≤ n , il existe p ∈ N tel que n = m + p , et l’on pose (−m) + n = p

Proposition: l’addition des entiers relatifs vérifie les propriétés qui sont les suivantes :
1 ¿ pour tout ( a , b , c ) ∈ Z 3 , ¿ + b ¿ + c = a + ¿ + c ¿
2 ¿ pour tout ( a , b ) ∈ Z 2 , a + b = b + a
3 ¿ pour tout ( a , b , c ) ∈ Z 3 , a + b = a + c alors on en déduit que b = c

Définition : pour tout entier k ∈ Z , il existe un entier l ∈ Z tel que k + l = l + k = 0 on appelle l’opposé de k
Remarque : on peut démontrer que cette définition associe bien à chaque entier un unique opposé.
On voit de plus à travers la démonstration en question que, pour tout k ∈ Z +¿, ¿ l’opposé de k est −k
Cela justifie le fait d’utiliser la même notation pour désigner ces deux choses a priori différentes

Définition : on appelle en soustraction des entiers relatifs l’application de Z × Z dans Z définie en posant :
pour tout ( a , b ) ∈ Z 2 , a−b = a + (−b)
Enfin, on peut définir une multiplication qui prolonge celle sur N , ainsi on obtient le résultat suivant :
Définition : on appelle multiplication des entiers relatifs l’application de Z × Z dans Z définie de cette
manière
.si (m , n)∈ ¿ est pris au sens de la multiplication des entiers naturels
. si (−m ,−n)∈¿ on pose (−m)×(−n) = m ×n
. si m ∈ Z+¿ ¿ et −n ∈ Z−¿ ¿on pose m ×(−n) = −(m× n)
¿

. si −m ∈ Z−¿ ¿ et n ∈ Z +¿¿ on pose (−m)× n = −(m× n)

¿

Proposition: la multiplication des entiers relatifs vérifie les propriétés qui sont les suivantes :
1 ¿ pour tout ( a , b , c ) ∈ Z 3 ,(a ×b) ×c = a ×(b × c)
2 ¿ pour tout ( a , b ) ∈ Z 2 , a ×b = b × a
3 ¿ pour tout ( a , b , c ) ∈ Z 3 , a × ¿ + c ¿ = a × b + a × c
4 ¿ pour tout (a ,b ,c )∈ Z 3 avec a ≠ 0 , a ×b = a × c ainsi on en déduit que b = c
5 ¿ pour tout (a ,b) ∈ Z 2 tel que a × b = 0 , a = 0 ou b = 0
Remarque : pour déterminer, on peut définir un ordre sur Z à partir de celui sur N
Ainsi on obtient la définition suivante, avec les quatre conditions qui sont les suivantes
Définition : soit (n , p)∈ Z 2 on obtient donc les assertions qui sont les suivantes :
. on dit que n est supérieur à p , et l’on note n ≥ p lorsque l’une des trois conditions suivantes est vérifiée :
¿(n , p)∈¿ ¿ et n ≥ p
¿(n , p)∈¿ ¿ et − p ≥ −n
¿ n ∈ Z +¿¿ et p ∈ Z−¿¿ ¿
. on dit que n est strictement supérieur à p , et l’on note n > p ,lorsque n ≥ p et n ≠ p
. on dit que n est inférieur à p , et l’on note n ≤ p , lorsque p ≥ n
. on dit que n est strictement inférieur à p , et l’on note n < p , lorsque n ≤ p et n ≠ p

Proposition: soit (a ,b ,c )∈ Z 3 ainsi on obtient les assertions qui sont les suivantes :
1 ¿ si a ≤ b et b ≤ a , alors a = b ¿≥¿
2 ¿ si a ≤ b et b ≤ c , alors a ≤ c ¿≥¿
3 ¿ on a toujours a ≤ b ou b ≤ a ¿ ≥¿
4 ¿ si b ≤ c , a + b ≤ a + c ¿≥¿
5 ¿ si b ≤ c et a ≥ 0 , a × b ≤ a × c ¿ ≥¿

2 ¿ divisibilité et division euclidienne :

Définition : soit (a ,b) ∈ Z 2 ainsi on obtient les assertions suivantes :
. on dit que a divise b , et l’on note a∨b , lorsqu’il existe k ∈ Z tel que b = ak
. on peut aussi dire que a est un diviseur de b ,que b est divisible par a ou que b est un multiple de a

Exemple 1: quels sont les diviseurs de 21 ?

.1 et 21 sont des diviseurs de 21 puisque l’on obtient 21 = 1 ×21
.3 et 7 sont également des diviseurs de 21 puisque l’on obtient aussi 21 = 3 ×7
. de même −1 ,−3 ,−7 et −21 sont des diviseurs de 21 puisque 21 = (−1)×(−21) et 21 =
(−3) ×(−7)
On peut donc conclure, qu’on se convainc facilement que 21 n’admet pas d’autres diviseurs que ceux déjà cités

Proposition: soit (a ,b)∈ Z 2 ainsi on obtient les assertions qui sont les suivantes :
1 ¿ si a∨b , alors (−a )|b , a|(−b) et (−a )∨(−b)
2 ¿ si a∨b et b∨a , alors a = b ou a = −b
Démonstration : nous allons démontrer uniquement le premier point
1 ¿ supposons que a∨b , alors par définition de la divisibilité, il existe k ∈ Z tel que b = ak ainsi on obtient :
b = (−a )(−k ) ainsi −b = a (−k ) et −b = (−a ) k

Proposition : soit (a ,b ,c )∈ Z 3 ainsi on obtient les assertions qui sont les suivantes :
1 ¿ si a∨b et b∨c , alors a∨c
2 ¿ si a∨b et a∨c , alors a∨b + c
3 ¿ si a∨b ou a∨c , alors a∨(bc)
¿ Démonstration : démontrons ces trois implications l’une après l’autre :
1 ¿ Supposons que a∨b et b∨c
. alors, par définition de la divisibilité comme a∨b , alors il existe k ∈ Z tel que b = ak
. alors, par définition de la divisibilité comme b∨c , alors il existe l ∈ Z tel que c = bl
Ainsi, en remplaçant on obtient comme résultat c = bl = ( ak ) l = a (kl) ainsi on peut conclure que a∨c
2 ¿ Supposons que a∨b et a∨c
. alors, par définition de la divisibilité comme a∨b , alors il existe k ∈ Z tel que b = ak
. alors, par définition de la divisibilité comme a∨c , alors il existe l ∈ Z tel que c = al
Ainsi, en remplaçant on obtient comme résultat b + c = ak + al = a ¿ + l ¿ ainsi on peut conclure que a∨b + c
3 ¿ Supposons que a∨b
. alors, par définition de la divisibilité, il existe k ∈ Z tel que b = ak
Ainsi, en remplaçant on obtient comme résultat bc = ( ak ) c = a (kc ) ainsi on peut conclure que a∨bc
. alors, par définition de la divisibilité, il existe l ∈ Z tel que c = al
Ainsi, en remplaçant on obtient comme résultat bc = ( al ) b = a (lb) ainsi on peut conclure que a∨bc
Remarque : les réciproques de ces implications sont fausses, nous pouvons le démontrer avec des exemples :
. un entier peut diviser une somme sans diviser les termes de cette somme comme nous pouvons le voir :
par exemple 2∨10 et 10 = 7 + 3 en revanche, 2 ∤ 7 et 2 ∤3
. un entier peut diviser un produit sans diviser aucun des facteurs comme nous pouvons le voir :
par exemple 21∨21 et 21 = 3 ×7 en revanche on n’a ni 21∨3 ni 21∨7
Exemple : montrer que pour tout n ∈ N , l’entier 6 n2 + 9 n est un multiple de 3
. comme 3∨6 , on obtient alors 3∨6 n2 d’après le troisième point
. de même comme 3∨9 , on obtient 3∨9 n d’après le troisième point
On peut donc en conclure que 3∨¿ + 9 n ¿ d’après le deuxième point de cette même proposition
Proposition: soit n ∈ Z ¿ ainsi on obtient les assertions qui sont les suivantes :
. pour tout entier diviseur d ∈ Z tel que d∨n , ainsi on obtient ¿ d∨¿ ≤ ¿ n∨¿
. en particulier l’ensemble des diviseurs de n est fini
Démonstration : nous allons démontrer successivement, les deux assertions énoncées précédemment :
. soit d ∈ Z tel que d∨n alors, par définition de la divisibilité, il existe k ∈ Z tel que n = dk
. raisonnons maintenant par l’absurde, en supposant que ¿ d∨¿ > ¿ n∨¿ on obtient alors le résultat suivant :
¿ d∨¿ > ¿ n∨¿ ≥ ¿ dk ∨¿ ≥ ¿ d∨×∨k∨¿ ≥ ¿ d∨¿
On peut donc conclure que ¿ d∨¿ > ¿ d∨¿ ce qui nous donne une contradiction donc on obtient bien ¿ d∨¿
≤ ¿ n∨¿
. d’après le premier point, l’ensemble des diviseurs de n est inclus dans { d ∈ Z|∨d∨¿ ≤ ¿ n∨}
. c’est-à-dire dans ¿ ce dernier ensemble est fini 2 + 1 alors l’ensemble des diviseurs de n est fini

2 ¿ Nombres premiers :
Définition : soit p ∈ Z , on dit que p est un nombre premier lorsque les conditions suivantes sont vérifiées :
.p ≥2
. les seuls diviseurs positifs de p sont 1 et p
Remarque : attention ni 0 , ni 1 , ni aucun entier négatif n’est un nombre premier

Exemple : donner tous les nombres premiers inférieurs à 15

.en parcourant dans l’ordre les entiers entre 2 et 15 et en cherchant de tête leurs diviseurs, on trouve que les
nombres premiers inférieurs à 15 sont 2 , 3 ,5 , 7 , 11 et 13
Exemple : l’entier 222 est-il un nombre premier ?
222 = 111× 2 donc 222 est divisible par 2 ¿-même ¿ ainsi 222 n’est pas un nombre premier
Exemple : l’entier 223 est-il un nombre premier ?
. on ne trouve pas de tête de diviseur évident de 223 , cependant pour montrer que c’est un nombre
premier, il faudrait s’assurer qu’il n’est divisible par aucun des entiers entre 2 et 222 , ce qui semble très
fastidieux…

Proposition : soit n ∈ N tel que n ≥ 2 alors on obtient l’assertion suivante :

n admet (au moins ) un diviseur premier
Démonstration : posons A = { k ∈ N| k∨n et k > 1 } soit n ∈ N un entier tel que n ≥ 2
−¿ on remarque que n ∈ A ¿ et n > 1 ¿ et donc on en déduit que A est une partie non vide de N
−¿ ainsi d’après les propriétés de l’ordre sur les entiers naturels, alors A admet un plus petit élément
. notons p ce plus petit élément et montrons qu’il est premier, considérons maintenant un diviseur d de p
. on a tout d’abord d ≤ p par la propriété précédente
. comme d∨ p (par choix de d ) et p∨n( puisque p ∈ A ), on obtient d∨n
Comme on a d > 1 par hypothèse, cela implique que d ∈ A et p étant le plus petit élément de A , alors d ≥ p
En rassemblant les inégalités, on obtient d = p autrement le seul diviseur de p strictement supérieur à 1 est p
On peut donc conclure suite à cette démonstration que p est bien un nombre premier

Proposition: soit n ∈ N tel que n ≥ 2 alors on obtient l’assertion qui est la suivante :
. s’il n’existe aucun nombre premier p tel que p ≤ √ n et p divise n , alors n est premier
Démonstration : nous allons raisonner par contraposition pour effectuer la démonstration
−¿ supposons que n ne soit pas premier, et montrons qu’il existe un nombre premier p tel que p ≤ √ n et
p∨n
−¿ d’après la démonstration précédente, n admet un plus petit diviseur strictement supérieur à 1 , notons-le
p0
Pour montrer que p0 vérifie la condition voulue, il ne reste plus qu’à vérifier que p0 ≤ √ n
. si l’on avait q = 0 , on aurait n = 0 ce qui est exclu par hypothèse
. si l’on avait q = 1 , on aurait n = p0 et n serait donc premier, ce qui est également exclu donc q > 1
 2
On peut conclure, d’après la manière dont p0 a été choisi, q ≥ p0 cela implique que n = p0 q ≥ p0 donc p0 ≤
√n
Exemple : si l’on reprend l’exemple précédent, 223 est-il un nombre premier ?
. on remarque que √ 223< 15 nous avons vu plus haut, les nombres premiers inférieurs à 15 : 2 , 3 ,5 , 7 , 11,
13 . alors on vérifie rapidement avec les nombres premiers inférieurs à 15 qu’aucun de ces entiers ne divise
23
Algorithme: soit N ∈ N ¿ , cet algorithme permet de trouver tous les nombres premiers inférieurs ou égaux
àN
. on écrit tous les entiers de 1 à N , et l’on barre 1 qui n’est pas premier
. le premier entier non barré est 2 , on l’entoure car il est premier, puis on barre tous ses multiples sauf 2
. le premier entier non barré est 3 , on l’entoure car il est premier, puis on barre tous ses multiples sauf 3
. on répète l’opération jusqu’à obtenir, que le premier entier non barré soit strictement supérieur à √ N
. au moment où l’on s’arrête, tous les entiers non barrés qui restent sont premiers et doivent être entourés

Exemple :
. on barre successivement les multiples de 2 ( en vert ) , de 3 ( en bleu ) , de 5(en rouge) et de 7(en violet )
. ainsi on en déduit que tous les nombres non barrés qui restent sont donc les nombres premiers ( en orange )
1 2 3 4 5 6 7 8 9 10
1112 1314 1516 17 18 19 20
21 2223 24 2526 27 28 29 30
31 3233 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

Théorème : il existe une infinité de nombres premiers, pour prouver cela nous allons le démontrer
Démonstration : supposons par l’absurde que l’ensemble des nombres premiers soit fini, alors on obtient :
n
. notons alors n ∈ N son cardinal et p1 , … , pn ses éléments, et posons N = ∏ p i + 1, il est clair que N ≥ 2
i=1
. N admet un diviseur premier p d’après une proposition précédente puisque p est un nombre,
p ∈{ p 1 , … , p n }
n
on en déduit que p divise ∏ pi
i=1
n
. d’après les propriétés de la divisibilité, p divise également N−∏ pi plus précisément il divise 1
i=1
On peut donc en conclure que p ≤ 1 , ce qui est absurde puisque le plus petit nombre premier est 2

3 ¿ Division euclidienne :
Afin de pouvoir terminer cette partie, nous allons enfin présenter un autre outil qui est indispensable en
arithmétique et cet outil indispensable est ¿ théorème de la divisioneuclidienne
Théorème : soient a ∈ Z et b ∈ Z ¿ , il existe un unique couple (q ,r ) ∈ Z 2 qui vérifie les conditions
suivantes :
. a = bq + r on rappelle que q correspond au quotient
. 0 ≤ r ≤ ¿ b∨¿ et r correspond au reste de la division euclidienne

Démonstration : démontrons qu’il existe un couple (q ,r ) et dans un second temps que ce couple est unique
∎ premier cas : supposons que a ≥ 0 et b > 0
. considérons la partie de N définie par A = { q ∈ N|bq ≤ a } comme 0 ∈ A , alors A est non vide
. de plus comme b ≥ 1 , tout élément q ∈ A vérifie 0 ≤ b ≤ bq ≤ a donc on en déduit que A est finie
Ainsi, avec ces deux conditions on peut conclure que A admet un plus grand élément, notons-le q 0
. posons alors r = a−bq 0 de manière à avoir a = bq 0 + r comme q 0 ∈ A alors bq 0 ≤ a donc r ≥ 0
. par ailleurs, comme q 0 + 1 >q 0 alors q 0 + 1 ∉ A donc b ¿ + 1 ¿ > a et donc r = a−bq 0 < b
On peut donc conclure avec cette démonstration pour ce premier cas que finalement le couple (q 0 ,b)
convient
∎ deuxième cas: supposons que a ≤0 et b > 0
. alors −a ≥ 0 et b > 0 d’après le premier cas, il existe un couple (q ,r ) ∈ Z 2 tel que −a = bq + r avec 0 ≤ r <
b
. nous avons donc a = −¿ + r ¿ = b (−q) + (−r ) , ainsi il faut alors distinguer deux cas qui sont les suivants :
¿ si r = 0 , on obtient a−r = 0 et le couple (−q , 0) convient
¿ si r > 0 , on peut écrire a = b (−q−1) + ( b−r ) , et l’on obtient b−r ≥ 0 ¿ < b ¿
Ainsi, on peut donc conclure que b−r < b ¿ > 0 ¿ , donc le couple (−q−1 , b−r) convient
∎ troisième cas : supposons que b < 0
. alors −b > 0 d’après le deuxième cas, il existe un couple (q ,r )∈ Z 2 tel que a = (−b ) q + r avec 0 ≤ r < −b
On peut donc conclure qu’on obtient l’égalité a = b (−q) + r avec 0 ≤ r < ¿ b∨¿ et le couple (−q , r)
convient
Remarque : on a bien prouvé que dans tous les cas, il existe un couple (q ,r )∈ Z 2 remplissant les conditions

Unicité : soient (q ¿ ¿ 1 ,r 1 )∈ Z 2 ¿ (q ¿ ¿ 2 ,r 2)∈ Z2 ¿ tel que a = bq 1 + r 1 avec 0 ≤ r 1 < ¿ b∨¿ et a = bq 2 +

r 2 avec 0 ≤ r 2 < 0
. en rassemblant les deux égalités, on obtient comme résultat bq 1 + r 1 = bq 2 + r 2 donc r 2−r 1 =
b (q ¿ ¿ 1−q2 )¿
. comme 0 ≤ r 1 < ¿ b∨¿ et 0 ≤ r 2 < ¿ b∨¿ on obtient 0 ≤ r 2−r 1 < ¿ b∨¿ par ailleurs b∨r 2−r 1 d’après
l’une des égalité
. si on avait r 2−r 1 ≠ 0 on aurait ¿ b∨¿ ≤ (r ¿ ¿ 2−r 1), ¿ ce qui donne une contradiction donc r 2−r 1 = 0 soit
r1 = r2
. cela entraîne que bq 1 = bq 2 , puis que q 1 = q 2 puisque b ≠ 0 les deux couples (q ¿ ¿ 1 ,r 1 )¿ et (q ¿ ¿ 2 ,r 2)¿
sont égaux
On peut conclure qu’en rassemblant les deux étapes il existe un unique couple d’entiers vérifiant les conditions
Remarque : attention, si on oublie la condition qui porte sur le reste, alors on dit qu’il n’y a plus unicité !
Exemple : quels sont le quotient et le reste de la division euclidienne de 4152 par 7 ?
. de manière générale on détermine le quotient, le reste d’une division euclidienne avec algorithme de division
. ici, en posant la division à la main, on trouve comme résultat que 4152 = 7 ×593 + 1 avec 0 ≤ 1 < 7
On peut conclure, donc que le quotient de la division euclidienne de 4152 par 7 est 593 et que son reste est 1
Exemple : démontrer que pour tout n ∈ N , l’entier n ¿ + 1 ¿ ¿+ 2 ¿ est divisible par 3 ?
. d’après le théorème de division euclidienne, il existe (q ,r )∈ N 2 tel que n = 3 q + r avec 0 ≤ r < 3
¿ si r = 0 , alors n = 3 q donc 3∨n et donc 3∨n ¿ + 1 ¿ ¿ + 2 ¿
¿ si r = 1 , alors n = 3 q + 1 donc n + 2 = 3 q + 3 = 3 ¿ + 1 ¿ donc 3∨¿ + 2 ¿ et donc 3∨n ¿ + 1 ¿ ¿ + 2 ¿
¿ si r = 2 , alors n = 3 q + 2 donc n + 1 = 3 q + 3 = 3 ¿ + 1 ¿ donc 3∨¿ + 1 ¿ et donc 3∨n ¿ + 1 ¿ ¿ + 2 ¿
On peut donc conclure, que nous avons bien montré que dans tous les cas 3 divise n ¿ + 1 ¿ ¿ + 2 ¿

3 ¿ PGCD et PPCM :
a ¿ Plus Grand Commun Diviseur

Définition : soit (a ,b)∈ Z 2 \{(0 , 0)} alors l’ensemble des diviseurs positifs à a et b admet un plus grand
élément
. on l’appelle PGCD de a et b et on le note PGCD(a ,b)
Démonstration : posons A = { d ∈ N|d ∨a et d∨b } et vérifions l’affirmation contenue dans cette définition
. il est clair que 1 ∈ A puisque 1∨a et 1∨b donc cela veut dire que A ≠ ∅
. si a ≠ 0, alors tous les entiers d appartenant à A vérifient 0 ≤ d ≤ |a| donc on en déduit que A ⊂ ¿
. si a = 0 alors on obtient b ≠ 0 et tous les entier d appartenant à A vérifient 0 ≤ d ≤ ¿ b∨¿ donc A ⊂ ¿
On peut donc conclure, que A est une partie non vide et finie de N donc A admet bien un plus grand élément

Exemple : quel est le PGCD des entiers 24 et 40 ?

.l’ensemble des diviseurs positifs de 24 est { 1 , 2, 3 , 4 ,6 ,8 , 12 ,24 }
. l’ensemble des diviseurs positifs de 40 est {1 , 2 , 4 , 5 , 8 ,10 , 20 , 40 }
On remarque que le plus grand élément commun à ces deux ensemble est 8 donc PGCD(24 , 40) = 8
Remarque : pour tout (a ,b) ∈ Z 2 \{(0 , 0) } on a clairement les relations qui sont les suivantes :
. PGCD(a , b) = PGCD(b ,a)
. PGCD(a , b) = PGCD(|a|,|b|)
. PGCD(a , a) = ¿ a∨¿
. PGCD(a , 1) = 1
. PGCD(a , 0) = ¿ a∨¿
Remarque : par commodité, et compte tenu de la troisième et la cinquième relations ci-dessus alors
on étend généralement la définition du PGCD à tout couple de Z 2 en posant de plus PGCD(0 , 0) = 0

'
b ¿ Algorithme d Euclide et couples de Bézout
Pour déterminer en pratique le PGCD de deux entiers sans devoir lister tous leurs diviseurs, pour cela on
peut utiliser la propriété suivante, qui donne lieu à un algorithme que nous présenterons juste après

Proposition: soient a ∈ Z , b ∈ Z ¿ et r le reste de la division euclidienne de a par b on obtient comme

résultat
PGCD(a ,b) = PGCD(b ,r )
Démonstration : notons q le quotient de la division euclidienne de a par b de manière à voir la forme a = bq +
r
. notons par ailleurs D 1 l’ensemble des diviseurs positifs communs à a et b
. notons par ailleurs D 2l’ensemble des diviseurs positifs communs à b et r
Afin d’obtenir le résultat voulu, nous allons démontrer que les deux ensembles D 1 et D 2 sont égaux
Pour cela, nous allons procéder par double inclusion en montrant d’abord que D 1 ⊂ D 2 et ensuite que
D2 ⊂ D1
¿(⊂) soit d ∈ D1
. par définition de D 1 on a d ≥ 0 alors d∨a et d∨b on en déduit que d∨(−bq) puis que d∨(a−bq)
donc d∨r
On peut conclure en associant les éléments, d est un diviseur positif commun à b et r cela montre que
D ∈ D2
¿(⊃) soit d ∈ D2
. par définition de D2 on a d ≥ 0 alors d∨b et d∨r on en déduit que d∨(bq) puis que b∨¿ + r ¿ donc
d∨a
On peut conclure en associant les éléments, d est un diviseur positif commun à a et b cela montre que
D ∈ D1
On en déduit ces deux inclusions que D 1 = D 2 notamment ces ensembles ont donc le même plus grand
élément
Or, le plus grand élément de D 1 est le plus grand diviseur positif commun à a et b , c’est-à-dire PGCD(a ,b)
Comme le plus grand élément de D 2 est le plus grand diviseur positif commun à b et r , c’est-à-dire
PGCD(a ,b) Ainsi on peut en conclure avec cette démonstration que PGCD(a ,b) = PGCD(b ,r )

Algorithme: soit (a ,b) ∈ Z 2 on peut déterminer le PGCD de a et b de la manière suivante alors on

obtient :
. si b = 0 , alors PGCD(a ,b) = ¿ a∨¿
. si b ≠ 0 , on note r 1 le reste de la division euclidienne de a par b , et le PGCD cherché est égal à
PGCD(b ,r 1 )
D’après la proposition précédente si r 1 = 0 alors PGCD(b ,r 1 ) = ¿ b∨¿ donc on obtient alors
PGCD(a ,b) = ¿ b∨¿
. si r 1 ≠ 0 , on note r 2 le reste de la division euclidienne de b par r 1 et le PGCD cherché est égal à
PGCD(r 1 , r 2)
D’après la proposition précédente si r 2 = 0 alors PGCD(r 1 , r 2) = r 1 donc on obtient alors PGCD(a ,b) =
r1
. si r 2 ≠ 0 , on continue à faire de même, quand on remplace le PGCD à calculer par un autre qui lui es égal
. mais avec le deuxième entier qui devient de plus en plus petit par définition du reste de la division euclidienne
Forcément on finit par avoir un nombre fini d’itérations, PGCD de la forme PGCD (n,0) qui est le PGCD
initial
Exemple : quel est le PGCD de 685 et 160 ?
Pour trouver ce PGCD , on effectue de division euclidienne en cascade jusqu’à obtenir un reste nul comme
ceci :
685 = 160 × 4 + 45
160 = 45 × 3 + 25
45 = 25 ×1 + 20
25 = 20 ×1 + 5
20 = 5 × 4 + 0
Le dernier reste non nul que l’on obtient est 5 , ainsi on obtient comme résultat PGCD(685,160) = 5
Exemple : quel est le PGCD de 137 et 64 ?
Pour trouver ce PGCD , on effectue de division euclidienne en cascade jusqu’à obtenir un reste nul comme
ceci :
137 = 64 × 2 + 9
64 = 9 ×7 + 1
9 = 1 ×9 + 0
Le dernier reste non nul que l’on obtient est 1 , ainsi on obtient comme résultat PGCD(137 , 64) = 1
. il permet de démontrer le théorème suivant, essentiel et permettra d’établir plusieurs autres résultats

Théorème : soit (a ,b)∈ Z 2 alors il existe (u , v )∈ Z 2 tel que PGCD(a ,b) = au + bv ainsi par la suite on
dit que
(u , v ) est un couple de Bézout associé à a et b
Démonstration : l’existence du couple (u , v ) ayant la propriété voulue est prouvée par l’algorithme d’Euclide
. nous n’allons pas rédiger la preuve général, qui nécessite d’introduire beaucoup de notations sans être clair
. décrire le principe de l’algorithme et donner un exemple qui montre comment s’obtient le couple de Bézout

Algorithme: soit ( a , b ) ∈ Z 2 , on peut déterminer un couple de Bézout associé à a et b

(complèter la version)
. on commence comme avant, par effectuer des divisions euclidiennes successives jusqu’à obtenir un reste nul
le PGCD de a et b est le dernier reste non nul, c’est le reste de la n -ième étape de l’algorithme et notons-le
rn
.en utilisant la division euclidienne écrite lors de cette étape, on peut exprimer le reste r n à partir r n−1 et r n−2
. dans l’expression obtenue, le reste r n−1 peut à son tour être exprimé à partir de r n−2 et r n−3
cette fois en utilisant la division euclidienne avec n−1 , on a une nouvelle expression à partir de r n−2 et r n−3
. on poursuit ainsi jusqu’à ce que le PGCD soit exprimé à partir des entiers a et b dont on est parti de départ
à la fin, on obtient bien comme résultat deux entiers u et v tels que PGCD(a ,) = au + bv

Exemple : déterminer le PGCD de 294 et 25 puis un couple de Bézout qui est associé à ces deux entiers
. on commence donc par écrire les divisions euclidiennes en cascade jusqu’à trouver un reste nul
294 = 25 ×11 + 19
25 = 19 ×1 + 6
19 = 6 ×3 + 1
6 = 1 ×6 + 0
Le dernier reste non nul, que l’on obtient est 1 , ainsi on obtient comme résultat PGCD (294 ,25) = 1
On remonte ensuite les calculs fait précédemment pour trouver un couple de Bézout, de la manière suivante
1 = 19−6 ×3
= 19−(25−19× 1)×3
= 19 × 4−25× 3
= ( 294−25 ×11 ) × 4−25 ×3
= 294 × 4 + 25 ×(−47)
Finalement PGCD(294 ,25) = 294 × 4 + 25 ×(−47) ainsi (4 ,−47) est un couple de Bézout associé à
294 et 25
Remarque : il n’y a pas unicité du couple de Bézout associé à a et b comme on peut voir dans l’exemple :
.1 = 2 ×(−1) + 3 ×1 , ce qui montre que (−1 , 1) est un couple de Bézout associé à 2 et 3
. 1 = 2 ×2 + 3 × (−1 ) , ce qui montre que (2 ,−1) est un couple de Bézout associé à 2 et 3
Proposition: soit (a ,b ,d )∈ Z 3 alors on dit que d est un diviseur commun à a et b selon la condition
suivante :
si et seulement si d divise PGCD(a ,b)
¿ Démonstration : nous allons démontrer cette équivalence par double implication, ainsi ce qui nous donne :
(⇒) supposons pour cette première équivalence que d soit un diviseur commun à a et b
. d’après le théorème de Bézout, il existe (u , v )∈ Z 2 tel que PGCD(a ,b) = au + bv
¿ comme d∨a on obtient d∨au d’après les propriétés de la divisibilité
¿ de même, comme d∨b on obtient d∨bv
On peut donc conclure avec cette démonstration que l’on obtient bien comme résultat d∨¿ + bv ¿
(⇐) supposons pour cette deuxième équivalence réciproquement que d∨PGCD (a , b)
¿ comme PGCD ( a , b )∨a on obtient alors d∨a d’après les propriétés de la divisibilité
¿ de même, comme PGCD ( a , b )∨b on obtient d∨b
On peut conclure suite à cette démonstration que on bien démontré que d est un diviseur commun à a et b

c ¿ entiers premiers entre eux

. la notion de PGCD permet de définir celle d’entiers premiers entre eux ¿différent des nombres
premiers¿

Définition : soit (a ,b)∈ Z 2 on dit que a et b sont premiers entre eux lorsque on obtient PGCD(a ,b) = 1
Exemple : les exemples donnés montrent que 137 et 67 ainsi que 294 et 25 sont premiers entre eux
. en revanche avec l’exemple précédent on remarque que 685 et 160 ne sont pas premiers entre eux

Proposition: soient (a ,b)∈ Z 2 et d = PGCD(a ,b) alors il existe (a ' , b' )∈ Z 2 on obtient la condition
suivante :
a = da ' et b = db ' ainsi a ' et b ' soient premiers entre eux
Exemple : PGCD(10 , 15) = 5 et l’on obtient pour 10 = 5 ×2 et 15 = 5 ×3 avec PGCD(2 , 3) = 1
. la première forme du théorème de Bézout nous permet par ailleurs de démontrer une caractérisation
. sur les entiers premiers entre eux que l’on appelle encore théorème de Bézout

Théorème : soit (a ,b)∈ Z 2 alors on dit que a et b sont premiers entre eux selon la condition suivante :
si et seulement il existe (u , v )∈ Z 2 et au + bv = 1
Démonstration : nous allons démontrer cette équivalence par double implication, ainsi ce qui nous donne :
(⇒) supposons pour cette première équivalence que a et b sont premiers entre eux
. d’après le théorème de Bézout, il existe (u , v )∈ Z 2 tel que au + bv = 1
¿ comme PGCD(a ,b) = 1 alors on obtient comme résultat au + bv = 1
On peut donc conclure avec cette démonstration que l’on obtient bien au + bv = 1
(⇐) supposons pour cette deuxième équivalence réciproquement qu’il existe (u , v )∈ Z 2 tel que au + bv = 1
¿ soit d un diviseur positif pour a alors d∨a donc d∨au
¿ soit d un diviseur positif pour b alors d∨b donc d∨bv
. on en déduit que d∨¿+ bv ¿ c’est-à-dire d∨1 et comme d ≥ 0 , cela entraîne que d = 1
On peut conclure, le seul diviseur positif commun à a et b est 1 cela montre que a et b sont premiers entre
eux
Remarque : attention, cette proposition n’est vrai que pour des entiers qui sont premiers entre eux
. en générale, c’est pas parce qu’il existe un couple (u , v )∈ Z 2 tel que au + bv = d qu’on a PGCD(a ,b) =
d
. par exemple 3 ×5 + 2 ×(−5) = 5 on remarque que PGCD(3 , 2) = 1 ≠5 ! donc ils ne sont pas premiers

Exemple : démontrer que, pour tout n ∈ N , les entiers 4 n + 7 et 2 n + 3 sont premiers entre eux
. on remarque que ¿+ 7 ¿ ×1 + ¿+ 3 ¿ ×(−2) = 4 n + 7−4 n−6 = 1
. donc d’après la deuxième forme du théorème de Bézout, 4 n + 7 et 2 n + 3 sont premiers entre eux

d ¿ lemme de Gauß et corollaires

. le résultat suivant, se démontre à partir du théorème de Bézout, est très utile pour ce que nous allons voir

Théorème : soit (a ,b ,c )∈ Z 3 alors on obtient comme résultat selon la condition qui est la suivante :
si a∨(bc) et PGCD(a ,b) = 1 alors a∨c
Démonstration : supposons que a∨(bc) et que a et b sont premiers entre eux alors par la suite on obtient :
. d’après le théorème de Bézout, il existe (u , v )∈ Z 2 tel que au + bv = 1
¿ en multipliant l’égalité par c on obtient comme résultat auc + bvc = c
¿ on obtient a∨auc par définition et a∨bvc puisque a∨bc et bc∨bvc
On peut conclure suite à cette démonstration ainsi qu’on en déduit que a∨¿ + bvc ¿ c’est-à-dire que a∨c

Exemple : démontrer que tout diviseur impair de 142 divise 71

. soit n diviseur impair de 142 , alors n divise 71 ×2
. de plus, comme n est impair alors PGCD(n , 2) = 1
On peut donc conclure avec cette petite démonstration que d’après le lemme de Gauß , n divise 71
Exemple : démontrer si le double d’un entier n est un multiple de 5 , alors l’entier n est aussi un multiple de 5
. soit n un entier dont le double est un multiple de 5
. on obtient alors 5∨2n or il est clair que PGCD(5 , 2) = 1
On peut donc conclure que d’après le lemme de Gauß , on obtient 5∨n ce qui montre que n est un multiple
de 5

Proposition: soit (a ,b ,c )∈ Z 3 alors on obtient comme résultat selon la condition qui est la suivante :
si a∨c , b∨c et a et b sont premiers entre eux alors ab∨c
Démonstration : supposons que a∨c et également b∨c et aussi que a et b soient premiers entre eux
¿ comme a∨c il existe a ' ∈ Z tel que c = aa '
¿ comme b∨c il existe b ' ∈ Z tel que c = bb '
.on en déduit en particulier que a∨bb ' or a et b sont premiers entre eux, donc d’après le lemme de
Gauß a∨b '
On peut conclure par définition de divisibilité, il existe k ∈ Z tel que b ' = ak → c = bb ' = bak = ( ab ) k donc
a∨bc
Remarque : si l’on omet l’hypothèse et b sont premiers entre eux , cela donne que le résultat est faux
. par exemple 4∨12 et 6∨12 mais 4 ×6 = 24 en revanche on remarque que 24 ne divise pas 12
Proposition: soit (a ,b , p)∈ Z 3 alors on obtient comme résultat selon la condition qui est la suivante :
si p est premier et p∨ab alors p∨a ou p∨b
Démonstration : supposons que p soit premier, et également que p∨ab mais à la fois que p ne divise pas a
¿ puisque les seuls diviseurs positifs de p sont 1 et p , et que pn’est pas un diviseur de a
¿ le seul diviseur commun à a et pest 1 on obtient comme résultat pour PGCD( p , a) = 1
On peut donc conclure, suite à cette démonstration qu’avec le lemme de Gauß on obtient bien p∨b
Remarque : si l’on omet l’hypothèse qui est la suivante : est premier cela donne que le résultat est faux
. par exemple 14∨28 et on sait que 28 = 7 × 4 en revanche on remarque que 14 ne divise ni 7 ni 4

Proposition: soit (a ,b ,c )∈ Z 3 alors on obtient comme résultat selon la condition qui est la suivante :
si PGCD(a ,b) = 1 et PGCD(a ,c ) = 1 alors PGCD(a ,bc ) = 1
Démonstration : supposons que PGCD(a ,b) = 1 et PGCD(a ,c ) = 1 soit d un diviseur positif commun à
a et bc
. pour tout diviseur positif d ' qui est un diviseur commun à d et b , ainsi par la suite on obtient comme
résultat :
¿ comme d ' ∨a ¿ et d∨a ¿ et d ' ∨b
¿ d = 1 ¿ = 1 ¿ cela montre que PGCD(d , b) = 1
'

¿ comme d∨bc on en déduit que d’après le lemme de Gauß d∨c

On peut donc conclure, que le seul diviseur positif commun à a et bc est 1 et on en déduit que
PGCD(a ,bc ) = 1

e ¿ Plus Petit Commun Diviseur :

.on sait depuis longtemps le pendant du Plus Grand Commun Diviseur , est le
Plus Petit Commun Multiple
Définition : soit (a ,b) ∈ Z 2 l’ensemble des multiples strictement positifs commun admet un plus petit
élément
.on l’appelle PPCM de a et b , et on le note PPCM (a ,b)
Démonstration : posons A = { m ∈ N|m > 0 a et b } alors vérifions l’affirmation contenue dans cette
définition :
¿ comme a ≠ 0 et également b ≠ 0 on obtient alors ¿ ab∨¿ > 0
¿ de plus, ¿ ab∨¿ est clairement un multiple de a et un multiple de b
On peut conclure |ab|∈ A , ce qui montre que A est une partie non vide de N et A admet un plus petit
élément

Exemple : quel est le PPCM des entiers 9 et 12 ?

.les multiples strictement positifs de 9 sont dans l’ordre croissant : 9 , 18 , 27 ,36 etc
. les multiples strictement positifs de 12 sont dans l’ordre croissant : 12 , 24 , 36 etc
On peut conclure que le plus petit multiple strictement positif commun à 9 et 12 est 36 donc PPCM (9 , 12)
= 36
Remarque : pour tout (a ,b)∈¿ on a clairement les quatre relations qui sont les suivantes :
. PPCM (a , b) = PPCM (b , a)
. PPCM (a , b) = PPCM (|a|,|b|)
. PPCM (a , a) = ¿ a∨¿
. PPCM (a , 1) = ¿ a∨¿
Remarque : si a ∈ Z , alors le seul multiple commun à a et 0 par déduction c’est 0 , alors on étend ainsi la
notion de PPCM à tout couple de Z 2 en posant de plus, pour tout a ∈ Z , PPCM (a , 0) = 0 et
PPCM (0 , a) = 0
Proposition: soit (a ,b ,m)∈ Z 3 alors on obtient comme résultat selon la condition suivante :
alorsm est un multiple commun à a et b si et seulement si m est un multiple de PPCM ( a , b )
Démonstration : nous allons démontrer cette équivalence par double implication, ainsi ce qui donne :
(⇐) supposons pour cette première implication que m soit un multiple de PPCM (a ,b)
¿ on obtient alors a∨PPCM (a , b) et PPCM (a ,b)∨m donc a∨m
¿ on obtient alors b∨PPCM (a , b) et PPCM ( a , b )∨m donc b∨m
On peut donc conclure, suite à cette première implication que m est bien un multiple commun à a et b
(⇒) supposons pour cette deuxième implication que m soit un multiple commun à a et b
. si a = 0 ou b = 0, nécessairement m = 0donc m est un multiple de PPCM (a ,b), prenons le cas où a et
b≠0
. si PPCM (a ,b)≠ 0 alors il existe (q ,r ) ∈ Z 2 tel qu’on obtient m = q PPCM (a , b) + r avec 0 ≤ r <
PPCM (a ,b)
¿ puisque a∨m et a∨PPCM ( a , b ) , on obtient a∨(m−q PPCM ( a , b ) ) c’est-à-dire que a∨r
¿puisque b∨m et b∨PPCM ( a , b ) , on obtient b∨(m−q PPCM ( a , b ) ) c’est-à-dire que b∨r
On peut conclure r est un multiple positif commun à a et b , comme r < PPCM (a ,b) la seule possibilité est
r =0
Finalement on a bien démontré que m = qPPCM (a , b) et m est donc bien un multiple de PPCM (a ,b)

Proposition: soit (a ,b)∈ Z 2 alors on obtient comme résultat selon la condition qui est la suivante :
alors PGCD(a ,b) × PPCM (a , b) = ¿ ab∨¿
Démonstration : posons d = PGCD(a ,b) et m = PPCM (a ,b) alors montrons que dm = ab
. si a = 0 ou b = 0 on obtient par la suite ¿ ab∨¿ = 0 et m = 0 donc l’égalité est vraie, prenons le cas où a et
b≠0
. d’après un résultat précédent, il existe (a ' , b' )∈ Z 2 tel que a = da ' ainsi que b = db ' et PGCD(a ' ,b ') =
1
¿ da ' b ' ainsi par la suite on obtient ( d a ' ) b ' = ab ' donc da ' b ' est un multiple de a
¿ da ' b ' ainsi par la suite on obtient (d b' ) a' = b a ' donc da ' b ' est un multiple de b
On peut conclure pour cette première implication, on a démontré que da ' b ' est un multiple commun à a et b
¿
posons maintenant soit n ∈ N un multiple commun à a et b
¿comme a∨n il existe k ∈ Z tel que n = ak ainsi on obtient da ' k
¿ comme b∨n il existe l ∈ Z tel que n = bl ainsi on obtient db ' k
. on obtient donc da ' k = db ' l puis a ' k = b ' l car on sait que d ≠ 0 ainsi on en déduit que a ' ∨(b ' l)
. comme on a également PGCD(a ' ,b ') = 1 , cela entraîne donc d’après le lemme de Gauß que a ' ∨l
On peut conclure qu’il existe l ' ∈ Z tel que l = a ' l' on a n = db ' l = db ' a ' l ' donc d∨a' b' ∨¿ divise n et
' '
d∨a b ∨¿ ≤ n
. on a démontré que d |a ' b'| est le plus petit multiple positif commun à a et b donc d |a ' b'| = PPCM ( ab ) =
m
. cela entraîne que ¿ ab∨¿ = ¿ d 2 a' b' ∨¿ = d ×(d|a' b'|) = dm ce qui montre qu’on obtient bien le résultat
voulu

Exemple : quel est le PPCM de 685 et 160 ?

. nous avons trouvé dans un exemple précédent que PGCD(685,160) = 5 donc d’après la proposition ci-
dessus
. PPCM (685,160) = 685 ×160 /5 = 685 ×32 = 21920

5 ¿ Congruences:
. dans diverses situations, et notamment pour étudier les bases de numération et les critères de divisibilité
. auxquels nous nous intéresserons dans la prochaine partie, notamment il peut être pratique d’exprimer
. certaines des notions introduites jusqu’ici sous une forme différente, qui est celle des congruences

a ¿ définition et exemple :
 ¿
Définition : soient n ∈ Z et (a ,b) ∈ Z 2 ainsi on dit que les entiers a et b sont congrus modulo n et on
obtient
. lorsque n divise a−b on note alors a ≡ b(mod n)

Exemple : citer plusieurs entiers congrus à 17 modulo 6

. par exemple 17 ≡5 (mod 6) puisque 17−5 = 12 et 6∨12
. par exemple 17 ≡11(mod 6) puisque 17−11 = 6 et 6∨6
. par exemple 17 ≡−1(mod 6) puisque 17 + 1 = 18 et 6∨18
¿
Remarque : pour tous n ∈ Z et (a ,b)∈ Z 2 on a les trois propriétés évidentes qui sont les suivantes :
. a ≡ a(mod n)
. a ≡0 (mod n) si et seulement si a est un multiple de n
. a ≡b (mod n) si et seulement si b ≡ a(mod n)

Proposition: soient n ∈ Z ¿ et (a ,b)∈ Z 2 ainsi on obtient a ≡ b(mod n) selon la condition qui est la
suivante
si et seulement si a et b ont le même reste de la division euclidienne par n
Démonstration : nous allons démontrer cette équivalence par double implication, ainsi ce qui nous donne :
. notons q1 et r 1≤quotient et≤reste de la division euclidienne de a par n
. notons q2 et r 2 ≤quotient et≤reste de ladivision euclidienne de b par n }avec a = nq 1 + r 1 et b =

nq 2 + r 2
(⇒) supposons que a ≡ b ( mod n ) , alors par définition on obtient comme résultat n∨(a−b)
¿ comme par ailleurs n∨n(q1−q 2) on obtient aussi n∨( ( a−b )−n ( q1−q 2 ) )
¿or ( a−b )−n(q1−q 2) = ( a−nq 1 )−(b−nq2 ) = r 1−r 2 on en déduit que n∨(r 1−r 2)
. si l’on avait r 1−r 2 ≠ 0 on aurait ¿ n∨¿ ≤ ¿ r 1−r 2∨¿ ce qui est impossible puisque 0 ≤ r 1 < ¿ n∨¿ et 0 ≤ r 2
< ¿ n∨¿
On peut donc conclure, suite à cette première équivalence que r 1−r 2 = 0 ainsi on en déduit que r 1 = r 2
(⇐) supposons maintenant que a et b aient le même reste dans la division euclidienne par n
¿ alors r 1 = r 2 donc a−b = ¿ + r 1 ¿−¿ ¿ + r 2 ¿ = n(q1−q2 )
On peut donc conclure, suite à cette deuxième équivalence que nous avons bien obtenu que n divise a−b

Exemple : quel est le plus petit entier naturel congru à 25 modulo 4 ?

. d’après la proposition, le plus petit entier naturel congru à 25 modulo 4 est le plus petit entier naturel
. qui a le même reste que 25 dans la division par 4 , c’est-à-dire le reste de la division euclidienne de 25 par 4
. or 25 = 4 ×6 + 1 avec 0 ≤ 1 < 4 on peut conclure donc que le plus petit entier congru à 25 modulo 4 est 1

b ¿ Règles de calcul
. on dispose pour manipuler les congruences, d’un certain nombre de règles de calcul qui sont très pratiques

Proposition: soient n ∈ Z ¿ et (a ,b ,c )∈ Z 3 on obtient comme résultat selon la condition qui est la

suivante :
si a ≡ b(mod n) et b ≡ c (mod n) alors a ≡ c (mod n)
Démonstration : supposons que a ≡ b(mod n) et b ≡ c (mod n)
¿ d’une part a et b ont le même reste dans la division euclidienne par n
¿ d’autre part b et c ont le même reste dans la division euclidienne par n
On peut conclure, que a et c ont le même reste dans la division euclidienne par n ainsi que a ≡ c (mod n)

Proposition: soient n ∈ Z 2 ,(a , b)∈ Z 2 et c ∈ Z ¿ on obtient comme résultat selon les conditions suivantes :
 si a ≡ b(mod nc) alors a ≡ b(mod n)
si a ≡ b(mod n) alors ac ≡bc (mod nc)
Démonstration : vérifions les deux points cités précédemment, ainsi on obtient le résultat qui est le suivant :
1 ¿ supposons que a ≡ b(mod nc)
¿ alors par définition des congruences nc∨(a−b) or on a aussi n∨nc
¿ donc d’après les propriétés de la divisibilité on obtient n∨(a−b)
On peut donc conclure que pour ce premier point démontré, ainsi on en déduit que a ≡ b(mod n)
2 ¿ supposons que a ≡ b(mod n)
¿ alors n∨(a−b) donc il existe k ∈ Z tel que a−b = nk
¿donc on en déduit que ac−bc = ( a−b ) c = ( nk ) c = ( nc ) k
On peut donc conclure que pour ce deuxième point démontré, que nc∨(ac−bc) donc que
ac ≡bc (mod nc)

Proposition: soient n ∈ Z ¿ et (a ,a ' , b , b' )∈ Z 4 on obtient comme résultat selon les conditions suivantes :
si a ≡ a' (mod n) et b ≡ b' (mod n) alors a + b ≡ a ' + b ' ( mod n)
si a ≡ a' (mod n) et b ≡ b' (mod n) alors ab ≡ a' b' (mod n)
si a ≡ b(mod n) alors pour tout k ∈ N ,a k ≡ bk ( mod n)
¿ Démonstration : vérifions les trois points cités précédemment, ainsi on obtient le résultat qui est le suivant :
1 ¿ supposons que a ≡ a' (mod n) et b ≡ b' (mod n)
¿alors on obtient comme résultat n∨(a−a' ) et n∨(b−b ' )
¿donc n∨¿ + (b−b ' )¿ c’est-à-dire n∨¿ + b ¿−¿ + b ' ¿ ¿
On peut donc conclure que pour ce premier point démontré, ainsi on obtient a + b ≡ a ' + b ' (mod n)
2 ¿ supposons que a ≡ a' (mod n) et b ≡ b' (mod n)
¿alors n∨(a−a' ) de sorte qu’il existe k ∈ Z tel que a−a ' = kn , c’est-à-dire qu’on obtient a = a ' + kn
¿ alors n∨(b−b ' ) de sorte qu’il existe l ∈ Z tel que b−b ' = ln , c’est-à-dire qu’on obtient b = b '+ ln
¿ on obtient donc ab = ¿ + kn ¿ ¿ + ln ¿ = a ' b ' + knb ' + a ' ln + kl n2 = a ' b ' + n ¿ + a ' l + kln ¿
On peut conclure, ce deuxième point ab−a ' b ' = n ¿ + a ' l + kln ¿ donc n∨(ab−ab) ainsi
' '
ab ≡ a b (mod n)

3 ¿ supposons que a ≡ b(mod n) et démontrons le résultat par récurrence

. Initialisation: pour tout k ∈ N , notons P(k) l’assertion {a} ^ {k} ≡ {b} ^ {k} ( mod n
¿nous savons que a 0 = 1 et b 0 = 1 or il est évident que 1 ≡1(mod n)
On peut conclure qu’on a bien obtenu comme résultat a 0 ≡ b0 ( mod n ) , ce qui montre que P(0) est vraie
. Hérédité : soit k ∈ N tel que P(k) soit vraie, c’est-à-dire tel que a k ≡ bk ( mod n)
¿ nous avons par hypothèse a ≡ b(mod n) ainsi d’après le point précédent a k × a ≡b k × b(mod n)
On peut conclure que P ¿ + 1 ¿ est vraie, d’après le principe de récurrence, P(k) est vraie pour tout k ∈ N
. autrement dit, on obtient donc comme résultat pour tout k ∈ N ,a k ≡ bk ( mod n)

Exemple : soient a et b deux entiers relatifs, le reste de la division euclidienne de a par 8 est 4 et que le reste
de la division euclidienne de b par 8 est 5. Quel est alors le reste de la division euclidienne de 3 a + b par 8 ?
. comme le reste de la division euclidienne de a par 8 est 4 on obtient a ≡ 4 (mod 8)
. comme le reste de la division euclidienne de b par 8 est 5 on obtient b ≡5 (mod 8)
D’après le point ( 2 ) , on a donc 3 a ≡3 × 4 ( mod 8 ) , c’est-à-dire 3 a ≡12 ( mod 8 ) donc 3 a ≡ 4 ( mod 8 )
D’après le point ( 1 ) , on a 3 a + b ≡ 4 + 5 ( mod 8 ) ,c’est-à-dire 3 a + b ≡ 9(mod 8) donc 3 a + b ≡1 (mod 8)
Comme de plus 0 ≤ 1 < 8 le reste de la division euclidienne de 3 a + b par 8 est 1
Exemple : quel est le reste de la division euclidienne de 1234 567 par 5 ?
. on remarque que 1234 ≡ 4 (mod 5) puisque 1234−4 = 1230 et 5∨1230
. d’après le point ( 3 ) , on a donc 1234 2 ≡ 42 ( mod 5 ) , soit 1234 2 ≡16 (mod 5) donc que
2
1234 ≡1(mod 5)
. toujours d’après le point ( 3 ) , on a alors ¿ c’est-à-dire 1234 567 ≡ 4( mod 5)
. enfin, d’après le point ( 2 ) , on a 1234 566 ×1234 ≡ 1× 4 ( mod 5 ) , c’est-à-dire 1234 567 ≡ 4(mod 5)
Comme de plus 0 ≤ 4 < 5 le reste de la division euclidienne de 1234 567 par 5 est 4

3 ¿ Corollaires dulemme de Gauß en termes de congruences :

. en plus des trois corollaires que nous avons déjà présentés précédemment dans la partie précédente
. il existe le lemme de Gau ß permet de démontrer un certain nombre de propriétés des congruences

Proposition: soient n ∈ Z ¿ et (a ,b ,c )∈ Z 3 on obtient comme résultat selon les conditions suivantes :

si ab ≡ 0(mod n) et a et n sont premiers entre eux, alors b ≡ 0(mod n)
si ab ≡ ac (mod n) et a et n sont premiers entre eux, alors b ≡ c (mod n)
Démonstration : démontrons chacun des deux points en utilisant le lemme de Gau ß ainsi ce qui nous donne :
1 ¿ supposons que ab ≡ 0(mod n) et PGCD (a ,n) = 1
¿ comme ab ≡ 0(mod n) on obtient alors n∨ab par définition des congruences
¿comme de plus PGCD(a ,n) = 1 , on obtient alors n∨b d’après le lemme de Gauß
On peut donc conclure, que pour ce premier point on obtient b ≡ 0(mod n) par définition des congruences
2 ¿supposons que ab ≡ ac (mod n) et PGCD(a ,n) = 1
¿ comme ab ≡ ac (mod n) on obtient alors n∨( ab−bc ) , c’est-à-dire n∨a(b−c)
¿ comme de plus PGCD(a ,n) = 1 , on obtient alors n∨(b−c ) d’après le lemme de Gauß
On peut donc conclure, que pour ce deuxième point on obtient comme résultat b ≡ c (mod n)
Remarque : attention, ces propriétés sont fausses si on oublie l’hypothèse et n sont premiers entre eux
. 2× 9 ≡0 (mod 6) mais 9 ≢ 0(mod 6)
. 2× 1≡ 2× 4 (mod 6) mais 1 ≢ 4(mod 6)

Exemple : démontrer que si le reste de la division euclidienne de 3 n par 5 est 3 alors le reste de n par 5 est 1
. supposons que le reste de la division de 3 n par 5 soit 3 alors 3 n ≡3(mod 5) donc 3 ×n ≡ 3× 1(mod 5)
¿ or 3 et 5 sont clairement premiers entre eux puisque ce sont deux nombres premiers distincts
¿ donc d’après le point ( 2 ) , n ≡1(mod 5) puisque 0 ≤ 1 < 5 cela montre le reste de la division de n par 5 est
1

Proposition: soient (m , n)∈ ¿¿ et a ∈ Z on obtient comme résultat selon la condition qui est la suivante :
si a ≡ 0 ( mod m ) ,a ≡ 0(mod n) et m et n sont premiers entre eux, alors a ≡ 0(mod mn)
Démonstration : supposons que a ≡ 0 ( mod m ) ,a ≡ 0(mod n) et PGCD(m , n) = 1 ainsi, ce qui nous
donne :
¿ comme a ≡ 0(mod m) alors on obtient comme résultat m∨a
¿ comme a ≡ 0(mod n) alors on obtient comme résultat n∨a
¿ comme m et n sont premiers entre eux, corollaire du lemme de Gauß démontré entraîne alors que
mn∨a
On peut donc conclure, que pour cette démonstration on a bien obtenu le résultat qui est a ≡ 0(mod n)
Remarque : encore une fois, le résultat est faux si l’on oublie l’hypothèse et n sont premiers entre eux
. 12≡ 0(mod 4) et 12 ≡0(mod 6) mais 4 ×6 = 24 et 12 ≢0 (mod 24)
Exemple : démontrer que, si les restes des divisions euclidiennes de n par 7 et de n par 11 sont tous les deux 4
. supposons que les restes des divisions euclidiennes de n par 7 et de n par 11 soient 4 et aussi n par 77 est 4
. on obtient donc n ≡ 4(mod 7) et n ≡ 4(mod 11) on déduit que n−4 ≡ 0(mod 7) et n−4 ≡ 0(mod 11)
. or 7 et 11 sont clairement premiers entre eux puisque ce sont deux nombres premiers distincts
. donc d’après la proposition ci-dessus, on obtient comme résultat n−4 ≡ 0 ( mod 77 ) , puis n ≡ 4(mod 77)
. comme 0 ≤ 4 < 77 alors cela montre que le reste de la division euclidienne de n par 77 est 4
5 ¿ Bases de numération :
'
a ¿ Décomposition d un entier dans une base
. nous utilisons actuellement la base 10 ,ainsi que la base 2 et la base 16 en informatique
. il est possible de décomposer un nombre entier dans n’importe quelle base, d’après le théorème suivant

Théorème : soit r ∈ N tel que r ≥ 2 , alors pour tout n ∈ N ¿ il existe un unique entier k ∈ N et une unique
famille (n 0 , n1 , … , nk ) d’entiers compris entre 0 et r −1 avec n k ≠ 0 ainsi ce qui donne la formule suivante :
k
n = ∑ ni r i = n k r k + n k−1 r k−1 + … + n1 r 1 + n 0 r 0
i=0
Cette écriture est la décomposition de n en base r , on dit que n 0 , … , nk sont les entiers de cette
décomposition
. lorsque r ≤ 10 on note parfois n = n k n k−1 … n1 n0r
Démonstration : nous allons démontrer séparément l’existence et l’unicité de la décomposition, ce qui donne
Existence : pour tout n ∈ N ¿ , notons P(n) l’assertion il existe k ∈ N et une famille (n 0 , … , nk ) avec
n k ≠ 0 tels que n = n k r k + n k−1 r k−1 + … + n1 r 1 + n 0 r 0
Initialisation: posons pour tout n ∈ ⟦ 1 ,r −1 ⟧ ainsi on obtient le résultat qui est le suivant :
¿ alors en posant n 0 = n on obtient la décomposition qui est la suivante n = n 0 r 0 qui est la forme voulue
On peut donc conclure, pour cette initialisation cela montre que P(n) est vraie dans ce cas
Hérédité : posons pour tout n ∈ N ¿ tel que n ≥ r −1 ainsi on obtient le résultat qui est le suivant :
. supposons que P(m) soit vraie pour tout m ∈ ⟦ 1 , n ⟧ ainsi ce qui donne le résultat suivant :
¿ d’après le théorème de la division, on sait qu’il existe un unique couple (q , s) ∈ Z 2 tel que n + 1 = qr + s
¿ mais q ≥ 1 et q ≤ n ¿ ≥ n + 1 donc qr ≥ 2 ¿ + 1 ¿ et donc qr + s > n + 1 ce qui est impossible¿
k
Ainsi, P(q ) est vraie, il existe k ∈ N et une famille (q ¿ ¿ 0 , … , qk )¿ avec q k ≠ 0 tels que q = q k r + … +
1 0
q1r + q0r
¿ puisque n + 1 = qr + s nous avons alors n + 1 = q k r k+1 + q k−1 r k + … + q 1 r 2 + q 0 r 1 + sr 0
¿ comme q k ≠ 0 alors q k , … ,q 0 sont compris entre 0 et r −1 on a décomposé n + 1 sous la forme voulue
¿
On peut conclure que P ¿ + 1 ¿ est vraie d’après le principe de récurrence, P(n) est vraie pour tout n ∈ N

Unicité : soit n ∈ N ¿ , considérons deux entiers k ∈ N et l ∈ N et deux familles (n ¿ ¿ 0 ,… ,n k )¿ et

(m ¿ ¿ 0 , … , ml)¿
n k ≠ 0 et ml ≠ 0 tels que n = n k r k + … + n 0 r 0 et m = ml r l + … + …+ m0 r 0
¿ comme n k ≥ 1 tous les entiers sont positifs, d’une part r k ≤ n k r k et d’autre part n k r k ≤ n k r k + … + n 0 r 0
¿ par ailleurs, comme tous les chiffres sont inférieurs à r −1 on a n k r k + … + n 0 r 0 ≤ (r −1)¿ + … + r 0 ¿
Mais nous savons que r k + … + r 0 = r k −1−1 /r−1 ce qui entraîne que (r −1)¿ + … + r 0 ¿ = r k +1−1
¿ finalement, en rassemblant toutes ces inégalités, on obtient comme le résultat suivant r k ≤ n ≤ r k +1−1
¿ on peut obtenir le même résultat r l ≤ n ≤ r l +1−1 et d’autre part r l ≤ r k +1 ainsi que l < k + 1 donc l ≤ k
On peut donc conclure, que k = l ce qui signifie que les deux décompositions ont le même nombres de termes
Enfin, il faut montrer que les chiffres sont égaux deux à deux, supposons qu’il existe j ∈ ⟦ 0 , k ⟧ tel que n j ≠ m j
¿ l’ensemble A = { i ∈ ⟦ 0 ,k ⟧|ni ≠ mi } est une partie non vide de N et admet donc un plus petit élément
¿ il admet un plus petit élément d’après les propriétés de l’ordre sur les entiers naturels, ainsi notons le i 0
Dans les deux décompositions, les chiffres dont l’indice est strictement inférieur à i 0 sont égaux deux à deux
Nous pouvons donc simplifier l’égalité pour ne garder que les termes dont l’indice est supérieur à i 0ainsi on a :
k i k i
n k r + … + ni r = m k r + … + m i r
0
0

0
0

Comme toutes les puissances de r qui apparaissent dans les deux sommes restantes sont supérieur à r i 0
Nous pouvons diviser chacune d’entre elles par r i0 ainsi ce qui nous donne le résultat qui est le suivant :
k −i 0
+ … + ni0 +1 r + ni0 = m k r + … + m i0+1 r + m i0
k−i 0
nk r
Nous pouvons factoriser chacune d’entre elles par r ainsi ce qui nous donne le résultat qui est le suivant :
r ¿ + … + ni0 +1 ¿ + ni0 = r ¿ + … + mi0+1 ¿ + mi0
¿ n k r k −i −1 + … + ni +1 et mk r k−i −1 + … + mi +1 sont deux entiers et qu’on a ni et mi ∈ ⟦ 0 , r −1 ⟧
0
0
0
0 0 0

Par unicité de la division euclidienne, les deux restes doivent être égaux, c’est-à-dire ni = m i ce qui absurde
0 0

On peut conclure qu’on a bien démontré que les deux décompositions avaient le même nombre de termes
et également que tous leurs chiffres étaient égaux deux à deux, ainsi ce qui achève la preuve de l’unicité
Exemple : quelle est la décomposition en base 2 de l’entier 25 ?
Pour trouver la décomposition de 25 , on effectue des divisions euclidiennes par 2 jusqu’à avoir un quotient nul
. la division euclidienne de 25 par 2 s’écrit 25 = 2 ×12 + 1
.la division euclidienne de 12 par 2 s’écrit 12 = 2 ×6 + 0
. la division euclidienne de 6 par 2 s’écrit 6 = 2 ×3 + 0
. la division euclidienne de 3 par 2 s’écrit 3 = 2 ×1 + 1
. la division euclidienne de 1 par 2 s’écrit 1 = 2 ×0 + 1
On obtient donc 25 = 2 ׿ + 1 ¿ + 0 + 0 ¿ + 1 = 24 ×1 + 23 ×1 + 22 ×0 + 2 ×0 + 1
On peut conclure, l’écriture 25 en base 2est 25 = 1 ×24 + 1 ×23 + 0 ×22 + 0 ×21 + 1 ×20 ou 25 = 1 10 0 12
Exemple : quelle est la décomposition en base 60 de l’entier 12 434 ?
On procède comme dans l’exemple précédent, en faisant cette fois des divisions euclidiennes en base 60:
. la division euclidienne de 12 434 par 60 s’écrit 12 434 = 60 ×207 + 14
. la division euclidienne de 207 par 60 s’écrit 207 = 60 ×3 + 27
. la division euclidienne de 3par 60 s’écrit 3 = 60 ×0 + 3
On obtient donc 12 434 = 60 ×207 + 14 = 60 ׿ + 27 ¿ + 14 = 602 ×3 + 60 ×27 + 14
On peut donc conclure, que l’écriture de 12 434 en base 60 est 12 434 = 3 ×60 2 + 27 × 601 + 14 × 600

b ¿ Critères de divisibilité :
.chaque base de numération, on dispose de critère de divisibilité qui dépend des propriétés l’entier de base
. nous allons présenter et démontrer dans cette partie les principaux critères de divisibilité en base 10

Proposition: soit n ∈ N ¿ notons n = n k 10k + n k−1 10k−1 + … + n1 101 + n 0 100 sa décomposition en base 10
:
1 ¿ n est divisible par 2 si et seulement si n 0 ∈{0 , 2 , 4 , 6 , 8 }
2 ¿ n est divisible par 3 si et seulement si n 0 + … + n1 + … + n k est divisible par 3
3 ¿ nest divisible par 5 si et seulement si n 0 ∈{0 , 5 }
4 ¿ nest divisible par 9 si et seulement si n 0 + … + n1 + … + n k est divisible par 9
5 ¿ nest divisible par 10 si et seulement si n 0 = 0

Démonstration : nous allons, pour une fois raisonner directement par équivalences, ainsi ce qui donne :
1 ¿ comme 2∨10 nous avons 10 ≡0 (mod 2), pour tout i∈ ⟦ 1 , k ⟧ 10i ≡0i (mod 2) puis ni 10i ≡0(mod 2)
¿ nous pouvons en déduire que n ≡ n0 (mod 2) ainsi 2∨n alors n ≡ 0(mod 2) donc n 0 ≡ 0(mod 2) ainsi
2∨n0
¿ mais, puisque n 0 est compris entre 0 et 9 , 2∨n0 doncn 0 ∈{0 , 2 , 4 , 6 , 8 } finalement, 2∨n et
n 0 ∈{0 , 2 , 4 , 6 , 8 }
Ainsi, on a bien démontré que n est divisible par 2 si et seulement si son chiffre des unités est 0 , 2 , 4 , 6 ou 8
2 ¿ comme 10 = 3 ×3 + 1on a 10 ≡1(mod 3) , pour tout i ∈ ⟦ 0 , k ⟧ 10 i ≡1 (mod 3) puis
i
ni 10 ≡ni (mod 3)
¿ nous pouvons en déduire que n ≡ n0 + n1 + … + n k−1 + n k (mod 3)
¿ ainsi 3∨n donc n ≡ 0(mod 3) alors n 0 + n1 + … + n k ≡ 0(mod 3) finalement 3∨¿ + n1 + … + n k ¿
Ainsi, on a bien démontré que n est divisible par 3 si et seulement si la somme de ses chiffres est divisible par 3
3 ¿ on procède de manière similaire que n est divisible par 5 si et seulement si son chiffre des unités est 0 ou 5
4 ¿ on procède de manière similaire, n est divisible par 9 si et seulement si la somme est divisible par 9
5 ¿ on procède de manière similaire, n est divisible par 10 si et seulement si son chiffre des unités est 0

Exemple : l’entier 25 764 est-il divisible par 2 ? par 3 ? par 9 ? par 6 ? par 18 ?
. le chiffre des unités de 25 764 est 4 on remarque que 4 ∈{0 ,2 , 4 ,6 ,8 }
On peut donc conclure que d’après le critère de divisibilité ( 1 ) ,on remarque que 25 764 est divisible par 2
. la somme des chiffres de 25 764 est 24 on remarque que 24 est divisible par 3
On peut donc conclure que d’après le critère de divisibilité ( 2 ) , on remarque que 25 764 est divisible par 3
. le chiffre des unités de 25 764 est 4 on remarque que 4 ∉{0 ,5 }
On peut conclure que d’après le critère de divisibilité ( 3 ) , on remarque que 25 764 n’est pas divisible par 5
. la somme des chiffres de 25 764 est 24 on remarque que 24 n’est pas divisible par 9
On peut conclure que d’après le critère de divisibilité (4), on remarque que 25 764 n’est pas divisible par 9
. nous avons déjà vu que 25 764 était divisible par 2 et 3 qui sont clairement premiers entre eux
On peut donc conclure, d’après un corollaire du lemme de Gau ß , 25 764 est divisible par 2 ×3 c’est-à-dire 6
. puisque 18 = 2 ×9 nous avons 9∨18 si nous avions 18∨25764 nous aurions alors 9∨25 764
On peut conclure, nous avons déjà que 25 764 n’est pas divisible par 9 donc 25 764 n’est pas divisible par 18

. en utilisant les congruences, nous pouvons par ailleurs trouver et démontrer de nombreux autres critères
de divisibilité en base 10 par des entiers moins standard par exemple : 4, 7, 8, 13, 19, 23
Exemple : déterminer et démontrer que un critère de divisibilité par 4 en base 13 , ainsi ce qui donne le
résultat
. soit n ∈ N ¿ un entier dont la décomposition en base 13 est n = n k 13k + n k−1 13k−1 + … + n1 13 + n 0
¿ puisque 13 = 4 ×3 + 1 nous avons donc 13 ≡1(mod 4)
¿ en conséquence, pour tout i∈ ⟦ 1 , k ⟧ alors 13i ≡1(mod 4) et ni 10i ≡ni (mod 4)
¿ n ≡ nk + n k−1 + … + n1 + n 0( mod 4 ) ainsi 4∨n donc n ≡ 0 ( mod 4 ) , n k + n k−1 + … + n1 + n 0 ≡ 0(mod 4)
Alors on peut en déduit qu’on obtient comme résultat 4∨¿ + n k−1 + … + n1 + n 0 ¿
On peut conclure, on a démontré que n est divisible par 4 si et seulement si la somme chiffre est divisible par
4

6 ¿ Décomposition des entiers en produits de nombres premiers :

a ¿ Théorème fondamental de l ' arithmétique :

Théorème : pour tout n ∈ N tel que n ≥ 2 , il existe k ∈ N ¿ une famille ( p1 , … , p k ) de nombres premiers
k
n = ∏ p αi = pα1 × pα2 × … × pαk avec p1 < p2 < … < pk
i 1 2 k

i=1
Et d’une famille (α 1 ,… α k ) d’entiers naturels non nuls et on peut dire que cette décomposition est unique
Démonstration : nous allons raisonner par récurrence (forte) ainsi on obtient le résultat qui est le suivant :
Existence : pour tout n ∈ N , notons P ( n ) l’assertion peut s’écrire comme un produit de nombres premiers
Initialisation: pour démontrer l’initialisation, il faut démontrer que P(2) est vraie en partant avec n ≥ 2
¿puisque 2 un nombre premier, il est clair que 2 s’écrit comme un produit de nombres premiers, P ( 2 ) est vrai
Hérédité : soit n ∈ N tel que n ≥ 2 et P ( q ) soit vraie pour tout q ∈ ⟦ 2 , n ⟧ ainsi on obtient comme résultat :
¿ comme n + 1 > n ≥ 2 nous savons par un résultat du cours que n + 1 admet un diviseur premier, notons-le p
¿
Ainsi, il existe alors q ∈ N tel que n + 1 = qp alors distinguons maintenant deux cas :
¿ supposons que q = 1 alors n + 1 = p il est donc clair que n + 1 s’écrit comme un produit de nombres
premiers
¿ supposons que q > 1 , c’est-à-dire que q ≥ 2 par ailleurs p ≥ 2 puisque p est premier on a également q < n +
1
Ainsi, q ∈ ⟦ 2 , n ⟧ et donc P(q ) est vraie cela implique que q s’écrit comme un produit de nombres premiers
On peut conclure, d’après le principe de récurrence, tout entier n ∈ N tel que n ≥ 2 peut s’écrire comme un
produit de nombres premiers, et donc en particulier sous la forme voulue, ce qui achève la démonstration
Unicité : soient deux entiers naturels non nuls k et l deux familles de nombres premiers deux à deux distincts
( p1 , … , p k ) et (q ¿ ¿ 1 ,… ,q l)¿ et deux familles (α ¿ ¿ 1 , … , α k )¿ et (β ¿ ¿ 1 , … , β l )¿ tels que n =
α1 αk β1 βl
p1 × … × pk = q 1 × …× q l
. commençons alors par démontrer que les nombres premiers apparaissant dans ces deux décompositions de
n sont les mêmes, c’est-à-dire que l = k et pour tout i∈ ⟦ 1 , k ⟧ ainsi on obtient comme résultat pi= q i
¿ soit i∈ ⟦ 1 , k ⟧ , alors pi∨( pα1 × … × pαk ) donc pi∨(q β1 × …× qlβ ) or pi est un nombre premier donc
1 k 1 l

d’après un lemme de Gauß , ainsi pi divise l’un des facteurs de ce produit, il existe j ∈ ⟦ 1 ,l ⟧ tel que pi∨q j
¿ mais q j est aussi un nombre premier, donc pi = q j nous avons donc démontré que
{ p1 , … , p k }⊂ { p1 ,… , q l }
par symétrie, on a également { q 1 ,… , q l } ⊂ { p1 , … , pl } on en déduit { p1 , … , p k } = {q1 , … , ql } donc que
k = l On peut conclure, pour tout i∈ ⟦ 1 , k ⟧ on obtient pi = q i nous avons ainsi n = pα1 × … × pαk =
1 k

β β
p1 × … × pk
1 k

. montrer que les exposants sont égaux deux, supposons par l’absurde qu’il existe i 0 ∈ ⟦ 1 , k ⟧ tel que α i ≠ β i
0 0
k k
k k
n = ∏ p αi = ∏ p βi ce qui nous donne ∏ p i = ∏ p i × pi 0
βαi β −α i i0 i0
i i

i=1 i=1
i=1 i=1 i ≠i 0 i≠ 0
¿comme β i 0−α i 0 > 0 alors pi 0 divise le membre de droite on en déduit qu’il divise le membre de gauche
Or pi 0 est premier, donc d’après le corollaire du lemme de Gau ß , alors pi 0 divise l’un des facteurs de ce
produit
C’est absurde, car tous les facteurs sont des nombres premiers distincts de pi 0 pour touti∈ ⟦ 1 , k ⟧ on a α i = β i
On peut donc conclure, finalement nous avons bien démontré, les deux décompositions de n sont les mêmes

Exemple : quelle est la décomposition de 132 en produit de nombres produits ?

. on remarque que 132 est divisible par 2 ainsi on peut l’écrire sous la forme de 132 = 2 ×66
. on remarque que 66 est lui-même divisible par 2 et 66 = 2 ×33 de sorte que 132 = 22 ×33
. on remarque que 33 est lui-même divisible par 3 et 33 = 3 ×11 de sorte que 132 = 22 ×3 ×11
Comme 2 , 3 et 11 sont trois nombres premiers rangés en ordre strictement croissant, on obtient cette écriture
Exemple : quelle est la décomposition de 630 en produit de nombres premiers ?
. on remarque que 630 est divisible par 2 ainsi on peut écrire sous la forme que 630 = 2 ×315
. on remarque que 315 est lui-même divisible par 3 et 315 = 3 ×105 de sorte que 630 = 2 ×3 ×105
.on remarque que 105 est lui-même divisible par 3 et 105 = 3 ×11 de sorte que 630 = 2 ×32 ×35 = 5 ×7
Comme 2 , 3 ,5 et 7 sont quatre nombres premiers rangés en ordre strictement croissant, on obtient ce
résultat
Remarque : la principale raison pour laquelle on choisit d’exclure 1 de la définition des nombres premiers est
si on acceptait 1 comme nombre premier, il n’y aurait pas unicité de la décomposition dans ce théorème :
. par exemple 132 = 1 ×22 × 3 ×11 ou encore 132 = 12 × 22 × 3× 11
b ¿ Applications du théorème fondamental de l ' arithmétique :

Proposition: soit n ∈ N tel que n ≥ 2, n = pα1 1 × p α2 2 × …× p αk

k la décomposition de n en nombres
premiers
p1 × p 2 × …× p k avec pour tout i∈ ⟦ 1 , k ⟧ et 0 ≤ β i ≤ α i
β1 β2 βk

Alors, l’ensemble des diviseurs positifs de n est l’ensemble des entiers qui s’écrivent sous la forme précédente
Démonstration : montrer que l’ensemble diviseur positif de n est égal
{ p β1 1 ×… × p βkk ∈ ⟦ 0 , α1 ⟧ × … × ⟦ 0 , ak ⟧ }
(⊃) soit d ∈ D alors il existe ( β 1 ,… , β k ) ∈ ⟦ 0 , α 1⟧ ×… × ⟦ 0 , α k ⟧ tel qu’on a comme résultat d =
β1 βk
p1 × … × pk
 k = ( p 1 … pk ) × ( p1 ) = d × ( p α1 1− β 1 … p αk−βk ) pour i∈ ⟦ 1 , k ⟧ β i−α i ≥ 0
β1 βk α 1−β 1
n = pα1 1 × … × pαk … pαk−
k
βk
k
On peut donc conclure, cette première inclusion on remarque que d est un diviseur ¿clairement positif¿ de n
(⊂) soit réciproquement d ∈ D un diviseur positif de n un raisonnement du même type que celui pour
prouver l’unicité la décomposition en produit de nombre premier permet de montrer que d peut s’écrire sous
la forme :
On peut écrire d sous la forme p1 × … × pk avec ( β 1 ,… , β k ) ∈ N puis que pour tout i∈ ⟦ 1 , k ⟧ et β i ≤
β1 βk k

αi

Exemple : quels sont les diviseurs positifs de 132 ?

On a déterminé dans un exemple que la décomposition de 132 en produit de nombre premier est 22 ×3 ×11
0 0 0 1 0 0 2 0 0
. 2 × 3 ×11 = 1 .2 × 3 ×11 = 2 . 2 × 3 × 11 = 4
0 1 0 1 1 0 2 1 0
. 2 × 3 × 11 = 3 . 2 × 3 × 11 = 6 .2 × 3 × 11 = 12
0 0 1 1 0 1 2 0 1
. 2 × 3 ×11 = 11 .2 × 3 ×11 = 22 . 2 × 3 × 11 = 44
0 1 1 1 1 1 2 1 1
. 2 × 3 × 11 = 33 . 2 × 3 × 11 = 66 . 2 × 3 × 11 = 132

Remarque : on peut utiliser un arbre pour être sûr de n’oublier aucun diviseur dans l’exemple ci-dessus on a :

Proposition: soit n ∈ N tel que n ≥ 2 , n = pα1 1 × p α2 2 × …× p αk

k la décomposition de n en nombres
premiers
alors n admet exactement ¿ + 1 ¿ ׿ + 1 ¿ ×… ׿ + 1 ¿ diviseurs positifs
Démonstration : les éléments de l’ensemble D qui est introduit dans la question précédente ont α 1 + 1 valeurs
possibles pour la puissance β 1 ainsi on obtient α 2 + 1 valeurs possibles pour la puissance β 2 et ainsi de suite …
¿ les éléments obtenus en choisissant des k -uplets de puissances différents sont bien deux à deux distincts
On peut conclure, que le cardinal de l’ensemble D est ¿ ¿ + 1 ¿ ×… ׿ + 1 ¿ ce qui donne le résultat voulu

Exemple : combien 132 admet-il de diviseurs positifs ?

. on a déterminé dans un exemple que la décomposition de 132 en produit de nombre premier est 22 ×3 ×11
. d’après la proposition ci-dessus, 132 = ¿ + 1 ¿ ׿ + 1 ¿ ׿ + 1 ¿ = 12 ainsi 132 admet 12 diviseurs positifs

Proposition: soit ( a , b ) ∈ ¿ ¿donc il existe k ∈ N ¿ une famille ( p1 , … , p k ) de nombre premiers deux à deux
a = pα1 1 × … × pαk β1
k et b = p1 × … × pk
βk

Deux familles (α ¿ ¿ 1 , … , α k )¿ et (β 1 ,… , β k ) d’entiers positifs ou nuls tels qu’on obtient les deux formules
suivantes
min ⁡(αk , βk )
. PGCD(a , b) = pmin
1
⁡(α 1, β 1)
× … × pk
(α 1 ,β 1) max (αk , βk )
. PPCM (a , b) = pmax
1 × … × pk

L’existence de décomposition de la forme indiquée pour a et b est une conséquence directe du théorème de
l’arithmétique, ces décompositions s’obtiennent à partir de leur décomposition usuelle en nombres premiers

Démonstration : démontrons la formule donnant le PGCD et prouvons que l'on a bien PGCD(a ,b) = d
→ posons I = { i ∈ ⟦ 1 , k ⟧ } de manière, la décomposition de a en nombre premier, à l’ordre près a = ∏ p i
αi

i ∈I
Alors pour tout i∈ ⟦ 1 , k ⟧ ¿ on obtient alors α i = 0 donc min(α ¿ ¿ i , βi )¿ = 0 on en déduit que d =
∏ p min(αi
i
, βi)

i ∈I
De plus, pour tout i∈ I , on obtient 0 ≤min( α i , βi ) ≤ α i donc d’après la caractérisation des diviseurs vue plus
haut, on en déduit que d divise a ainsi on montre exactement de la même manière que d divise également b
On peut donc conclure ainsi pour ce premier point, on remarque que d est un diviseur commun à a et b
→ maintenant il reste à montrer que c’est le plus grand, donc soit n un diviseur positif commun à a et b
Comme n∨a et a = ∏
i ∈I
αi
p i il existe toujours d’après la caractérisation des diviseurs une famille ¿ ¿
En complétant cette famille avec de entier nul, on déduit qu’il existe une famille (γ ¿ ¿ 1 , … , γ k )¿ d’entiers
telle que :
k
n = ∏ p γii avec pour tout i∈ ⟦ 1 , k ⟧ et 0 ≤ γ i ≤ α i
i=1
Par ailleurs n∨b , pour tout i∈ ⟦ 1 , k ⟧ et 0 ≤ γ i ≤ β i donc n = p1 × … × pk avec 0 ≤ γ i ≤ min ⁡(α i , β i) donc
γ1 γk

n≤d
On peut donc conclure, que d est le plus grand diviseur commun à a et b , c’est-à-dire que d = PGCD(a ,b)
Exemple : que valent PGCD(630 , 132) et PPCM (630,132)
. nous avons vu dans des exemples précédents que l’écriture de 132 = 22 ×3 ×11 et 630 = 2 ×32 ×5 ×7
Pour trouver le PGCD et le PPCM de ces deux entiers, on peut commencer par réécrire leurs
décompositions En faisant apparaître, les nombres premiers qui apparaissent dans l’autre, quitte à utiliser des
exposants nuls
. PGCD (630,132) = 21 × 31 × 50 ×70 ×110 = 2 ×3 = 6
. PPCM (630,132) = 22 ×32 ×51 × 71 ×111 = 4 ×9 ×5 × 7 ×11 = 13 860
Remarque : ces deux formules ne sont en fait pas du tout efficaces en pratique, pour de grands entiers, il est
plus rapide d’appliquer l’algorithme d’Euclide que de déterminer les décompositions en nombres premiers

7 ¿ équations diophantiennes:

Dans cette dernière partie du chapitre d’arithmétique, nous allons mettre en pratique certains résultats vus
dans les parties précédentes afin de résoudre ce que l’on appelle des équations diophantiennes

La résolution des équations diophantiennes est un domaine des mathématiques particulièrement difficile.
Par exemple, le grand théorème de Fermat qui affirme pour tout entier n ≥ 3 l’équation diophantienne
x + y = z d’inconnue (x , y , z)∈¿ ¿ n’admet pas de solution, a été démontré qu’en 1995, plus de trois
n n n

siècles après la mort de Fermat dans un article de plus de cent pages qui s’appuie lui-même sur des centaines
Dans ce cours, nous serons beaucoup moins ambitieux, et nous allons seulement limiter à deux cas simples

Contrairement aux précédents, cette partie ne contient pas de résultats théoriques, mais seulement des
exemples illustrant des méthodes générales que vous devez savoir réutiliser pour résoudre des problèmes

a ¿ équations diophantiennes du type a = by

Exemple : déterminer l’ensemble des solutions de l’équation 33 x = 15 y d’inconnue ( x , y ) ∈ Z2

Première étape: calcul le PGCD pour simplifier l’équation avoir une équation avec des coefficients
premiers
¿ pour cela, utilisons comme d’habitude l’algorithme d’Euclide, ainsi on obtient comme résultat :
33 = 15 ×2 + 3
15 = 3 ×5 + 0 le dernier reste non nul que l’on obtient est 3 , donc PGCD(33 , 15) = 3
En simplifiant, par le PGCD , on constate que l’équation 33 x = 15 y d’inconnue (x , y )∈ Z2 est équivalente
à l’équation 11 x = 5 y d’inconnue ( x , y ) ∈ Z2 avec 11 et 5 les deux coefficients qui sont premiers entre eux
Deuxième étape : résolvons maintenant l’équation simplifiée, en procédant par analyse-synthèse
Analyse: soit ( x , y ) ∈ Z2 tel que 11 x = 5 y avec 11 et 5 qui sont premiers entre eux
¿ alors 11∨5 y , donc d’après le lemme de Gauß 11∨ y on en déduit qu’il existe k ∈ Z tel que y = 11k
En remplaçant, dans l’égalité de départ, on obtient alors 11 x = 5 ×(11k ) donc x = 5 k
Cela montre que tout couple est solution de l’équation simplifiée est inclus dans { (5 k ,11k ) , k ∈ Z }
Synthèse: vérifions, tout couple de cette forme est bien solution de l’équation soit k ∈ Z et (x , y ) =
(5 k , 11k )
¿ alors 11 x = 11×(5 k ) = 55 k = 5 ×(11k ) = 5 y on en déduit que (x , y ) est solution de l’équation
simplifiée
Cela montre que tout couple de la forme (5 k , 11k ) avec k ∈ Z est solution de l’équation simplifiée
Autrement dit { (5 k ,11k ) , k ∈ Z } est inclus dans l’ensemble des solutions de l’équation simplifiée
On peut conclure pour cette étape, que l’ensemble des solutions de l’équation simplifiée est
{ (5 k ,11k ) , k ∈ Z }
Troisième étape: concluons quant aux solutions de l’équation de départ, ainsi ce qui nous donne le résultat :
Puisque les équations 33 x = 15 y d’inconnue (x , y )∈ Z2 et 11 x = 5 y d’inconnue (x , y )∈ Z2 sont
équivalentes
On peut donc conclure, que l’ensemble des solutions de l’équation de départ est aussi { (5 k ,11k ) , k ∈ Z }

b ¿ équations diophantiennes du type a + by = c

Exemple : déterminer l’ensemble des solutions de l’équation 33 x + 15 y = 8 d’inconnue ( x , y ) ∈ Z2

Première étape: calculons le PGCD des coefficients 33 et 15

Nous venons de voir dans l’exemple précédent que pour PGCD(33 , 15) on obtient PGCD(33 , 15) = 3
Deuxième étape : concluons par l’absurde
Si l’équation admettait une solution ( x , y ) ∈ Z2 on aurait 3∨33 x et 3∨15 y donc 3∨¿ + 15 y ¿ d’après
les propriétés de la divisibilité, c’est-à-dire 3∨8 ce qui est absurde donc cette équation n’admet pas de
solutions
On peut donc conclure que l’ensemble des solutions de l’équation 33 x + 15 y = 8 d’inconnue (x , y )∈ Z2 est
∅
Exemple : trouver l’ensemble des solutions de l’équation 34 x + 85 y = 136 d’inconnue (x , y )∈ Z2

Première étape: calculons le PGCD des coefficients 34 et 85 pour cela utilisons l’algorithme d’Euclide :
85 = 34 × 2 + 17
34 = 17 ×2 + 0 le dernier reste non nul que l’on obtient est 17 , donc PGCD(34 ,85) = 17
Deuxième étape : cherchons une solution particulière en utilisant un couple de Bézout associé aux
coefficients
¿ en remontant les calculs dans l’algorithme d’Euclide, on trouve 34 ×(−2) + 85 ×1 = 17
¿ en multipliant cette égalité par 8 ,qui est le quotient de la division de 136 par 17 on en déduit qu’on obtient :
34 ×(−2 ×8) + 85 ×(1 ×8) = 17 × 8 c’est-à-dire que 34 ×(−16) + 85 × 8 = 136
On peut donc en conclure que le couple (x 0 , y 0) = (−16 , 8) qui est une solution particulière de l’équation
Troisième étape: déterminons l’ensemble des solutions en procédant par analyse-synthèse :
Analyse: soit (x , y )∈ Z2 une solution de l’équation, on obtient alors comme résultat 34 x + 85 y = 136
De plus, il existe (x ¿ ¿ 0 , y 0) ¿ qui est également une solution de l’équation, ainsi on obtient 34 x 0 + 85 y 0 =
136
¿en rassemblant les deux, on peut écrire 34 x + 85 y = 34 x 0 + 85 y 0 puis 34 (x−x 0) = 85( y ¿¿ 0− y )¿
¿ en divisant par le PGCD on obtient 2(x−x 0 ) = 5( y ¿ ¿ 0− y )¿ avec 2 et 5 qui sont des premiers entre
eux
Comme 2∨5 ( y 0− y ) et 2 et 5 sont premiers entre eux alors 2∨( y 0− y) d’après le lemme de Gauß
¿ il existe donc k ∈ Z tel que y 0− y = 2 k ou encore y = y 0−2k
¿ en remplaçant on obtient 2(x−x 0 ) = 5 ×2 k puis x−x 0 = 5 k on en déduit que x = x 0 + 5 k
On peut donc conclure, que l’ensemble des solutions de l’équation est inclus dans {¿¿ +
5 k , y 0−2 k ¿ , k ∈ Z }
Synthèse : vérifions que tout couple est solution de l’équation soit k ∈ Z et (x , y ) = ¿ ¿ + 5 k , y 0−2 k ¿
¿ alors 34 x + 85 y = 34 × ¿ + 5 k ¿ + 85 ×( y ¿¿ 0−2 k)¿ = 34 x 0 + 34 × 5 k + 85 y 0−85× 2 k = 34 x 0 +
85 y 0
¿ 34 x 0 +85 y 0 = 136 et le couple (x ¿ ¿ 0 , y 0) ¿ est solution de l’équation donc (x , y ) est solution de
l’équation
On peut donc conclure que tout couple de la forme ¿ ¿ + 5 k , y 0−2 k ¿ avec k ∈ Z est solution de l’équation
Finalement, l’ensemble des solutions de l’équation diophantienne 34 x + 85 y = 136 d’inconnue (x , y )∈ Z2
est {¿¿ + 5 k , y 0−2 k ¿ , k ∈ Z } c’est-à-dire en remplaçant (x ¿ ¿ 0 , y 0) ¿ par sa valeur on a {¿ +
5 k , 8−2k ¿ , k ∈ Z }