1/ 39 2017-2018

Université Cheikh Anta Diop de Dakar

Arithmétique
IREMPT
c

LMath
Arithmétique
Farba Faye IREMPT/UCAD

Pré requis :
- Connaitre les différents types de démonstration.
- Dans Z toute partie non vide et minorée a un plus petit élément ; en particulier, dans N qui est
minoré par 0 toute partie non vide a un plus petit élément.
Dans Z toute partie non vide et majorée a un plus grand élément.
Par conséquent dans Z toute partie non vide bornée est finie.
- Axiome d’Archimède : Pour tout entier a et tout entier naturel b > 0, il existe un entier n tel que
a < bn.
Remarquons que l’axiome d’Archimède peut être énoncé dans l’ensemble des nombres réels :
Pour tout réel a et tout réel b > 0, il existe un entier n tel que a < bn.
Dans le cadre plus général des rationnels, cet axiome permet de définir la notion de partie entière.
L’axiome signifie simplement que la suite arithmétique bn a pour limite +∞.
- La descente infinie est un principe introduit et utilisé par Fermat. Selon ce principe, il n’existe pas
de suite strictement décroissante d’entiers positifs.
On utilise ce principe pour prouver qu’il n’existe pas de solution à certains problèmes faisant intervenir
des nombres entiers : si à partir d’une solution, on sait en fabriquer une autre strictement plus petite
mais toujours en nombres entiers, et qu’on peut recommencer indéfiniment, alors le problème initial n’a
pas de solution.
Montrons par exemple en utilisant ce√principe qu’il n’existe pas d’entiers naturels a, b strictement
positifs tels que a2 = 2b2 (autrement dit 2 n’est pas rationnel).
On raisonne par l’absurde en supposant qu’il existe une solution (a, b) à ce problème.
Alors a2 est paire. par conséquent a aussi est pair : Il existe un entier naturel a1 tel que a = 2a1 . La
relation a2 = 2b2 devient 2a21 = b2 .
Partant de cette relation et utilisant le même raisonnement, on en déduit que b aussi est paire : Il
existe un entier naturel b1 tel que b = 2b1 .
La relation 2a21 = b2 devient a21 = 2b21 ; de plus a1 et b1 sont strictement positifs et a1 <a et b1 <b..
Ainsi le couple (a1 , b1 ) est une solution du problème.
On peut alors répéter le processus indéfiniment. On obtient deux suites strictement décroissantes
d’entiers naturels positifs. Par le principe de la descente infinie, cela est impossible.
Remarquer que si l’on avait demandé que en plus a et b soient premiers entre eux, la première étape
aurait suffit pour écrire une contradiction. En effet dans ce cas 2 serait un facteur commun de a et b.
Pré test :
Exercice 1. Quel sont les quotient et reste de la division euclidienne de 7 par −3 ? de −7 par 3 ? de −7
par −3 ?

Réponse. 7 = −3 × (−2) + 1 quotient −2 reste 1.

−7 = 3 × (−3) + 2 quotient −3 reste 2.
−7 = −3 × (3) + 2 quotient 3 reste 2.


Exercice 2.
1. Ndew et Debo se rencontrées au marché lundi. Ndew retourne au marché tous les deux jours. Debo
retourne au marché tous les trois jours. Quel est le jour de leur prochaine rencontre ?
2. Montrer que n5 − n est un multiple de 5.

3. a. Réduire n5 − n en un produit de facteurs irréductibles.

1
Arithmétique 1 /39 2017-2018
LMath Farba Faye IREMPT/UCAD Arithmétique 2

b. En déduire que n5 − n est divisible par 2 et par 3.

4.
5. en déduire que n5 − n par 30
Exercice 3. Résoudre les équation suivantes dans l’ensemble X spécifié.
1. x + y = 1 et X = R × R.
2. x + y = 1 et X = Z × Z.

3. a. x + 3y = 1 et X = R × R.

b. x + 3y = 1 et X = Z × Z.

4. a. 223092870x + 3y = 1 et X = Z × Z.

b. 3 × 9699690x + 3y = 1 et X = Z × Z.

Réponse.
1. {(x, 1 − x), x ∈ R}, points R2 de la droite d’équation x + y = 1.
2. {(x, 1 − x), x ∈ Z}, points R2 à coordonnées entières de la droite d’équation x + y = 1 (l’addition
dans Z est une relation de composition interne,. . .)
3. y étant donné dans Z, 1−3y est aussi un entier ; donc l’ensemble des solutions est {(1−3y, y), y ∈ Z}.

4. a. Sous cette forme cela est difficile. Mais on peut remarque que 223092870 = 3 × 9699690. Le
problème est donc identique à celui de la question suivante.

b. Si (x, y) est une solution, alors 1 = 3 × 9699690x + 3y doit être un multiple de 3, ce qui est faux.
L’équation n’a pas de solution.


Exercice 4. Le nombre 28 s’écrit 26 en base a. Combien vaut a ?

Réponse. 28 = 2a + 6. Donc a = 11.


Première partie

Généralités

3
1 Divisibilité

1.1 Premiers concepts

Cette section, comme son nom l’indique, expose le concept de base de l’arithmétique : la divisibilité.
On introduit ensuite les nombres premiers ce qui permet d’énoncer le théorème fondamental de
l’arithmétique (c’est-à-dire la décomposition en facteurs premiers) dans lequel les nombres premiers jouent
le rôle de briques élémentaires pour la fabrication des nombres.

1.1.1 Divisibilité
Définition 1.

Soit a et b sont deux entiers tels que a soit non nul. On dit que a divise b, ou que b est divisible
par a, s’il existe un entier q telque b = aq. On dit aussi que a est un diviseur de b, ou que b
est un multiple de a. On le note a|b.

Voici quelques propriétés assez immédiates que l’on pourra démontrer à titre d’exercice.

Propriétés 1.

1. a. 0 est divisible par n’importe quel entier.

b. Pour tout entier a non nul, les entiers a, 1, −a et −1 sont des diviseurs de a.

2. a. La relation ”divise” est symétrique : Pour tout entier non nul a, on a a|a.

b. La relation ”divise” est transitive : Si a|b, et b|c, alors a|c.

c.
- Si a divise b et b 6= 0, alors |a| ≤ |b|.
- Si a|b et b|a, alors on a seulement |a| = |b|. La relation ”divise” n’est donc pas antisymétrique ;
mais sa restriction à l’ensemble N des entiers naturels l’est

∀a, b ∈ N, a|b et b|a ⇒ a = b.

Ainsi la relation ”divise” est un ordre sur N. Cet ordre est partiel car par exemple 2 ne divise
pas 3 et 3 ne divise pas 2.
3. Si a divise b et c, alors a divise la somme b + c et pour tout entier n, a divise bn en
particulier a divise le produit bc.

Soit a un entier. L’ensemble {an, n ∈ Z} des multiples de a est noté aZ.

Quant à l’ensemble des diviseurs de a on le notera Div(a)
Exercice 5. Soient m et n des entiers. Montrer que a = 5m + 3n est un multiple de 11 si et seulement
si b = 6m + 8n l’est.
Indication : Calculer a + b.

4
 5

Réponse. c = a + b = 11(m + n) est un multiple de 11.

Donc si a est multiple de 11, alors b = c − a est un multiple de 11 et si b est multiple de 11, alors
a = c − b est un multiple de 11.


1.1.2 pgcd et ppcm

Comme déjà vu dans les propriétés précédentes tout entier a non nul a au moins 2 diviseurs : on peut
citer −1, 1, −a, a. De plus cet ensemble est borné car tout diviseur de a appartient à l’intervalle [−|a|, |a|].
Soit a et b sont des entiers non nuls.
L’ensemble des diviseurs communs de a et b est non vide car il contient 1 ; de plus cet ensemble est
majoré par |a||b|.
L’ensemble des multiples communs strictement positifs de a et b est non vide car il contient |a||b| ; de
plus cet ensemble est minoré par 1.
Ceci motive la définition suivante du pgcd et du ppcm concepts fondamentaux de l’arithmétique.

Définition 2.

Soient a et b deux entiers non tous deux nuls. L’ensemble des diviseurs communs de a et b est
non vide et majoré, il possède donc un plus grand élément appelé plus grand commun diviseur
(pgcd ).
Le pgcd de a et b est noté a ∧ b. Ainsi a ∧ b = max (Div(a) ∩ Div(b))
Lorsque a ∧ b = 1, on dit que a et b sont premiers entre eux .
L’ensemble des multiples communs strictement positifs a et b est non vide et minoré, il possède
donc un plus petit élément appelé plus petit commun multiple (ppcm).
Le ppcm de a et b est noté a ∨ b. Ainsi a ∨ b = min (aN∗ ∩ bN∗ )

Soit a un entier non nul si n est un diviseur de a notons a/n l’unique entier tel que a = na/n . (la
a
notation traditionnelle est .
n
 6

Proposition 1.

1. a. d = a ∧ b, alors un entier n divise a et b si et seulement si il divise d.

Div (a ∧ b) = Div a ∩ Div b.

b. m = a ∨ b, alors un entier n est un multiple de a et b si et seulement si il est un multiple

de m.
(a ∨ b)Z = aZ ∩ bZ
2. Si a et b sont des entiers et n ∈ N∗ , alors

na ∧ nb = n(a ∧ b) et na ∨ nb = n(a ∨ b)

En particulier, si n divise a et b, alors

n(a/n ∧b/n ) = a∧b.

3. a et b sont des entiers distincts et non tous nuls, alors a ∧ b = a ∧ (b − a) dès que le
deuxième membre a un sens.
Plus généralement, si q est un entier quelconque

a ∧ b = a ∧ (b − aq).

Cette égalité est à la base de l’algorithme dit d’Euclide pour déterminer le pgcd de deux entiers.

Exemple 1. Deux entiers consécutifs sont premiers entre eux. En effet si n est un entier, alors par la
proposition 1 item 3,
n ∧ (n + 1) = n ∧ (n + 1 − n) = n ∧ 1 = 1
D’après cette même propriété, a et qa + 1 sont premiers entre eux car

a ∧ (qa + 1) = a ∧ (qa + 1 − qa) = a ∧ 1 = 1

1. Si d est le pgcd de deux entiers a et b, alors les entiers a/d et b/d sont premiers entre eux.
n
Exercice 6. Soit n un entier naturel. Le nième nombre de Fermat est Fn = 22 + 1.

1. a. Démontrer par récurrence que

n
Y
∀n ∈ N, Fn+1 = Fk + 2
k=0

b. En déduire que si m et n sont deux entiers tels que m > n alors il existe un entier q telque
Fm = qFn + 2.
2. Démontrer que deux nombres de Fermat distincts sont premiers entre eux.

Réponse.

1. a. Par récurrence
 7

b. Par récurrence
2. Soit Fm et Fn deux nombres de Fermat avec m > n. Alors il existe un entier q tel que Fm = qFn + 2.
Donc
Fn ∧ Fm = Fn ∧ (Fm − qFn ) d’après la proposition 1 item 3
= Fn ∧ 2 = 1 car Fn est impair

1.2 Nombres premiers

Les nombres premiers sont les atomes (les éléments insécables ) de l’univers des entiers.

1.2.1 Définition et premières propriétés

Comme nous l’avons dit dans l’introduction de cette partie, les nombres premiers sont les briques
élémentaires pour fabriquer les nombres. De façon plus précise et moins imagée, on a la définition suivante :

Définition 3.

Un entier non nul est dit premier s’il a exactement deux diviseurs positifs : 1 et lui-même.
Un nombre qui n’est pas premier est appelé nombre composé.

Les nombres 2, 3, 5, 7, 11 sont premiers. Les nombres 1, 4, 6, 8, 9, 10 ne sont pas premiers.

Exercice 7. Soit p un entier premier telque p > 3. Montrer que p2 − 1 est un multiple de 12.
Indication : Un nombre premier est nécessairement impair.
De trois nombres consécutifs un et un seul est un multiple de 3(?) .

Réponse. Puisque p est premier, il est impair. Il existe donc un entier k telque p = 2k + 1. Alors
p2 − 1 = 4(k 2 + k) est un multiple de 4.
En suivant l’indication, un des entier p − 1, p et p + 1 est multiple de 3. Ce n’est pas p car p est premier
et > 3. Donc p2 − 1 = (p − 1)(p + 1) est multiple de 3.
p2 − 1 multiple de 3 et de 4 entraine p2 − 1 multiple de 12(?) .


Ce n’est pas toujours facile de voir si un nombre est premier ou non.

Les nombres de Fermat F0 , F1 , F2 , F3 et F4 sont premiers.
Fermat pensait que tous les nombres de Fermat étaient premiers. En 1732, Euler prouva que F5 était
divisible par 641.
Soit a un entier naturel distinct de 1. L’ensemble des diviseurs de a strictement supérieurs à 1 est non
vide car il contient a. Cet ensemble contient donc un plus petit élément.
La proposition suivante est utile dans les tests de primalité, dont l’un des plus célèbre est le crible
d’Eratosthène.
Proposition 2.

1. Soit a un un entier naturel non nul. Son plus petit diviseur d > 1 est un nombre premier.
2. Si a est premier, alors d = a.
Si de plus a est composé, alors d2 ≤ a.

Démonstration.
 8

1. Démontrons cela par l’absurde. Si d n’est pas premier, il a un diviseur positif d′ , distinct de 1 et de
d.
Dans ce cas d′ est aussi un diviseur de d et comme il est < d, cela contredit la minimalité de d.
2. Si a est premier, il a deux diviseurs positifs : 1 et a. Le plus petit qui est strictement supérieur à
1 est bien a. Il existe un entier q telque a = dq. Si de plus a est composé, alors d<a = dd′ ; donc q > 1.
Du coup q ≥ d (car d est le plus petit diviseur de a qui est strictement supérieur à 1). On conclut en
multipliant par d que a ≥ d2 .

Remarque 1.

On déduit de la propriété précédente que pour tester si un entier a > 1 √est premier, il suffit de
regarder s’il est divisible ou non par un des entiers compris entre 2 et a. Par exemple, pour
vérifier que 31 est premier, il suffit de voir qu’il n’est divisible ni par 2, ni par 3, ni par 4, ni
par 5.
Comme aucun de ces entiers n’est divisible par 31, et que l’entier suivant 6 a un carré supérieur
à 31, on peut conclure que 31 est premier.
On aurait pu évidemment s’épargner le test de la divisibilité par 4 si on savait par avance que
4 est composé.

Remarque 2.

La proposition nous amène à la méthode, appelée crible d’Eratosthène pour lister tous les
nombres premiers entre 1 et a : on écrit à la suite les uns des autres tous les entiers compris
entre 1 et a.
2 est premier. On le choisit et on barre tous ses multiples.
Le suivant non barré est 3. Il est premier car sinon son plus petit diviseur ne pourrait être que
2. Mais on a barré tous les multiples de 2 ! !
Le suivant non barré est 5. Il est premier car sinon son plus petit diviseur ne pourrait être que
2 ou 3. Mais on a barré tous les multiples de 2 et de 3 ! ! √
Par ce procédé quand on aura atteint le dernier nombre dont le carré est inférieur à a, on
aura terminé : tous les autres nombres non barrés seront premiers.

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
/

1.2.2 L’ensemble des nombres premiers est infini

Proposition 3 (Euclide).

Il existe une infinité de nombres premiers.

Démonstration. Pour tout nombre de Fermat Fn , notons dn le plus petit diviseur premier de Fn . Alors
si m et n sont des entiers distincts, Fn et Fm étant premiers entre eux, dn et dm sont distincts.
On crée ainsi une application injective d : n → dn de N dans l’ensemble P des nombres premiers.
L’ensemble P est donc infini.
 9

Démonstration d’Euclide, par l’absurde. Si l’ensemble P des nombres premiers était fini, l’ensemble de
nombres premiers positifs serait aussi fini. Notons p1 , p2 , . . . , pn ces nombres et posons p = p1 p2 pn + 1.
Alors, p strictement plus grand que chacun des pi , n’est pas premier. p a un plus petit diviseur positif
premier ; ce plus petit diviseur positif est l’un de pi , notons-le pj . Notons q le produit de tous les autres.
Il existe un entier d telque p = pj d. Alors, p = p1 p2 pn + 1 = pj q + 1 = pj d ; donc pj (d − q) = 1. C’est
impossible car pj n’est pas inversible dans Z.
Exercice 8. Un nombre premier est premier avec tout entier qu’il ne divise pas.

Réponse. Soit p un nombre premier, a un entier non multiple de p et notons d leur pgcd. Alors d divise p.
Comme n n’est pas multiple de p, l’entier d est différent de p donc est supérieur strictement à p. Puisque
p est premier, d = 1.(N’oublions pas que p n’a que deux diviseurs positifs : 1 et p.)


Exercice 9. Bien que l’ensemble des nombres premiers soit infini, leur répartition dans N est assez rare.
Plus précisément :
Prouver que pour tout entier naturel n ≥ 1 (aussi grand que l’on veut) l’intervalle
[(n + 1)! + 2, (n + 1)! + n + 1, ], dont la longueur est n, ne contient aucun nombre premier.

Réponse. En effet, un entier appartenant à cet intervalle est de la forme (n + 1)! + k, k étant un entier
compris entre 2 et n + 1.
Or le produit (n+1)! contient le facteur k : il existe q tel que (n+1)! = kq. Donc (n+1)!+k = k(q+1).

2 Division euclidienne et conséquences

2.1 Division euclidienne

Théorème 1 (Division euclidienne).

Soit b un entier non nul. Tout entier a s’écrit de manière unique sous la forme a = bq + r , avec
q et r entiers et 0 ≤ r < |b|.
Les entiers q et r sont appelés respectivement quotient et reste de la division euclidienne de a
par b.

On remarque immédiatement que a est divisible par b si et seulement si r = 0. Comme pour les parties
entières, on prendra garde à ce qui se produit lorsque l’un des nombres a et b est négatif.
Démonstration.
1. Existence. Si a = 0 on peut prendre q = r = 0. Supposons donc a non nul.
Supposons d’abord b > 0 et posons B = {n ∈ Z : bn ≤ a}
Si a > 0 alors B contient tous les entiers négatifs. De plus, d’après l’axiome d’Archimède, il existe un
entier n0 telque a < bn0 . Alors, pour tout élément n ∈ B, on a bn ≤ a < bn0 . Par conséquent n < n0 et
B est majoré.
Si a < 0 alors d’après l’axiome d’Archimède, il existe un entier n1 tel que −a < bn1 c’est à dire
b(−n1 ) < a ; B est donc non vide. De plus, pour tout entier positif m et tout élément n de B on a
bn ≤ a < 0 ≤ bm. Par conséquent n < m et B est majoré.
On voit ainsi que dans tous les cas, B est non vide et majoré. Il a donc un plus grand élément q. Alors
q + 1 n’appartient pas à B, autrement dit, a < b(q + 1).
a
En résumé, bq ≤ a < b(q + 1). (On vient en fait de définir q comme la partie entière de .) Il suffit
b
alors de poser r = a − bq.
Si b < 0, on se ramène au cas précédent avec −b.
2. Unicité. si a s’écrit a = bq + r = bq ′ + r′ , alors b(q − q ′ ) = r′ − r.
La non nullité de |q ′ − q| aurait entrainé |b|>|r′ − r| = |b||q − q ′ | ≥ |b|, une contradiction ! !
Donc q = q ′ puis r = r′ .
Exercice 10. Soit p un entier naturel premier tel que 8p2 + 1 soit premier. Montrer que 8p2 − est aussi
premier. Indication : Discuter suivant les valeurs du reste de la division euclidienne de p par 3.

10
 11

2.2 Conséquences principales

2.2.1 Théorème de Bézout
Théorème 2 (Bezout).

1. Soient a et b des entiers non tous nuls. Notons d le pgcd de a et b : d = a ∧ b. Alors il

existe des entiers u et v tels que :
au + bv = d
2. En particulier, a et b sont premiers entre eux si, et seulement s’il existe des entiers u et
v tels que au + bv = 1.

Démonstration.
1. Posons B = {am + bn où m et n sont entiers non tous nuls} ∩ N∗ . En prenant dans R2 le vecteur
A = (a, b), B est en fait l’ensemble des produits scalaires positifs AX, X étant le vecteur (m, n).
B est non vide car il contient |a| + |b| (faire m = signe(a) et n = signe(b)).
Comme B un sous ensemble de N∗ , il est minoré par 1.
B a donc un plus petit élément δ = au + bv.
Maintenant montrons que δ = a ∧ b.
Posons d = a ∧ b. Comme d divise a et b, il divise aussi au et bv donc au + bv = δ ; alors d ≤ δ.
Soit q et r le quotient et le reste de la division euclidienne de a par δ :

a = δq + r, 0 ≤ r < δ.

Alors r = a − δq = a(1 − uq) + vqr. La non nullité de r entraine alors son appartenance à B ; ce qui est
impossible puisque r < d et d est le plus petit élément de B. Donc r = 0 et a = δq est divisible par δ.
Par un raisonnement analogue, b est un divisible par δ.
Ainsi δ est un diviseur commun de a et b. Donc δ ≤ d.
Finalement δ = d.
2. Si a et b sont premiers entre eux, leur pgcd vaut 1, alors, d’après la première partie, il existe des u
et v tels que au + bv = 1.
Réciproquement, supposons cette propriété réalisée et notons d le pgcd de a et b.
Comme d divise a et b, il divise aussi au et bv donc au + bv qui vaut 1. on conclut que d = 1.

Remarque 3.

Attention ! ! Soit c un entier. La relation au + bv = c n’entraine pas que c est le pgcd de a et

b.
En revanche, on en déduit en notant d le pgcd de a et b : il existe un entier m telque a = dm
et il existe un entier n telque b = dn.
La relation devient alors dmu + dnv = c. c est donc un multiple de d.
Ainsi, l’équation au + bv = c, d’inconnue le couple (u, v) n’a de solution que si c est un multiple
de a ∧ b.
Dans ce cadre, puisque la division euclidienne de b par a s’écrit aussi a(−q) + b.1 = r, le reste
r est nécessairement un multiple du pgcd a ∧ b.

Corollaire 1.

Si un entier est premier avec deux autres, alors il est premier avec leur produit.

a ∧ b1 = 1
⇒ a ∧ b1 b2 = 1
a ∧ b2 = 1
 12

Démonstration. Si a est premier avec b1 et b2 , par Bezout, il existe des entiers u1 , v1 , u2 , v2 tels que

au1 + b1 v1 = 1
au1 + b2 v2 = 1
En faisant le produit membre à membre on obtient au3 + bv3 = 1 avec u3 = au1 u2 + b2 u1 v2 + b1 v1 u2 et
v3 = v1 v2 . On conclut alors par Bezout.
Exercice 11. Montrer que si a et b sont premiers entre eux, toute puissance de a est premier avec toute
puissance de b en particulier pour tout entier n, an et bn sont premiers entre eux.
a ∧ b = 1 ⇒ ∀m, n ∈ N∗ , am ∧ bn = 1

Indication : Utiliser Bezout pour montrer d’abord que am ∧ b = 1.

Réponse. Si a et b sont premiers entre eux, par Bezout, il existe des entiers u et v tels que au + bv = 1
c’est à dire au = 1 − bv. On élève à la puissance m et on utilise la formule du binôme au second membre.
am um = (1 − bv)m .
Une fois développé, ce second membre est la somme de 1 et de termes contenant tous le facteur b : il
existe un entier w tel que (1 − bv)m = 1 − bw. La relation précédente devient am um = 1 − bw ; autrement
dit am um + bw = 1. On conclut encore une fois par Bezout que am et b sont premiers entre eux.
On vient de démontrer que : Si deux entiers sont premiers entre eux chacun des deux est premier avec
toute puissance de l’autre.
Appliquons cela aux deux nombres premiers entre eux am et b avec l’entier n : am est premier avec
n
b .


2.2.2 Lemme de Gauss

Enoncé du lemme

Théorème 3 (Gauss).

Soit a, b et c trois entiers non nuls. Si a divise le produit bc et est premiers avec b alors a divise
c.

a|bc
⇒ a|c
a∧b=1

Démonstration. Puisque a divise bc, il existe un entier q tel que bc = aq.

Par Bezout il existe des entiers u et v tels que au + bv = 1.
Alors en multipliant par c on a acu + bcv = c. Ensuite, on remplace bc par aq pour avoir
c = acu + bcv = acu + aqv = a(cu + qv)
On conclut que a divise c.

Corollaire 2.

Si un entier premier divise un produit a1 a2 . . . an alors p divise au moins l’un des ai .

Remarque 4.

Attention ! ! Il est essentiel de supposer l’entier premier. Par exemple, 8 divise 4 × 6 (en trois
parties) mais il ne divise aucun des facteurs.
 13

Démonstration. Par l’absurde, supposons que p ne divise aucun des ai . Alors p est premier avec chacun
d’eux.
p est premier avec a1 et divise a1 (a2 . . . an ) ; par Gauss p divise a2 . . . an .
p est premier avec a2 et divise a2 (a3 . . . an ) ; par Gauss p divise a3 . . . an .
En itérant on arrive à p divise an−1 an et comme il est premier avec an−1 , il devra diviser an ; une
contradiction.

Résolution de l’équation Diophantienne linéaire au + bv = c

a. Résolution de l’équation homogène au + bv = 0 Quitte à simplifier par d, le pgcd de a et b

on peut supposer a et b premiers entre eux.
L’équation est équivalente à au = −bv.
Alors a divise bv et comme il est premier avec b il doit diviser v, d’après Gauss. Il existe donc un
entier k telque v = ak. L’équation devient au = −bak c’est dire u = −bk.
L’ensemble des solutions de l’équation homogène au + bv = 0 dans Z2 est

{k(−b, a), k ∈ Z}

Remarque 5.

On pouvait s’attendre à ce résultat. En effet, l’ensemble des solutions de l’équation homogène

au + bv = 0 dans R2 est bien la droite vectorielle engendrée par le vecteur (−b, a). Les solutions
dans Z2 sont donc les points de cette droite ayant de coordonnées entières.

b. Résolution de l’équation avec second membre au + bv = c

Soit (u0 , v0 ) une solution de l’équation au + bv = c. Pour toute autre solution (u, v) de cette équation,
on a : 
au0 + bv0 = c
au + bv = c
et en faisant la différence membre à membre, a(u − u0 ) + b(v − v0 ) = 0. Ainsi, le couple (u − u0 , v −
v0 ) est solution de l’équation homogène. Il existe donc k ∈ Z telque u = u0 − kb et v = v0 + ka
(u0 , v0 ) étant une solution particulière de l’équation avec second membre
au + bv = c dans Z2 , l’ensemble des solutions de cette équation est

{(u0 − kb, v0 + ka), k ∈ Z}

Par conséquent, pour résoudre
cette équation, il suffit d’en connaitre une solution particulière. Une solution particulière peut être fournie
par l’algorithme dit d’Euclide.

Corollaire 3.

Soient a et b des entiers non tous nuls.

(a ∨ b) . (a ∧ b) = |a| |b|

Démonstration. Supposons d’abord que a et b soient premiers entre eux c’est à dire a ∧ b = 1.
Soit µ un multiple commun de a et de b. Il existe deux entiers m et n tels que µ = am = bn
Le couple (m, n) est donc solution de l’équation homogène au − bv = 0. Par conséquent, il existe un
entier k tel que m = bk et n = ak ; donc µ = abk est un multiple de ab.
Puisque tout multiple commun de a et b est un multiple de ab donc de |a| |b|, on a a ∨ b = |a| |b|.
Dans le cas général, en notant d le pgcd de a et de b, les entiers a/d et b/d sont premiers entre eux ;
on a donc par ce qui précède a/d ∨ b/d = |a/d | |b/d | soit, en multipliant par d2 : d2 (|a/d ∨ b/d ) = |a| |b|.
Finalement |a| |b| = d[d(a/d ∨ b/d )] = d(da/d ∨ db/d ) = d(a ∨ b)
Exercice 12. Déterminer tous les entiers naturels n tels que 5n−1 + 3n−1 divise 5n + 3n .
 14

Réponse. 5n−1 +3n−1 divise 5n +3n si et seulement s’il existe un entier q tel que 5n +3n = q(5n−1 +3n−1 )
c’est à dire 5n−1 (5 − q) − 3n−1 (q − 3) = 0.
Le couple (5 − q, q − 3) est donc solution de l’équation diophantienne 5n−1 u − 3n−1 v = 0.
comme 3 et 5 sont premiers entre eux, 3n−1 et 5n−1 sont aussi premiers entre eux,
On en déduit qu’il existe un entier k tel que 5 − q = 3n−1 k et q − 3 = 5n−1 k. Soit en faisant la
différence membre à membre (5n−1 + 3n−1 )k = −2. Ainsi, 5n−1 + 3n−1 est un diviseur de 2 qui est ≥ 2.
Donc 5n−1 + 3n−1 = 2 la seule valeur possible est n = 1. L’hypothèse de départ devient 2 divise 8.


Exercice 13. Montrer que pour tout entier n, n3 − n est un multiple de 6.

Réponse. n3 − n = (n − 1)n(n + 1) est un multiple de 2 car il contient deux facteurs entiers consécutifs
c’est aussi un multiple de 3 car il contient trois facteurs entiers consécutifs. Il existe donc deux entiers p
et q tels que n3 − n = 2p = 3q ; donc 2p − 3q = 0.
Le couple (p, q) est donc solution de l’équation diophantienne 2u − 3v = 0.
comme 2 et 3 sont premiers entre eux, on en déduit qu’il existe un entier k tel que p = 3k et q = 2k.
Alors n3 − n = 2p = 6k est bien un multiple de 6.


Exercice 14. Montrer que pour tout entier n, 14n + 3 et 21n + 4 sont premiers entre eux.

Réponse. Il suffit de trouver deux entiers u et v tels que (14n + 3)u + (21n + 4)v = 1 c’est à dire
(14u + 21v)n + (3u + 4v) =  1.
2u + 3v = 0
Pour cela il suffit que . La seule solution de ce système linéaire à deux inconnues
3u + 4v = 1
est u == 3 et v = −2. Une fois ce résultat trouvé, il devient évident que 3(14n + 3) − 2(21n + 4)v = 1.


2.2.3 Algorithmes
Algorithme de calcul du pgcd
Comme déjà dit, l’algorithme d’Euclide de calcul du pgcd repose sur la relation suivante :
a ∧ (aq + r) = a ∧ r valable pour a et r entiers non tous nuls.
Soit a et b deux entiers strictement positifs. Pour avoir une formule générale posons b = r0 et a = r1 .
Par division euclidienne de b par a, il existe des entiers r2 et q2 tels que b = aq2 + r2 et 0 ≤ r2 < a
La relation devient r0 = r1 q2 + r2 et 0 ≤ r2 < r1 et alors a ∧ b = r0 ∧ r1 = r1 ∧ r2 .
On en déduit, si r2 est non nul et par division euclidienne de r1 par r2 qu’il existe deux entiers q3 et
r3 tels r1 = r2 q3 + r3 , 0 ≤ r3 < r2 et alors r1 ∧ r2 = r2 ∧ r3 .
Si r3 est non nul, on peut reprendre le processus.
On poursuit... Si aucun reste n’est nul, on obtient une suite strictement décroissante de restes ri > 0
tels que a ∧ b = r0 ∧ r1 = · · · = ri ∧ ri+1 . . . . Par le principe de la descente infinie, cela est impossible.
On aboutit donc nécessairement au bout d’un nombre fini d’étapes à un reste rn nul.
a ∧ b = r0 ∧ r1 = · · · = ri ∧ ri+1 = · · · = rn−2 ∧ rn−1 = rn−1 ∧ 0 = rn−1 .
Avec r0 = b, r1 = a et ri = ri+1 qi+2 + ri+2 , 0 ≤ ri+2 < ri+1
Alors
Soit par exemple à déterminer le pgcd de 6525 et de 2353.

6525 = 2353 × 2 + 1819 6525 ∧ 2353 = 2353 ∧ 1819

2353 = 1819 × 1 + 534 2353 ∧ 1819 = 1819 ∧ 534
1819 = 534 × 3 + 217 1819 ∧ 534 = 534 ∧ 217
534 = 217 × 2 + 100 534 ∧ 217 = 217 ∧ 100
100 = 17 × 5 + 15 217 ∧ 100 = 100 ∧ 15
17 = 15 × 1 + 2 100 ∧ 15 = 15 ∧ 2
15 = 2×7+1 15 ∧ 2 = 2 ∧ 1
2 = 1×2+0 2∧1=1∧0=1
 15

Algorithme étendu ( de détermination d’une solution de l’équation diophantienne)

Voir le fichier index.html

2.3 Décompositions
2.3.1 Décomposition d’un nombre premier
Théorème 4.

Tout entier > 1 se décompose d’une manière unique (à l’ordre des facteurs près) en un produit
de nombres premiers.
Autrement dit, pour tout n ∈ N et a > 1, il existe des entiers premiers et deux à deux distincts
p1 , p2 . . . , pk et des entiers strictement positifs α1 , α2 . . . , αk tels que a = pα1 α2 αk
1 p2 . . . . .pk

Démonstration.
1. Existence : Par récurrence forte, démontrons la propriété ∀ ∈ N, n ≥ 2 ⇒ Pn : n se décompose en
un produit de nombres premiers.
P2 est vrai car 2 est premier.
Soit n ≥ 3 un entier. Supposons Pk vraie pour tout entier strictement inférieur à n et montrons que
Pn est vraie.
Distinguons deux cas.
- Si n est premier, il s’écrit bien comme un produit de nombres premiers.
- Si n n’est pas premier, il a deux facteurs propres a et b, c’est à dire des entiers distincts de 1 et de n
tels que n = ab. Chacun des entiers a et b est ≤ n − 1 ; Pa et Pb sont donc vraies : Chacun de ces entiers
est un produit fini d’entiers premiers deux à deux distincts. Donc leur produit n est bien un produit fini
d’entiers premiers deux à deux distincts.
Unicité : Remarquons d’abord que deux entiers naturels distincts et premiers sont premiers entre eux.
Rappelons ensuite, corollaire 2, que si un entier premier divise un produit, il divise l’un des facteurs .
β1 β2 βl
Supposons que a s’écrit a = pα 1 α2 αk
1 p2 . . . . .pk = q1 q2 . . . . .ql .
β1 β2 βl
Alors p1 est premier et divise le produit q1 q2 . . . . .ql . p1 doit alors diviser l’un des facteurs q1 , q2 , . . . , ql .
p1 est donc égal à l’un de ces facteurs. Par le même raisonnement, chaque pi est égal à l’un des qj .
Par le même raisonnement, chaque qi est égal à l’un des pj .
Donc les pi et le qj sont égaux et k = l.
αk β1 β2 βk
Ainsi on a a = pα 1 α2
1 p2 . . . . .pk = p1 p2 . . . . .pk .
Je dis que α1 = β1 .
En effet, si par exemple α1 > β1 , on pourra écrire pα 1
1 −β1 α2
p2 . . . . .pα β2 βk
k = p2 . . . . .pk . Alors p1 qui est
k

β2 βk
premier divise le produit p2 . . . . .pk sans diviser aucun des facteurs p2 , . . . , pk . Cela contredit le corollaire
2.
Par un raisonnement analogue αi = βi pour tout i.
Voici une conséquence immédiate de ce théorème, donnant tous les diviseurs d’un entiers, connaissant sa
décomposition en produits de facteurs premiers.

Proposition 4.

Si la décomposition en facteurs premiers d’un entier a ≥ 2 est a = pα 1 α2 αk

1 p2 . . . . .pk , alors les
γ1 γ2 γk
diviseurs positifs de a sont les entiers de la forme p1 p2 . . . . .pk avec pour chaque i, γi est un
entier vérifiant 0 ≤ γi ≤ αi .
Le nombre total de diviseurs positifs de a est donc (α1 + 1)(α2 + 1). . . . .(αk + 1)
 16

Corollaire 4.

Si la décomposition en facteurs premiers de deux entiers a et b ≥ 2 est

αk αk
a = pα1 α2 α1 α2
1 p2 . . . . .pk et b = p1 p2 . . . . .pk

alors
min(α ,β ) min(α ,β )
1 1 2 2 min(α ,β )
k k
a∧b = p1 p2 . . . . .pk
max(α1 ,β1 ) max(α2 ,β2 ) max(αk ,βk )
a∨b = p1 p2 . . . . .pk

En général a et b n’ont pas les mêmes facteurs premiers dans leur décomposition. Si c’est le cas on reporte
dans a les facteurs premiers de b absent dans la décomposition de a en leur affectant la puissance 0 et on
reporte dans b les facteurs premiers de a absents dans la décomposition de b en leur affectant la puissance
0.
Par exemple si a = 23 .34 .5 et b = 31 .52 .72 , on écrira

a = 23 .34 .51 .70 et b = 20 .31 .52 .72

et donc
a ∧ b = 20 .31 .51 .70 et a ∨ b = 23 .34 .52 .72
Avec le corollaire précédent, on retrouve un résultat déjà démontré : ab = (a ∧ b).(a ∨ b). Il suffit de
se rappeler que si α et β sont des nombres quelconques, alors α + β = min(α, β) + max(α, β)
Exercice 15 (proposé par El Hadji Dame Seye). Soit a et b des entiers. Démontrer que prour tout entier
naturel non nul m, am divise bm si et seulement si a divise b.

Réponse. Si a divise b ; im existe un entier q tel que b = aq. Alors bm = am q m . donc am divise bm (en
q m parties).
Réciproquement, supposons que am divise bm . On peut supposer a et b positifs.
Il existe des entiers naturels premiers p1 , . . . , pn et des entiers naturels α1 , . . . , αn et β1 , . . . , βn (certains
β1
d’entre eux pouvant être nuls) tels que a = pα αn
1 + · · · + pn et b = p1 + · · · + pn .
1 βn
m mα1 mαn mβ1
Donc a = p1 + · · · + pn m
et b = p1 + · · · + pn . Puisque a divise bm , pour chaque indice
mβn m

i, mαi ≤ mβi c’est à dire αi ≤ βi . Donc a divise b.



2.3.2 Décomposition d’un entier dans une base

Le entiers que nous avons l’habitude de manipuler sont en fait écrit en base 10.
Ainsi 123 = 1.102 + 2.101 + 3.100 et 1002 = 1.103 + 0.102 + 0.101 + 2100 .
Dans cette section, on souhaite montrer qu’un entier naturel donné peut être décomposé dans n’im-
porte quelle base b ≥ 2.

Théorème 5.

Soit b un entier ≥ 2. Tout entier strictement positif a s’écrit de façon unique sous la forme :
a = ak b k + · · · + a2 b 2 + a1 b + a0
où k est un entier, les ai sont des entiers compris entre 0 et b − 1 et où ak 6= 0.

On note parfois a = ak ak−1 ...a0 b . Cette notation est l’écriture de a en base b.

Si b = 10, les ai correspondent aux chiffres usuels de a.

Si a = 16 les chiffres sont 0, 1, . . . , 9, A, B, C, D, E, F.
 17

Démonstration. Existence : Elle consiste à effectuer des divisions euclidiennes successives par b.
a = bq0 + a0 , 0 ≤ a0 ≤ b − 1.
a s’écrit Alors 0 ≤ q0 <a. Si q0 = 0, alors a = a0 et c’est fini.
Si q0 6= 0, q0 s’écrit q0 = bq1 + a1 , 0 ≤ a1 ≤ b − 1. Alors 0 ≤ q1 <q0 . a = b2 q1 + ba1 + a0 . Si q1 = 0 alors
a = ba1 + a0 et c’est fini.
Si q1 6= 0, on continue, construisant q2 , a2 , q3 , a3 .
Supposons avoir construit les q0 > · · · > qi et les 0 ≤ a0 , a1 , . . . , ai ≤ b − 1 tels que
a = qi bi + ai bi + · · · + a1 b + a0 .
Si qi = 0, a = ai bi + · · · + a1 b + a0 c’est fini.
qi = bqi+1 + ai+1 , 0 ≤ ai+1 ≤ b − 1.
Si qi 6= 0, qi s’écrit
Le processus va s’arrêter en un rang donné k, car la suite (qi ) est positive et strictement décroissante
et alors on obtient la décomposition attendue.
Unicité : Si a s’écrit a = ak bk + · · · + a2 b2 + a1 b + a0 = a′l bl + · · · + a′2 b2 + a′1 b + a′0 . Alors |a0 − a′0 |
qui est < b est un multiple de b. Ce qui nécessite a0 = a′0 .
Alors ak bk + · · · + a2 b2 + a1 b = a′l bl + · · · + a′2 b2 + a′1 b.
On simplifie par b et on reprend le même raisonnement pour montrer que a1 = a′1 . On continue le
processus.
Exemple 2. Comment s’écrit 48 en base 5?
48 5
3 9 5
4 1 5
1 0
5
L’écriture de 48 en base 5 est 143 .

2.4 Exercices
Exercice 16. Le nombre 29 dans le système décimal s’écrit 27 en base a. Combien vaut a ?

Réponse. 29 = 2a1 + 7a0 Donc a = 11.



5 5
Exercice 17. Réponse. Calculer 34124 + 2222

 Deuxième partie

Arithmétique modulaire

18
 19

L’arithmétique modulaire ou des congruences est un outil très puissant pour traiter de manière simple
des problème d’arithmétique assez complexes.
3 Congruence modulo n

3.1 Congruence modulo n

Définition 4.

Soit n un entier naturel non nul.

Un entier a est congru modulo n à un entier b si et seulement si a − b est un multiple de n. on
écrit a ≡ b[n].
a ≡ b[n] ⇔ a − b ∈ nZ
⇔ ∃q ∈ Z : a − b = nq

La relation ”congru modulo n” vérifie les propriété suivantes :

Proposition 5 (Propriétés immédiates).

∀a ∈ Z, a ≡ a[n].
1. a. Tout entier est congru modulo n à lui-même :
On dit que la ”congru modulo n” est réflexive.

b. Si a est congru modulo n à b, alors b est congru modulo n à a :

∀a, b ∈ Z, a ≡ b[n] ⇒ b ≡ a[n].

On dit que la ”congru modulo n” est symétrique.

c. Si a est congru modulo n à b et b est congru modulo n à c alors a est congru modulo n à

a ≡ b[n]
∀a, b, c ∈ Z, ⇒ a ≡ c[n].
b ≡ c[n]
c:
On dit que la ”congru modulo n” est transitive.
On résume ces trois propriétés en disant que la relation ”congru modulo n” est une relation
d’équivalence

a + a′ ≡ b + b′ [n]
 
a ≡ b[n]
Si alors
a′ ≡ b′ [n] aa′ ≡ bb′ [n]
2. On résume cette propriété en disant que
la relation ”congru modulo n” respecte (ou est compatible avec) l’addition et la multiplication.

Soit a un entier. Un entier b est congru modulo n à a si et seulement s’il existe un entier q tel que
b − a = nq c’est à dire b = nq + a.
L’ensemble des entiers congrus modulo n à a est donc {a + qn, q ∈ Z} ; il est souvent noté ȧ ou a + nZ
et appelé classe de a modulo n et l’ensemble des classes modulo n est noté Z/nZ
La classe de 0 modulo n est {qn, q ∈ Z} ; c’est l’ensemble des multiples de n.

20
 21

L’item 2 de compatibilité de la relation de congruence avec lois + et . dans Z permet de définir une ad-
· ·
∀a, b ∈ Z, a + b= ȧ + ḃ et a.b= ȧ.ḃ
dition (notée encore +)et un multiplication (notée encore .) par : .
Ces deux lois sont commutatives, associatives. 0̇ est l’élément neutre de l’addition, 1̇ est l’élément
neutre de la multiplication.
Enfin, la multiplication est distributive par rapport à l’addition : ȧ.(ḃ + ċ) = ȧ.ḃ + ȧ.ċ.
Exercice 18. Soit n1 et n2 des entiers naturels non nuls. Démontrer que

a ≡ b[n1 ]
Si alors a ≡ b[n1 ∨ n2 ]
a ≡ b[n2 ]

Réponse. L’hypothèse se traduit par a−b est un multiple commun de n1 et de n2 . Donc c’est un multiple
de leur ppcm.


3.2 Système complet de résidus modulo n

.
Soit n entier naturel non nul.
Pour tout tout entier a, il existe par division euclidienne, un couple d’entiers (q, r) tel que a = nq + r
et 0 ≤ r < n. Comme r = a − nq, l’entier r appartient à la classe de a.
Si r′ est un représentant de la classe de a vérifiant la condition 0 ≤ r′ < n alors il existe un entier q ′
tel que r′ = a + nq ′ . Par conséquent |r′ − r| = n|q + q ′ | est un multiple de n ; comme il est plus petit que
n, il est nécessairement nul. Donc r = r′ .
Ainsi r, reste de la division euclidienne de a par n est l’unique élément de la classe de a vérifiant la
condition 0 ≤ r < n.

Définition 5.

Soit n un entier naturel non nul. L’ensemble {0, 1, . . . , n − 1} est appelé un système complet de
résidus modulo n. Un élément de cet ensemble est appelé un résidu modulo n.
Plus généralement un système complet de résidus modulo n est une partie R de Z tel que deux
éléments de R qui sont distincts sont non congrus et tout entier contient un et un seul élément
de R dans sa classe.

Toute partie de Z constitué de n entiers consécutifs est un système complet de résidus modulo n.
Souvent, lorsqu’on à résoudre une équation faisant intervenir des congruences dont le modulo est un
entier n connu, il suffit d’étudier cette équation dans un système de résidus modulo n.
Exercice 19. Déterminer tous les entiers a tels que a2 + a + 1 est multiple de 3.

Réponse. L’hypothèse se traduit par a2 + a + 1 ≡ 0[3]

Soit a un solution. Pour tout entier b dans la classe de a (c’est à dire b ≡ a[3]), on a d’après la
proposition 5 item 2 b2 + b + 1 ≡ a2 + a + 1[3]. b est alors une solution. On peut donc chercher les solutions
appartenant au système complet de résidus {0, 1, 2}.
Si a = 0, a2 + a + 1 = 1 ≡ / 0[3]. 0 n’est pas solution.
Si a = 1, a2 + a + 1 = 3 ≡ 0[3]. 1 est solution.
Si a = 2, a2 + a + 1 = 7 ≡ / 0[3]. 2 n’est pas solution.
L’ensemble des solution est 1 et tous les entiers qui lui sont congrus = {1 + 3q, q ∈ Z}.
Si on vouait utiliser la notion de classe, on dirait simplement que l’hypothèse signifie : ȧ2 + ȧ + 1 = 0.
La seule classe qu convient est 1̇ = {1 + 3q, q ∈ Z}.

 22

3.3 Bezout et Gauss modulaires

. Le théorème suivant est la version modulaire du théorème de Bezout.
Théorème 6.

Soit a un entier naturel > 1. Un entier b est premier avec a si et seulement si il existe un entier
u tel que au ≡ 1[b]. L’entier u est appelé un inverse de a modulo n.

Démonstration.
b premier avec a ⇔ a ∧ b = 1
⇔ ∃u, v ∈ Z : au + bv = 1 d’après Bezout
⇔ ∃u ∈ Z : au ≡ 1[b]

Exercice 20.
1. Déterminer tous les inverses de 2 modulo 8.
2. Déterminer tous les inverses de 3 modulo 8.

Réponse.
1. u est un inverse de 2 modulo 8 signifie 2u ≡ 1[8] ⇔ ∃v ∈ Z : 2u + 8v = 1 ce qui est impossible
puisque 2u + 8v est pair. On pouvait s’attendre à ce résultat puisque 2 et 8 ne sont pas premiers entre
eux.
2. u est un inverse de 3 modulo 8 signifie 3u ≡ 1[8] ⇔ ∃v ∈ Z : 3u + 8v = 1. C’est une équation
diophantienne linéaire. Le couple (3, −1) est une solution de cette équation.
L’ensemble des solutions est donc {(8k + 3, −3k − 1), k ∈ Z}.
Par conséquent l’ensemble des inverse de 3 modulo 8 est {8k + 3, k ∈ Z}. Ainsi par exemple 3 est un
inverse de 3 modulo 8 : 3.3 ≡ 1[8].
Noter bien que les inverses de 3 modulo 8 constitue une classe : la classe de 11 par exemple. On peut
en fait étudier cette équation dans le système complet de congruences modulo 8 ou dans Z/8Z. Pour cela
il suffit il suffit de dresser la table de multiplication de Z/8Z.
Post quantum RSA
Francois Arnault cours de DEA crypto
Voici par exemple la table de multiplication de Z/9Z \ {0̇, 1̇}

× 2̇ 3̇ 4̇ 5̇ 6̇ 7̇ 8̇
2̇ 4̇ 6̇ 8̇ 1̇ 3̇ 5̇ 7
3̇ 6̇ 0̇ 3̇ 6̇ 0̇ 3̇ 6̇
4̇ 8̇ 3̇ 7̇ 2̇ 6̇ 1̇ 5̇
5̇ 1̇ 6̇ 2̇ 7̇ 3̇ 8̇ 4̇
6̇ 3̇ 0̇ 6̇ 3̇ 0̇ 6̇ 3̇
7̇ 5̇ 3̇ 1̇ 8̇ 6̇ 4̇ 2̇
8̇ 7̇ 6̇ 5̇ 4̇ 3̇ 2̇ 1̇

On y voit nettement que 3 et 6 ne sont pas inversibles, les inverses de 2̇, 4̇, 5̇, 7̇, 8̇ sont respectivement
5̇, 7̇, 2̇, 4̇, 8̇.
Évidemment pour les ”gros” nombres, il n’est pas question d’utiliser cette méthode.


Exercice 21. Démontrer que si p est un entier premier, tout entier non multiple de p admet des inverses
modulo p.
Voici une traduction du lemme de Gauss en termes de congruences :
 23

Théorème 7 (Simplification).

Soit n un entier naturel supérieur strictement à 1 et a, b et c des entiers.


ac ≡ bc[n]
Si alors a ≡ b[n]
c∧n=1


ȧċ = ḃċ
Si alors ȧ = ḃ
c∧n=1
Dans Z/nZ, le lemme se traduit par On dit que ċ est un
élément régulier de Z/nZ. Il existe des éléments non réguliers. Par exemple, dans Z/9Z, 3̇.1̇ = 3̇.7̇ mais
1̇ 6= 7̇
Démonstration. ac ≡ bc[n] ⇔ ac − bc ≡ 0[n] ⇔ ∃q ∈ Z : c(a − b) = nq.
Puisque n divise c(a − b) et est premier avec c, d’après le lemme de Gauss, il doit diviser a − b. Il
existe donc un entier q ′ tel que a − b = nq ′ autrement dit a ≡ b[n]
Exercice 22. Soit p un entier naturel non nul. Montrer que p est premier si et seulement si tout élément
(classe ) non nul de Z/pZ est inversible.

Réponse. Si p est non premier, il a deux diviseurs propres 1 < a ≤ b < p. La relation ab = p entraine
ȧ.ḃ = 0̇. Alors ȧ et ḃ sont tous les deux distincts de 0̇.
Je dis que a est non inversible.
En effet si a était inversible, il existerait c ∈ Z tel que ȧ.ċ = 1̇. On pourrait alors écrire en multipliant
la relation ȧ.ḃ = 0̇ par ċ :

ḃ = 1̇.ḃ = (ȧ.ċ)ḃ = ċ.(ȧḃ) = ċ.0̇ = 0̇, une contradiction

Réciproquement : Supposons p premier. Soit a tel que ȧ 6= 0̇ c’est à dire a non multiple de p. Alors p
et a sont premiers entre eux. D’après le théorème 6 (version modulaire de Bezout), a admet un inverse.

Corollaire 5 (Petit théorème de Fermat).

ap−1 ≡ 1[p]
Si p est un nombre premier et a est un entier quelconque, alors autrement dit,
ap−1 − 1 est divisible par p.

Démonstration. La relation est vraie si ȧ = 0 c’est à dire si a est multiple de p.

Supposons donc ȧ 6= 0̇. Alors a est premier avec p . Posons E = Z/pZ \ {0̇}. C’est un ensemble fini
ayant p − 1 éléments.
f: E→ E
L’application est alors injective. En effet, pour tout ẋ, ẏ ∈ E,
ẋ → ȧẋ

f (ẋ) = f (ẏ) ⇒ ȧẋ = ȧẏ

⇒ ẋ = ẏ d’après le théorème 7 de simplication
Y Y Y
Puisque E est fini, f est bijective. Par conséquent, ẋ = ȧẋ = ȧp−1 ẋ. Une dernière application
ẋ∈E ẋ∈E ẋ∈E
p−1
du théorème 7 permet de simplifier et d’obtenir 1̇ = ȧ .
 24

Remarque 6.

1. Souvent, le théorème est décliné de la manière suivante que l’on obtient en multipliant
la congruence par a :
Si p est un nombre premier et a est un entier quelconque, alors ap ≡ a[p].
2. En théorie des groupes, cela signifie que tout élément du groupe monogène (E, .) est
d’ordre p − 1.
En fait on montre que Z/nZ est un corps si et seulement si n est nombre premier.

Exercice 23.
1. Soit p un nombre premier. Montrer que pour tout entier naturel n, 5n+p − 5n+1 est divisible par p.

2. a. En utilisant les congruences montrer que, pour tout entier naturel n, 36n − 1 est divisible par 7.

b. Retrouver ce résultat à l’aide du petit théorème de Fermat.

3. Montrer que, pour tout entier naturel a non nul, a13 −a est divisible par 26. Indication : Décomposer
26 en produit de facteurs premiers et appliquer la remarque à chacun de ces facteurs.
4 Conséquences

4.1 Critères de divisibilité

Théorème 8.

Soit b > 2 un entier et d un diviseur de b. Alors un entier est divisible par d si, et seulement si
le dernier chiffre de son écriture en base b est lui-même divisible par d.

Théorème 9.

Soit b > 2 un entier et d un diviseur de b − 1. Alors un entier est divisible par d si, et seulement
si la somme des chiffres de son écriture en base b est elle-même divisible par d.

Remarque 7.

- Un entier est divisible par 4 si, et seulement si le nombre formé par ses deux derniers chiffres
(en base 10) l’est.
- Un entier est divisible par 11 si, et seulement si la somme des ses chiffres (en base 10) de rang
pair diminuée de la somme de ses chiffres de rang impair est divisible par 11.

4.2 Théorème chinois

Le nombre de soldats du général Han Xin est compris entre 10 000 et 10 200. Il sait que s’il range les
soldats par 3 il en reste 2. S’il les range par 5, il en reste 3 et s’il les range par 7, il en reste 2. De combien
de soldats dispose le général Han Xi ?.

Théorème 10 (Théorème chinois).

Soit n1 , . . . , nk des entiers naturels non nuls deux à deux premiers entre eux et r1 , . . . , rk des
entiers quelconques. Il existe un entier unique modulo n = n1 . . . nk telque

 x ≡ r1 [n1 ]
.........
x ≡ rk [nk ]


Démonstration.
 avec n = 3 pour fixer les idées. Unicité : Si x et y sont des solutions du système, alors
 x − y ≡ 0[n1 ]
x − y ≡ 0[n2 ] Ainsi, x − y est un multiple commun de n1 , n2 et n3 , donc un multiple de leur ppcm
x − y ≡ 0[n3 ]

qui n’est rein d’ autre que N (puisque les trois nombres, n1 , n2 et n3 sont premiers entre eux deux à
deux). Donc x ≡ y[n]. Existence : Pour tout indice i posons Ni = n/ni (c’est le produit de tous les nj
sauf ni .) Puisque Ni et ni son premiers entre eux, l’entier Ni a un inverse xi modulo ni : xi Ni ≡ 1[ni ].

25
 26


 r1 x1 N1 ≡ r1 [n1 ]
Alors on a r2 x2 N2 ≡ 0[n1 ] car N2 contient le facteur n1
r3 x3 N3 ≡ 0[n1 ] car N3 contient le facteur n1

En posant x = r1 x1 N1 + r2 x2 N2 + r3 x3 N3 et en faisant la somme membre à membre, on voit que
x ≡ r1 [n1 ]. Même raisonnement pour établir les deux autres relations.

 x ≡ 2[3]
Notons x le nombre de soldats du général. On doit avoir : x ≡ 3[5] Ici n1 = 3, n2 = 5 et n3 = 7 ;
x ≡ 2[7]

donc N1 = 5 × 7 = 35, N2 = 3 × 7 = 21 et N3 = 3 × 5 = 15 ; Par l’algorithme étendu de Bezout, x1 = −1
est un inverse de 35 modulo 3, x2 = 1 est un inverse de 21 modulo 5, x3 = −1 est un inverse de 35 modulo
3 et 1 est un inverse de 15 modulo 7. On peut donc prendre comme solution

x = r1 x1 N1 + r2 x2 N2 + r3 x3 N3 = 2 × (−1) × 35 + 3 × 1 × 21 + 2 × 1 × 15 = 23

ou tout entier y congru à 23 modulo n1 n2 n3 = 105. Un tel entier s’écrit y = 23 + 105k, k ∈ Z. On doit
donc avoir 10000 ≤ 23 + 105k ≤ 10200. On trouve k = 95 et y = 10103.
5 Exercices Bac

Exercice 1 (Bac 2009, remplacement). On rappelle la propriété connue sous le nom de petit théorème
de Fermat :
”Si p est un nombre premier et a un entier naturel premier avec p, alors ap−1 − 1 est divisible par p.”
1. Prouver à l’aide du petit théorème de Fermat, que 428 − 1 est divisible par 29.
2. Soient a et n deux entiers naturels non nuls.
Démontrer que
(a + 1)n ≡ 1n [a].
En déduire que 4n ≡ 1 [3].
3. Soient a et n deux entiers naturels non nuls.
Démontrer que
(a − 1)2n ≡ (−1)2n [a].
En déduire que 44n ≡ 1 [17] et 42n ≡ 1 [5].
4. A l’aide des questions précédentes, déterminer 4 diviseurs premiers de 428 − 1.

Réponse. 1
1. En appliquant le petit théorème de Fermat avec p = 29 qui est premier et a = 4, on peut écrire :
429−1 − 1 est divisible par 29.
✑ Soient a, b, c, d, p et n des entiers naturels avec p et n non nuls. Alors on a modulo p :
a ≡ c a ≡ c
⇒ a+b ≡ c+d; ⇒ ab ≡ cd ; a ≡ c ⇒ an ≡ cn
b ≡ d b ≡ d
Autrement dit, on peut additionner membre à membre des congruences, les multiplier ou les élever à
une puissance donnée.
2. On peut donc écrire d’après ce préliminaire et pour tous entiers a et n non nuls :

a ≡ 0 [a]
⇒ a + 1 ≡ 1 [a] ⇒ (a + 1)n ≡ 1n [a]
1 ≡ 1 [a]

4n ≡ 1 [3] en prenant a = 3.
On obtient alors la relation demandée
3. On a aussi, toujours d’après ce préliminaire et pour tous entiers a et n non nuls :

a ≡ 0 [a]
⇒ a − 1 ≡ −1 [a] ⇒ (a − 1)2n ≡ (−1)2n [a]
−1 ≡ −1 [a]

a = 17 que 162n ≡ 1 [17]

On en déduit en prenant c’est à dire 44n ≡ 1 [17]
2n
a = 5 que 4 ≡ 1 [5].
Et en prenant
  
1. Si p est premier, Z/pZ \ 0 ; . est un groupe d’ordre p − 1 et d’élément neutre 1̇. Alors ∀a ∈ Z et premier avec p
(donc non multiple de p ou ȧ 6= 0̇ ), ȧp−1 = 1̇ c’est à dire ap−1 ≡ 1 [p]

27
 28

4. On déduit de 4n ≡ 1 [3] en prenant n = 28 que 428 ≡ 1 [3] c’est à dire 428 − 1 est divisible 3.
On déduit de 44n ≡ 1 [17] en prenant n = 7 que 428 ≡ 1 [17] c’est à dire 428 − 1 est divisible 17.
On déduit de 42n ≡ 1 [5] en prenant n = 14 que 428 ≡ 1 [5] c’est à dire 428 − 1 est divisible 5.
428 − 1 est divisible par chacun des quatre nombres premiers 3, 5, 17 et 29.
En résumé


Exercice 2 (Bac 2010).

On rappelle la propriété connue sous le nom de petit théorème de Fermat : ”Si p est un nombre
premier et a un entier naturel premier avec p, alors ap−1 ≡ 1[p].”

1. a. Démontrer que 193 est un nombre premier. 0,75 pt

b. Soit a un entier naturel inférieur à 192. Montrer que a192 ≡ 1[193]. 0,5 pt
2. On considère l’équation

(E) : 83x − 192y = 1 où x et y sont des entiers relatifs.

a. Vérifier que le couple (155, 67) est solution de (E). 0,5 pt

b. Résoudre l’équation (E). 0,75 pt

3. On note A l’ensemble des 193 entiers naturels inférieurs ou égaux à 192 et on considère les deux
fonctions f et g définies de la manière suivante :
à tout entier a de A, f associe le reste de la division euclidienne de a83 par 193;
à tout entier a de A, g associe le reste de la division euclidienne de a155 par 193.

a. Démontrer g(f (a)) ≡ a83×155 [193]. En déduire que pour tout a ∈ A on a : g f (a) = a.

0,5 pt +0,5 pt

b. Déterminer f ◦ g. 0,5 pt

Réponse.

1. a. Pour que 193 soit premier, il faut et il suffit qu’il soit non divisible par tout nombre premier
dont le carré est inférieur à 193. Ces nombres sont 2, 3, 5, 7, 11, 13 et aucun d’eux ne divise 193.

b. 193 étant premier, est premier avec tout entier naturel strictement plus petit, en particulier, il est
premier avec 192.
Il suffit d’appliquer le petit théorème de Fermat avec a = 193 et p = 192.

2. a. Le couple (x0 , y0 ) = (155, 67) est solution de (E) parce que 83.155 − 192.67 = 1.

b. Si (x, y) est une solution de (E) on peut écrire :


83.x0 − 192.y0 = 1
83.x − 192.y = 1

Puis en faisant la différence

83.(x − x0 ) − 192.(y − y0 ) = 0
c’est à dire
83.(x − x0 ) = 192.(y − y0 )
Or 83 est premier avec 192 parce que l’équation (E) a une solution (théorème de Bezout ).
 29

La relation précédente montre que 83 divise le produit 192.(y − y0 ) (en x − x0 parties) ; comme il est
premier avec 192, il divise y − y0 (théorème de Gauss).
Donc il existe un entier k tel que y − y0 = 83k soit y = y0 + 83k.
La relation 83.x − 192.y = 1 devient alors 83.x = 192.(y0 + 83k) + 1 = 83.(x0 + 192k) c’est à dire
x = x0 + 192k.
Ensuite on vérifie que n’importe quel couple du genre (x0 + 192k, y0 + 83k) est bien une solution de
(E).

L’ensemble des solutions de (E) est (155 + 192k, 67 + 83k), k ∈ Z

3. On utilisera la propriété suivante : Si a, b et n sont des entiers tels que

a ≡ b[n],
alors pour tout entier naturel k on a :
ak ≡ bk [n]

Posons A = 0, . . . 192 . Pour tout a ∈ A, f (a) et g(a) sont les seuls éléments de A tels que :
f (a) ≡ a83 [193] (1)
et g(a) ≡ a155 [193] (2)
Puisque g(a) appartient à A, dans (2), on peut remplacer a par f (a) :

g(f (a)) ≡ f (a)155 [193]

Dans (1) utilisons la propriété citée avec k = 155 :

 155
f (a)155 ≡ a83 [193]

On obtient alors par transitivité de ≡:

g(f (a)) ≡ a83.155 [193] (3)

a. Reprenons la relation
83.x0 + 192.y0 = 1
qui s’écrit aussi :
83.x0 = 1 + 192.y0
Cette relation permet d’avoir :
a83.x0 = a1+192.y0 = a (a192 ).67
Comme nous le savons déjà a192 ≡ 1[193]. Donc a83.155 = a83.x0 = a1+192.y0 ≡ a. 167 [193].
Finalement
a83.155 ≡
a[193] (4).

(3) et (4) entraı̂nent par transitivité :

g(f (a)) ≡ a[193]
g(f (a)) et a sont des éléments de A équivalents modulo 193.
Nous allons monter qu’ils sont égaux.
g(f (a)) et a sont des éléments de A entraı̂ne |g(f (a)) − a| ≤ 192
g(f (a)) ≡ a[193] signifie il existe un entier k tel que g(f (a)) − a = 193k.
On déduit de ces deux propriétés que 193|k| ≤ 192 c’est à dire k = 0 ou g(f (a)) = a.
Le même raisonnement montre que pour tout a ∈ A, on a : f (g(a)) = a.
Nous venons de démontrer que f ◦ g = g ◦ f = IA

 30

Exercice 3 (4 points).

1. a. Déterminer les restes respectifs des divisions euclidiennes de 31 , 32 , 33 par 13.

1 pt

b. En déduire les restes de la division euclidienne par 13 des différentes puissances de 3 à exposants
entiers naturels.
1 pt
2. Déterminer les entiers naturels n tels que An = 3n + 32n + 33n soit divisible par 13.
1pt
3. Quels sont parmi les nombres 1010100 et 1001001000 écrits dans le système de numération de base
3 ceux qui sont divisibles par 13 ?
1 pt

Réponse.

1. a. Les restes de la division euclidienne de 31 , 32 , 33 par 13 sont 3, 9, 1

b. Soit a = 3n une puissance de 3 avec n ∈ N∗ . Si r est le reste de la division euclidienne de n par 3,

il existe un entier q tel que n = 3q + r.
Ce qui entraı̂ne :
33 ≡ 1[13]
⇒ (33 )q ≡ 1q [13]
.
⇒ 33q × 3r ≡ 3r [13]
⇔ 3n ≡ 3r [13]
Puisque 0 ≤ r ≤ 2, 3r vaut 30 = 1, 31 = 3 ou 32 = 9.
Les restes de la division euclidienne par 13 des différentes puissances de 3 à exposants entiers
naturels sont donc 1, 3 ou 9.

2. D’après la question précédente, si r est le reste de la division euclidienne de n par 3, alors 3n ≡ 3r [13]
On en déduit que An ≡ 3r + 32r + 33r [13].
Si r = 0, alors An ≡ 1 + 1 + 1 = 3[13] et An n’est pas un multiple de 13.
Si r = 1, alors An ≡ 31 + 32 + 33 = 39 ≡ 0[13] et An est un multiple de 13.
Si r = 2, alors An ≡ 32 + 34 + 36 ≡ 32 + 31 + 30 = 13 ≡ 0[13] et An est un multiple de 13.
En résumé pour que An = 3n + 32n + 33n soit divisible par 13 il faut et il suffit que n ne soit
pas un multiple de 3.

1 × 36 + 0 × 35 + 1 × 34 + 0 × 33 + 1 × 32 + 0 × 31 + 0 × 30
3. Le nombre 1010100 en base 3 s’écrit : = 36 + 34 + 32
= 33n + 32n + 3n avec n = 2
le nombre 1010100 en base 3 est multiple de 13.
Comme 2 n’est pas multiple de 3, Vérification :
l’écriture décimale de 1010100 est 819 et on a bien 819/13 = 63 Le nombre 1001001000 en base 3 s’écrit :
1 × 39 + 1 × 36 + 1 × 33 le nombre 1001001000 en base 3 n’est pas multiple de 13.
3n 2n n Comme 3 est multiple de 3,
= 3 + 3 + 3 avec n = 3
Vérification : l’écriture décimale de 1001001000 est 20439 et on a bien 20439/13 = 1572, 230769


Exercice 4 (4 pts). On considère la suite (un ) d’entiers naturels définie par :

u0 =27
∀n ∈ N, un+1 =3un − 4

1. Calculer u1 , u2 , u3 et u4 .Quelle conjecture peut-on émettre concernant les deux derniers chiffres
de un ? 2 × 0,25 pts
 31

2. Montrer que pour tout entier naturel n, un+2 ≡ un [8].

En déduire que pour tout entier naturel n, u2n ≡ 3 [8] et u2n+1 ≡ 5 [8].
0,25+0,5+0,5 pts
3. Pour tout entier naturel n on pose : vn = un − 2.
Montrer que la suite (vn ) est une suite géométrique dont on déterminera le premier terme et la raison.
En déduire que pour tout entier naturel n, 2un = 50 × 3n + 4.
2 × 0,25 pt
4. Montrer que pour tout entier naturel n, 2un ≡ 54 [100].
Déterminer les deux derniers chiffres de l’écriture décimale de un suivant les valeurs de n.
0,25 + 0,75 pt
5. Montrer que deux termes consécutifs de la suite (un ) sont premiers entre eux.
0,75 pt

Réponse.
1. u0 = 27, u1 = 77, u2 = 227, u4 = 677
Conjecturons que les deux derniers chiffres de un sont 27 ou 77
2. Puisque le premier terme u0 est un entier, on montre facilement par récurrence que pour tout
n ∈ N∗ , un est bien un entier comme l’affirme l’énoncé.
On a pour tout n ∈ N∗ :

un+2 = 3 un+1 − 4
= 3(3 un − 4) − 4
= 9 un − 16
donc

un+2 − un = 8 un − 16
.
= 8( un − 2)
Ainsi un+2 − un est un multiple de 8 ; ce qui se traduit par :

un+2 ≡ un [8].

En prenant pour n un entier pair 2p, p ∈ N cette relation se traduit par :

u2(p+1) ≡ u2p [8]

c’est à dire en posant pour tout p ∈ N∗ : u 2p = ap :

ap+1 ≡ ap [8].

Deux termes consécutifs de la suite (ap ) sont donc congrus modulo 8 ; donc tous les termes sont
congrus au premier terme a0 = u0 = 27 qui lui-même est congru à 3. Conclusion u2n ≡ 3 [8]
(On peut aussi utiliser la relation précédente pour faire une récurrence : Lepremier terme a0 = u0 = 27
est congru à 3. Supposons que ak soit congru à 3 pour tout k appartenant à 0, . . . , n et montrons que
an+1 est congru à 3.. . . ).
En prenant pour n un entier impair 2p + 1, p ∈ N cette relation se traduit par :

u2(p+1)+1 ≡ u2p+1 [8]

c’est à dire en posant pour tout p ∈ N∗ : u2p+1 = bp :

bp+1 ≡ bp [8]

Deux termes consécutifs de la suite (bp ) sont donc congrus modulo 8 ; donc tous les termes sont congrus
au premier terme b0 = u1 = 77 qui lui-même est congru à 5. Conclusion u2n+1 ≡ 5 [8].
(On peut aussi utiliser la relation précédente pour faire une récurrence : Lepremier terme b0 = u1 = 77
est congru à 5. Supposons que bk soit congru à 5 pour tout k appartenant à 0, . . . , n et montrons que
bn+1 est congru à 5.. . . ).
 32

3. On a pour tout n ∈ N∗ :
vn+1 = un+1 − 2
= 3un − 6
= 3(un − 2)
= 3vn .
La suite (vn ) est donc géométrique de raison 3 et de premier terme v0 = u0 − 2 = 25.
Par conséquent, pour tout n ∈ N∗ : vn = 3n v0 c’est à dire un = 2 + 25 × 3n ou 2un = 4 + 50 × 3n
4. De cette relation on déduit 2un − 54 = 50(3n − 1), ce qui entraı̂ne : 2un − 54 ≡ [50]
De plus (3n − 1) est pair parce que 3n est impair ; donc 2un − 54 est un multiple de 2 × 50 = 100 c’est
à dire 2un − 54 ≡ [100].
Cette dernière relation se traduit par : il existe un entier q tel que 2un = 54 + 100p soit, un = 27 + 50p.
Le nombre 50p se terminant par 50 ou 00, le nombre un se termine par 27 + 50 = 77 ou 27 + 00 = 27
5. Remarquons d’abord que un est impair parce que son écriture décimale se termine par 7 ; donc tous
ses diviseurs sont impairs.
Soit d un diviseur commun positif de un+1 et un . Il existe deux entiers p et q (dépendant de n) tels
que un+1 = pd et un = qd.
La relation un+1 = 3un − 4 qui définit la suite (un ) devient d(3q − p) = 4. Ainsi d, qui est un nombre
impair, divise 4 c’est à dire d = 1 et un+1 et un sont bien premiers entre eux.
On peut aussi dire : Si a et b sont deux entiers tels qu’il existe deux entiers q et r avec a = bq + r
alors a ∧ b = b ∧ r et l’écriture un+1 = 3un − 4 montre que un+1 ∧ un = un ∧ 4 = 1 la dernière égalité
provenant de ce que les seuls diviseurs positifs de 4 sont 1, 2 et 4 et un est impair.


Exercice 5 (4 points).
On considère la suite (un ) définie pour tout entier naturel n non nul par :

un = 2n + 3 × 7n + 14n − 1.

1. a. Calculer u3
0, 5 pt

b. Montrer que, pour tout entier naturel n non nul, un est pair.
0, 5 pt

c. On note (E) l’ensemble des nombres premiers qui divisent au moins un terme de la suite (un ).
Les entiers 2, 3, 5 et 7 appartiennent-ils à l’ensemble (E).
0, 5 pt
2. On rappelle le petit théorème de Fermat : ≪ Si p est un nombre premier et q un entier naturel
premier avec p, alors q p−1 ≡ 1[p].) ≫
Soit p un nombre premier strictement supérieur à 7.
Soient m et n deux entiers naturels tels que 14 = mn.

a. Quelles sont les valeurs possibles de m ? 0, 5 pt

b. Montrer que 14 × mp−2 ≡ n (modulo p). 0, 5 pt

c. En déduire que 14up−2 ≡ 0 (modulo p). 0, 5 pt

d. L’entier p appartient-il à l’ensemble E ? 0, 5 pt

e. Déterminer E. 0, 5 pt

Réponse.

1. a. u3 = 3780.
 33

b. 2n et 14n sont des nombres pairs, 3 × 7n produit de nombres impairs, est impair ; donc un est un
nombre pair.

c. u3 = 3780 = 22 × 33 × 5 × 7 ; u3 est donc divisible par 2, 3, 5 et 7. Oui 2, 3, 5 et 7 appartiennent à

E.

2. a. Les valeurs possibles de m sont 1, 2, 7, 14

b. 14 × mp−2 = mn × mp−2 = n × mp−1 .

p étant premier et strictement supérieur à 7, est premier avec m ; donc, d’après le petit théorème de
Fermat mp−1 ≡ 1 [p]. On obtient, en multipliant par n :

14 × mp−2 = n × mp−1 ≡ n [p]

En appliquant ce résultat à m = 2, 7 puis 14, on en déduit modulo p :

14up−2 = (14 × 2p−2 ) + 3 × (14 × 7p−2 ) + (14 × 14p−2 ) − 14 ≡ 7 + 3 × 2 + 1 − 14 = 0

c. Puisque p divise 14up−2 et qu’il est premier avec 14, il divise up−2 d’après le théorème de Gauss ;
donc p ∈ E.

d. 2, 3, 5 et 7 appartiennent à E et si p est un nombre premier strictement supérieur à 7, il appartient

aussi à E.
E est donc l’ensemble de tous les nombres premiers.


Exercice 6.
1. Déterminer l’ensemble des couples (x, y) d’entiers relatifs, solutions de l’équation

(E) : 8x − 5y = 1.

0, 5 pt
2. Soit m un entier relatif tel qu’il existe un couple (p, q) d’entiers relatifs vérifiant
m = −8p + 4 et m = −5q + 3.

a. Montrer que le couple (p, q) est solution de l’équation (E) et en déduire que m ≡ −12 [40].
1 pt = 2 × 0, 5 pt

b. Réciproquement si m ≡ −12 [40], montrer qu’il existe un couple (p, q) d’entiers relatifs vérifiant
m = −8p + 4 et m = −5q + 3.
0, 5 pt

c. Déterminer le plus petit des entiers naturels m tels qu’il existe un couple (p, q) d’entiers relatifs
vérifiant m = −8p + 4 et m = −5q + 3. 0, 5 pt
3. Un groupe de 8 menuisiers se partage à parts égales m planches de bois, il reste 4 planches qu’ils
gardent dans le magasin.
Un autre groupe de 5 menuisiers se partagent le même nombre de planches à parts égales, il reste 3
planches qu’ils gardent dans le magasin.
Quelle est la valeur minimale de m ? 0, 75 pt
Les questions qui suivent sont indépendantes de ce qui précède.
4. Soit n un entier naturel.

a. Montrer que pour tout entier naturel k, on a : 23k ≡ 1 [7]. 0, 25 pt

b. Quel est le reste de la division euclidienne de 22012 par 7 ? 0, 25 pt

5. Soit a et b deux entiers naturels inférieurs ou égaux à 9 avec a non nul.
On considère le nombre N = a 103 + b.
On se propose de déterminer parmi ces nombres N ceux qui sont divisibles par 7.
 34

a. Vérifier que 103 ≡ −1 [7]. 0, 25 pt

b. En déduire tous les entiers naturels N cherchés. 1 pt

Réponse.
1. Pour trouver une solution particulière de l’équation 8x−5y = 1 on peut utiliser l’algorithme habituel
ou voir la solution ”évidente” x0 = 2 et y0 = 3. 
8x − 5y = 1
Si (x, y) un solution quelconque, on doit avoir et en faisant la différence 8(x −
8x0 − 5y0 = 1
x0 ) − 5(y − y0 ) = 0 soit 8(x − x0 ) = 5(y − y0 ). Par conséquent, 8 divise le produit 5(y − y0 ) et comme
il est premier avec 5, il divise y − y0 d’après le théorème de Gauss ; il existe donc un entier k tel que
y − y0 = 8k i.e y = 8k + 3. La relation 8(x − x0 ) = 5(y − y0 ) entraine x = 5k + 2.
L’ensemble des solutions de l’équation 8x − 5y = 1 est {(5p + 2, 8p + 3), p ∈ Z}

m = −8p + 4
2. a. S’il existe un couple (p, q) d’entiers relatifs vérifiant , en faisant la différence
m = −5q + 3
on obtient 8p − 4 − 5q + 3 = 0 i.e 8p − 5q = 1 ; le couple (p, q) est bien solution de l’équation.
D’après la question précédente, il existe un entier k tel que p = 5k + 2 et alors m = −8(5k + 2) + 4 =
−40k − 12 i.e m ≡ −12 [40].

b. Réciproquement si m ≡ −12 [40], il existe un entier k tel m = 40k − 12.

Alors m = 8(5k − 2) + 4 = 8p + 4 avec p = 5k − 2.
Et m = 5(8k − 3) + 3 = 5q + 3 avec q = 8k − 3.

12
c. Pour que m soit un entier naturel, il faut et il suffit que 40k − 12 soit ≥ 0 i.e k ≥ . La plus
40
petite valeur de k est 1 et la plus petite valeur de m est 40 − 12 = 28.
3. Puisque les 8 menuisiers se partagent les planches à parts égales, il existe un entier naturel p tel
que m − 4 = 8p i.e m = 8p + 4.
De même il existe un entier naturel q tel que m = 5q + 3 et la question précédente entraı̂ne que la
valeur minimale du nombre de planches est 28.

4. a. Puisque 8 ≡ 1 [7], 23k = 8k ≡ 1k [7] ; donc on a bien 23k ≡ 1 [7]

b.
22012 = 23×670+2
≡ 22 [7] d’après le a.
Donc le reste de la division euclidienne de 22012 par 7 est 4.

5. a. Puisque 103 = 1000 = 7 × 142 + 6 ≡ 6 [7] ≡ −1 [7].

b. D’après le a. N = a103 + b ≡ −a + b [7]. Donc si N est divisible par 7, alors a ≡ b [7].

Réciproquement, si a ≡ b [7] alors il existe un entier k tel que a = 7k + b et

N = (7k + b)103 + b = 7 × 103 k + 103 b + b ≡ 0 − b + b [7] ≡ 0 [7]

N est donc divisible par 7.

Voici les valeurs possibles de N

a 1 1 2 2 3 4 5 6 7 7 8 8 9 9
b 8 1 9 2 3 4 5 6 0 7 1 8 2 9
N 1008 1001 2009 2002 3003 4004 5005 6006 7000 7007 8001 8008 9002 9009

Exercice 7 (2013). On considère l’équation

(E) : 5x + 6y = 29 où x et y sont des entiers

 35

1. a. Déterminer un couple d’entiers relatifs (u, v) tel que 5u + 6v = 1.

En déduire une solution particulière de (E). 2 × 0.5 pt

b. Résoudre dans Z2 l’équation (E). 0.5 pt

−
→ → − − →
Dans l’espace E muni d’un repère orthonormé (O, i , j , k ), on considère le plan P d’équation

5x + 6y + 4z = 29
−
→ − →
Soit D la droite d’intersection du plan P et du plan (O, i , j ).
−
→ − →
c. Représenter graphiquement la droite D dans le plan (O, i , j ).
Montrer que D a un seul point dont les coordonnées sont des entiers naturels que l’on déterminera.
0.25 + 0, 75 pt
2. On considère un point M du plan P dont les coordonnées x, y et z sont des entiers naturels.

a. Montrer que l’entier x est impair. 0.75 pt

b. On pose x = 2p + 1 où p est un entier naturel.

Montrer que p + z est un multiple de 3. 0.75 pt

Réponse.

le couple (u, v) = (−1, 1) vérifie 5u + 6v = 1.

1. a.
(x0 , y0 ) = (−29, 29) est une solution particulière de (E).
On en déduit en mutipliant par 29, que

b. Si (x, y) est une solution quelconque de (E), on a :

5x0 + 6y0 = 29
5x + 6y = 29
et en faisant la différence membre à membre : 5(x − x0 ) + 6(y − y0 ) = 0 i.e 5(x − x0 ) = −6(y − y0 ). Donc
6 divise 5(x − x0 ), et comme il est premier avec 5, il doit diviser x − x0 (théorème de Gaus). Il existe un
entier p tel que x − x0 = 6p et la relation 5(x − x0 ) = −6(y − y0 ) devient y − y0 = −5p.
L’ensemble des solutions de (E) est donc {(6p − 29, −5p + 29), p ∈ Z}


5x + 6y + 4z = 29
c. La droite D a pour système d’équations .
z = 0
−
→ − →
Par conséquent dans le plan (O, i , j ) elle a pour équation 5x + 6y = 29. Voici sa représentation
graphique.
Si M est un point de D aux coordonnées (x, y, 0) entières, le couple (x, y) est solution de (E).
Si de plus ces entiers sont positifs , il existe un entier p tel que

x = 6p − 29 ≥ 0 et y = −5p + 29 ≥ 0

i.e 29/6 ≤ p ≤ 29/5 et p = 5.

Il existe donc un seul point de D ayant ses coordonnées dans N3 .
De plus x = 6 × 5 − 29 = 1 et y = −5 × 5 − 29 = 4.
Les coordonnées de l’unique point de D dont les coordonnées sont des entiers naturels sont (1, 4, 0)
(voir figure).

2. a. Si M est un point de P aux coordonnées (x, y, z) entières, on doit avoir

5x = 29 − 6y − 4z et comme le deuxième membre de cette égalité est un nombre impair, x doit
être impair.
 36

M
b
4

3 D

−1
→
j
0
−2 −1 0 1−
→
i 2 3 4 5 6 7

−1

−2

Figure 5.1 – La droite D et son unique point aux coordonnées entiers naturels

b. Si x = 2p + 1, p ∈ Z, la relation précédente devient : 10p + 4z = −6y + 24.

10 ≡ 1[3] et 4 ≡ 1[3] entraı̂ne p + z ≡ 10p + 4z = −6y + 24 ≡ 0[3]
Mais


Exercice 8 (5 points).
1. Soient a, b, c des entiers relatifs et n un entier naturel non nul.

a. Démontrer que a et b sont premiers entre eux si et seulement si a et bn sont premiers entre eux.
1 pt

b. En déduire que si a et b sont premiers entre eux et si a divise le produit bn c, alors a divise c.
0, 5 pt
2. On se propose dans cette question de déterminer les solutions rationnelles de l’équation suivante :

(E) : 7x3 + 2x2 + 2x − 5 = 0

a. Démontrer que l’équation (E) admet une solution réelle unique appartenant à l’intervalle ]0, 1[.
1 pt
p
b. En utilisant les résultats de la question 1, démontrer que si (E) admet une solution rationnelle
q
où p et q sont des entiers premiers entre eux, alors p divise 5 et q divise 7.
1 pt

c. Résoudre l’équation (E) dans Q ensemble des rationnels. 0, 75 pt

3. Résoudre l’équation (E) dans C ensemble des nombres complexes. 0, 75 pt

Réponse.
 37

1. a. Si n = 1, la propriété est triviale. Supposons donc n ≥ 2.

a ∧ bn = 1 ⇔ ∃u, v ∈ Z : au + bn v = 1 d’après Bezout
⇒ au + bv ′ = 1 avec v ′ = bn−1 v
⇒ a∧b=1
Réciproquement

a∧b=1 ⇔ ∃u, v ∈ Z : au + bv = 1 d’après Bezout

⇔ ∃u, v ∈ Z : bv = 1 − au
⇒ bn v n = (1 − au)n
Xn
⇔ bn v n = Cnp ap (−u)p
p=0
n
X
Tous les termes de la somme Cnp ap (−u)p contiennent le facteur a sauf le premier (correspondant à
p=0
p = 0) qui vaut 1 ; donc cette somme s’écrit 1 + au′ , u′ ∈ Z et
a∧b=1 ⇒ bn v ′ = 1 + au′ avec v ′ = v n
⇔ −au′ + bn v ′ = 1
⇒ a ∧ bn = 1 d’après Bezout

b. Si a et b sont premiers entre eux, alors a est premier avec bn , d’après le a.

Comme a divise le produit bn c, il doit diviser c, d’après Gauss.

2. a. La fonction f : x 7→ 7x3 + 2x2 + 2x − 5 est définie sur R, continue et dérivable et

∀x ∈ R, f ′ (x) = 21x2 + 4x + 2.
La dérivée est un polynôme du second degré en x dont le discriminant réduit 22 − 42 est strictement
négatif ; la dérivé est alors strictement positive sur R. La fonction f est donc une bijection de R sur
f (R) = R, cette dernière égalité provenant du fait que lim f (x) = +∞ et lim f (x) = −∞. L’équation
x7→+∞ x7→−∞
f (x) = 0 admet donc une solution réelle unique.
f (0)f (1) = −30 < 0 donc la solution réelle de l’équation appartient à ]0, 1[, d’après le théorème des
valeurs intermédiaires.
p3 p2 p
b. Si p/q est solution de l’équation, on doit avoir 7 3
+ 2 2 + 2 − 5 = 0 soit, en multipliant par q 3 :
q q q
7p3 + 2p2 q + 2pq 2 − 5q 3 = 0
Cette relation s’écrit
p(7p2 + 2pq + 2q 2 ) = 5q 3
donc p divise 5q 3 et d’après la question précédente, p divise 5.
Cette relation s’écrit aussi
7p3 = q(5q 2 − 2pq − 2p2 )
donc q divise 7p3 et d’après la question précédente, q divise 7.

c. Une éventuelle solution rationnelle de l’équation étant positive, on peut considérer que p et q sont
positifs ; alors, les seules valeurs possibles de p sont 1 et 5 et les seules valeurs possibles de q sont 1 et 7.
Comme en plus la solution appartient à l’intervalle ]0, 1[, les seuls candidats solutions sont 1/7 et 5/7.
l’unique solution rationnelle de l’équation est 5/7.
Un calcul direct montrer alors que
3. Ce qui précède montre que 7x − 5 est un facteur du polynôme 7x3 + 2x2 + 2x − 5.
En procédant par identification ou par division euclidienne, on obtient
7x3 + 2x2 + 2x − 5 = (7x − 5)(x2 + x + 1)
les autres solutions de l’équation sont donc celles de x2 + x + 1 = 0.
√
2
Le discriminant de cette équation est −3 = i 3 .
√ √
−1 + i 3 −1 − i 3
Les solutions complexes de l’équation sont donc 5/7, j = et j =
2 2


 38

Exercice 9 (2017).
Soit a un entier naturel non nul et (un )n∈N la suite définie par : un = pgcd(n, a).

1. a. Pour a = 15, calculer les 3 premiers termes de la suite (un ). 3 × 0.25 pt

b. Pour a = 4, soient m et n des entiers naturels tels que um = un = 2.

Montrer que um+n = 4. 0.75 pt

2. a. Soit b un entier naturel.

Démontrer que pour tout entier relatif q on a : pgcd(a, b) = pgcd(a, b − qa).
0.75 pt

b. Calculer u0 et ua . 2 × 0.25 pt

c. Démontrer que un+a = un .

Quelle propriété de la suite (un ) a-t-on mise en évidence ? 0.5 + 0.25 pt
3. Pour a = 15, calculer un avec n = 1521 + 2. 0.5 pt

Réponse. Soit a un entier naturel non nul et (un )n∈N la suite définie par :
un = pgcd(n, a).

1. a. u0 = pgcd (0, 15) = 15, u1 = pgcd (1, 15) = 1, u2 = pgcd (2, 15) = 1.

b. Pour a = 4, um = un = 2 signifie pgcd (m, 4) = pgcd (n, 4) = 2.

m et n sont donc des nombres paires non multiples de 4.
Il existe donc des entiers naturels impairs 2m′ + 1 et 2n′ + 1 tels que m = 2(2m′ + 1) et n = 2(2n′ + 1).
Alors m + n = 4(m′ + n′ + 1), puis pgcd (m + n, 4) = 4 c’est à dire um+n = 4.

2. a. Soit b un entier naturel.

Démontrer que pour tout entier relatif q on a : pgcd(a, b) = pgcd(a, b − qa).
Soit d un entier.
Si d est un diviseur commun de a et b, il existe deux entiers m et n tels que a = dm et b = dn. Alors
b − qa = d(n − qm). Donc d est un diviseur commun de a et b − qa.
Réciproquement, si d est un diviseur commun de a et b − qa, il existe deux entiers m′ et n′ tels que
a = dm′ et b − qa = dn′ . Alors b = (b − qa) + qa = d(n′ + qm′ ). Donc d est un diviseur commun de a et b.
{a, b} et {a, b − qa} ayant les mêmes diviseurs commun ont le même pgcd.

b. u0 = pgcd (0, a) = a et ua = pgcd (a, a) = a.

c.
un+a = pgcd (a, n + a)
= pgcd (a, n) d’après le a. avec b = n + a et q = −1 .
= un
Nous venons de démontrer que la suite (un ) est périodique et a est une période.
3. n = 1521 + 2 = 2 + 15m avec m = 1520 donc

un = u2+15m
= u2 car 15 est une période de (un )
.
= pgcd (2, 15)
= 1


Table des matières

I Généralités 3
1 Divisibilité 4
1.1 Premiers concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Divisibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 pgcd et ppcm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Définition et premières propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2 L’ensemble des nombres premiers est infini . . . . . . . . . . . . . . . . . . . . . . 8

2 Division euclidienne et conséquences 10

2.1 Division euclidienne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Conséquences principales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1 Théorème de Bézout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.2 Lemme de Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.3 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Décompositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.1 Décomposition d’un nombre premier . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.2 Décomposition d’un entier dans une base . . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

II Arithmétique modulaire 18
3 Congruence modulo n 20
3.1 Congruence modulo n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 Système complet de résidus modulo n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 Bezout et Gauss modulaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

4 Conséquences 25
4.1 Critères de divisibilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 Théorème chinois . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

5 Exercices Bac 27

39