CH 1 DIVISIBILITE ET CONGRUENCES

Introduction : l’arithmétique au « quotidien »

L’arithmétique est une branche des mathématiques qui étudie les propriétés des entiers. Euclide, Diophante, Fermat,
Gauss et plus récemment Andrew Wiles ont contribué aux avancées dans ce domaine. L’arithmétique est aujourd’hui au
centre des problèmes liés à l’informatique. On s’intéressa en particulier dans ce chapitre aux codes-barres, aux relevés
d’identités bancaires et au numéro INSEE qui sont de codes qui se terminent tous par une clé, appelée clé de contrôle.
La division euclidienne et les congruences sont les principaux outils utilisés pour « fabriquer » ces clés.

ℕ = {0; 1; 2; … } est l’ensemble des entiers naturels et ℤ = {… ; −2; −1; 0; 1; 2; … } celui des entiers relatifs.

I. Divisibilité dans ℤ
1. Notion de multiples et de diviseurs
DEFINITION 1
𝑎 et 𝑏 sont deux entiers relatifs avec 𝑏 ≠ 0.
On dit que 𝒃 divise 𝒂, et on note 𝒃|𝒂 , si il existe un entier relatif 𝑘 tel que 𝒂 = 𝒌𝒃 .

AUTRE ECRITURE : On écrit aussi : si 𝑏|𝑎 alors ∃𝑘 ∈ ℤ tel que 𝑎 = 𝑘𝑏.

Le symbole ∃ signifie « il existe »
VOCABULAIRE : On dit aussi que 𝒃 est un diviseur de 𝒂, que 𝒂 est divisible par 𝒃 et que 𝒂 est un
multiple de 𝒃.

CONSEQUENCES :
 Tout entier relatif 𝑏 divise 0 (0 = 𝑏 × 0, 𝑏 ∈ ℤ). On dit que ℤ∗ est l’ensemble des diviseurs de 0.
 Tout entier relatif 𝑏 admet au moins comme diviseur : 1; −1; 𝑏 et −𝑏.
Tout entier relatif 𝑏 admet un nombre fini de diviseurs compris entre −𝑏 et 𝑏.
 Tout entier naturel 𝑛 non nul admet au plus 𝑛 diviseurs dans ℕ.
En effet, si 𝑑 est un diviseur de 𝑛, c’est-à-dire si 𝑑|𝑛 alors ∃𝑘 ∈ ℕ tel que 𝑛 = 𝑘𝑑.
Or, comme 𝑘 ≠ 0 (en effet si 𝑘 = 0 alors 𝑛 = 0 ce qui est exclu), 𝑘 ≥ 1 donc 𝑘𝑑 ≥ 𝑑, c’est-à-
dire 𝑛 ≥ 𝑑 qui s’écrit 𝑑 ≤ 𝑛.
Donc, il y a au plus 𝑛 diviseurs de 𝑛.

PROPRIETE 1
𝑎 et 𝑏 sont deux entiers relatifs.
𝑏|𝑎 ⟺ −𝑏|𝑎 ⟺ 𝑏|−𝑎 ⟺ −𝑏|−𝑎.

REMARQUE : 𝑎 et −𝑎 ont les mêmes diviseurs dans ℤ. Les diviseurs de −𝑎 étant les opposés des
diviseurs positifs de 𝑎, on restreindra l’étude à la divisibilité dans ℕ.

2. Propriétés
PROPRIETE 2
𝑎, 𝑏 et 𝑐 trois entiers relatifs non nuls. Si 𝑎|𝑏 et si 𝑏|𝑐 alors 𝑎|𝑐 .
On dit que la divisibilité est transitive.

PROPRIETE 3
𝑎, 𝑏 et 𝑐 trois entiers relatifs non nuls.
Si 𝑎|𝑏 et si 𝑎|𝑐 alors 𝑎|𝑏𝑢 + 𝑐𝑣 où 𝑢 et 𝑣 sont deux entiers relatifs.
On dit que l’entier bu + cv est une combinaison linéaire de b et c .

CAS PARTICULIERS : Si 𝑎|𝑏 et si 𝑎|𝑐 alors 𝑎|𝑏 − 𝑐 (𝑢 = 1,𝑣 = −1) et 𝑎|𝑏 + 𝑐 (𝑢 = 𝑣 = 1).
Si 𝑎|𝑏 alors 𝑎|𝑏𝑢 où 𝑢 ∈ ℤ.
Page 1 sur 6
 3. Applications
a) Utiliser la divisibilité dans ℕ et dans ℤ.
(1) Déterminer les entiers naturels 𝑛 tel que 11 divise 𝑛 + 5.
METHODE : Pour déterminer 𝑛 tels que 𝑘|𝑓(𝑛) , on utilise la définition de la divisibilité.

(2) Déterminer les entiers relatifs 𝑛 tels que 2𝑛 + 3 divise 10.

METHODE : Pour déterminer 𝑛 tels que 𝑓(𝑛)|𝑘 , où 𝑘 ∈ ℤ,on résout les équations
𝑓(𝑛) = 𝑑 pour tout diviseur 𝑑 de 𝑘.

(3) Déterminer les entiers relatifs 𝑛 tels 𝑛 + 7 que divise 3𝑛 + 32.

METHODE : Pour déterminer 𝑛 tels que 𝑓(𝑛)|𝑔(𝑛) , on se ramène au cas où
𝑓(𝑛)|𝑘 par combinaisons linéaires « bien choisies ».

REMARQUES :
 Une combinaison linéaire « bien choisie » est une combinaison linéaire qui
permet « d’éliminer les 𝑛 ».
 ATTENTION, dans ce dernier exemple, on a raisonné en utilisant uniquement
des implications. Il est donc nécessaire de vérifier que les valeurs trouvées
conviennent (c’est la réciproque).

b) Résoudre une équation à deux inconnues entières dans ℕ ou dans ℤ

Déterminer tous le couples d’entiers relatifs (𝑥; 𝑦) solutions de l’équation 𝑥² − 𝑦² = 7.
METHODE : Pour résoudre ces équations, on se ramène à une équation de la forme 𝐴 × 𝐵 = 𝐶
où l’on connait les diviseurs de 𝐶.

II. Division euclidienne

1. Division euclidienne d’un élément de ℤ par un élément de ℕ
THEOREME 1
Soient 𝑎 un entier relatif et 𝑏 un entier naturel tel que 𝑏 ≠ 0.
Il existe un unique couple (𝑞; 𝑟) d’entiers relatifs tels que 𝒂 = 𝒃𝒒 + 𝒓 avec 0 ≤ 𝑟 < 𝑏.

DEMONSTRATION :
• Existence du couple (𝑞; 𝑟) : On raisonne par disjonction de cas.
1ier cas : Soit 𝑎 est multiple de 𝒃 alors ∃𝑞 ∈ ℤ tel que 𝑎 = 𝑏𝑞, donc en prenant 𝑟 = 0 , on a
bien 𝑎 = 𝑏𝑞 + 𝑟 et 𝑟 vérifie 0 ≤ 𝑟 < 𝑏.
2nd cas : Soit 𝑎 n’est pas multiple de 𝒃 alors 𝑎 est compris entre deux multiples consécutifs
de 𝑏 donc ∃𝑞 ∈ ℤ tel que 𝑎 est compris entre 2 entiers de la forme 𝑏𝑞 et 𝑏(𝑞 + 1).
On peut écrire que 𝑏𝑞 < 𝑎 < 𝑏(𝑞 + 1) où 𝑏(𝑞 + 1) est le plus petit multiple de 𝑏
supérieur à 𝑎.

L’encadrement 𝑏𝑞 < 𝑎 < 𝑏(𝑞 + 1) devient 𝑏𝑞 < 𝑎 < 𝑏𝑞 + 𝑏, puis

𝑏𝑞 − 𝑏𝑞 < 𝑎 − 𝑏𝑞 < 𝑏𝑞 + 𝑏 − 𝑏𝑞 et 0 < 𝑎 − 𝑏𝑞 < 𝑏. En posant 𝑟 = 𝑎 − 𝑏𝑞 , on a
alors 0 < 𝑟 < 𝑏 et 𝑎 = 𝑏𝑞 + 𝑟 .
En résumé, après l’étude des deux cas, ∃𝑞 ∈ ℤ tel que 𝑏𝑞 ≤ 𝑎 < 𝑏(𝑞 + 1),
c’est-à-dire 0 ≤ 𝑎 − 𝑏𝑞 < 𝑏 et en posant 𝑟 = 𝑎 − 𝑏𝑞 , on a 0 ≤ 𝑟 < 𝑏.
Donc, il existe un couple (𝒒; 𝒓) tel que 𝒂 = 𝒃𝒒 + 𝒓 avec 0 ≤ 𝒓 < 𝑏 .
Page 2 sur 6
 • Unicité du couple (𝑞; 𝑟) : O raisonne par l’absurde.
On suppose donc qu’il existe un autre couple(𝑞 ′ ; 𝑟 ′ ) différent du couple (𝑞; 𝑟) tel que 𝑎 = 𝑏𝑞 ′ + 𝑟′
avec 0 ≤ 𝑟′ < 𝑏.
On peut alors écrire 𝑎 = 𝑏𝑞 + 𝑟 et 𝑎 = 𝑏𝑞 ′ + 𝑟′ ce qui donne :
𝑏𝑞 + 𝑟 = 𝑏𝑞’ + 𝑟’, 𝑏𝑞 − 𝑏𝑞’ = 𝑟’ − 𝑟, 𝑏(𝑞 − 𝑞’) = 𝑟’ − 𝑟.
Par définition, on en déduit que 𝑟 ′ − 𝑟 𝑒𝑠𝑡 𝑢𝑛 𝑚𝑢𝑙𝑡𝑖𝑝𝑙𝑒 𝑑𝑒 𝑏 .
Or, 0 ≤ 𝑟 < 𝑏 c’est-à-dire −𝑏 < −𝑟 ≤ 0 et 0 ≤ 𝑟′ < 𝑏 donc en additionnant membre à membre, on
a : −𝑏 < 𝑟 ′ − 𝑟 < 𝑏 .
Mais, il n’y a qu’un seul multiple de 𝑏 compris entre −𝑏 et 𝑏, c’est 0 donc 𝑟 ′ − 𝑟 = 0 d’où 𝑟 ′ = 𝑟 .
D’où, 𝑏𝑞 ′ = 𝑏𝑞 et 𝑞 ′ = 𝑞 (𝑏 ≠ 0) ce qui absurde.
Donc, il existe un unique couple (𝒒; 𝒓) .

REMARQUE : Raisonner par « disjonction de cas », signifie lister tous les cas possibles et traiter chacun
d’entre eux.
EXEMPLE : ATTENTION , il y a de multiples écritures de 𝑎 sous la forme 𝑎 = 𝑏𝑞 + 𝑟 .
Si 𝑎 = 28 et 𝑏 = 8 alors 28 = 8 × 3 + 4 = 8 × 2 + 12 = 8 × 1 + 20 mais seule la 1ère
égalité, où 0 ≤ 𝑟 < 𝑏 est la relation de la division euclidienne de 𝑎 par 𝑏.

DEFINITION 2
𝑎 désigne un entier relatif et 𝑏 un entier naturel non nul.
Effectuer la division euclidienne 𝒂 de par 𝒃 c’est déterminer ce couple (𝑞; 𝑟).
𝑞 est le quotient et 𝑟 le reste de la division euclidienne de 𝑎 par 𝑏.

PROPRIETE 4
𝑎 ∈ ℕ et 𝑏 ∈ ℕ∗ , 𝑏|𝑎 si et seulement si le reste de la division euclidienne de 𝑎 par 𝑏 est nul.

𝑎
REMARQUE : Puisque 𝑏𝑞 ≤ 𝑎 < 𝑏(𝑞 + 1) et 𝑏 ≠ 0 alors 𝑞 ≤
𝑏
< 𝑞 + 1, 𝑞 est appelé la partie
𝑎
entière de . Par conséquent, avec la calculatrice, 𝒒 = 𝒑𝒂𝒓𝒕𝑬𝒏𝒕(𝒂/𝒃) (via le Menu
𝑏
𝑚𝑎𝑡ℎ puis Menu 𝑵𝑼𝑴) et 𝒓 = 𝒂 − 𝒃 ∗ 𝒒 .

ALGORITHME : Voici ci-dessous une fonction Python permettant de déterminer le quotient et le

reste de la division euclidienne de 𝑎 par 𝑏 avec 𝑎 ∈ ℤ et 𝑏 ∈ ℕ∗ .

EXEMPLE : Effectuer la division euclidienne de 2014 par 41 puis celle de −5000 par 17.

2. Ecriture d’un entier relatif quelconque

PROPRIETE 5
𝑎 ∈ ℤ et 𝑏 ∈ ℕ∗ .
Dans la division euclidienne de 𝑎 par 𝑏, on note 𝑞 le quotient et 𝑟 le reste.
Il y a 𝑏 valeurs possibles du reste 𝑟: 0,1,2, … , 𝑏 − 1.
Donc, tout entier relatif 𝑎 s’écrit sous l’une des formes :
𝒂 = 𝒃𝒒 + 𝟎, 𝒂 = 𝒃𝒒 + 𝟏, 𝒂 = 𝒃𝒒 + 𝟐, … , 𝒂 = 𝒃𝒒 + (𝒃 − 𝟏) avec 𝑞 ∈ ℤ.

EXEMPLE : Dans la division euclidienne de 𝑎 par 2, 𝑎 peut s’écrire sous les formes 𝑎 = 2𝑞 ou
𝑎 = 2𝑞 + 1, 𝑞 ∈ ℤ. Ce sont les écritures d‘un nombre pair et d’un nombre impair .

Page 3 sur 6
 Dans la division euclidienne de 𝑎 par 3, 𝑎 peut s’écrire sous les formes 𝑎 = 3𝑞, 𝑎 = 3𝑞 + 1
ou 𝑎 = 3𝑞 + 2, 𝑞 ∈ ℤ. Etc.…
Ce résultat est important et très utile lorsqu’on utilise un raisonnement par disjonction
de cas

3. Nombre et liste des diviseurs d’un entier - Fonction Python

L’objectif est d’obtenir une fonction Python qui affiche la liste des diviseurs d’un entier.
On crée d’abord une fonction en Python qui permet d’obtenir le nombre de diviseurs d’un entier 𝑛, 𝑛 ≥ 1
puis on la modifie afin d’obtenir la liste des diviseurs positifs d’un entier , 𝑛 ≥ 1 .

METHODE: Les diviseurs positifs d’un tel entier 𝑛, 𝑛 ≥ 1 appartiennent à l’ensemble

{1,2,3, … , 𝑛 − 1, 𝑛} = ⟦1; 𝑛⟧
Un entier 𝑘 de cet ensemble est un diviseur de 𝑛, si et seulement si, le reste de la
division euclidienne de 𝑛 par 𝑘 est nul
En balayant l’ensemble ⟦1; 𝑛⟧ et en testant, pour tout élément 𝑘 de cet ensemble
si le reste associé de la division euclidienne de 𝑛 par 𝑘 est nul, on obtiendra
l’ensemble des diviseurs de 𝑛.

REMARQUE : Le cœur des deux algorithmes est donc essentiellement composé d’une boucle et
d’un test de nullité.
Le reste 𝑟 de la division euclidienne de 𝑛 par 𝑘 s’obtient en utilisant l’instruction
𝑎%𝑏 qui renvoie le reste de la division euclidienne de 𝑎 par 𝑏 en Python.

4. Applications
a) Utiliser la définition de la division euclidienne
(1) La division euclidienne de 523 par un entier naturel non nul 𝑏 a un quotient égal à 17.
Déterminer les valeurs possibles de 𝑏 et du reste 𝑟.

(2) La division euclidienne de 256 par un entier naturel non nul 𝑏 a un reste égal à 25.
Déterminer les valeurs possibles de 𝑏 et du quotient 𝑞.
ATTENTION, ne pas oublier la condition sur le reste.

b) Déterminer les restes dans une division euclidienne

(1) 𝑛 désigne un entier naturel non nul. Déterminer, selon les valeurs de 𝑛, les restes de la
division euclidienne de 7𝑛 + 16 par 2𝑛 + 3.

METHODE : Ecrire 𝑎(𝑛) sous la forme 𝑏(𝑛)𝑞(𝑛) + 𝑟(𝑛) et vérifier la condition sur le
reste.

(2) Justifier que tout entier naturel 𝑛 s’écrit nécessairement sous l’une des trois formes 3𝑘, 3𝑘 + 1
ou 3𝑘 + 2 avec 𝑘 ∈ ℕ. En utilisant un raisonnement par disjonction de cas, démontrer que
dans la division euclidienne de (𝑛2 + 𝑛) par 3, le reste n’est jamais égal à 1. (𝑛 ∈ ℕ)

METHODE : On raisonne par disjonction de cas, c’est-à-dire, on liste tous les cas
possibles et on examine chacun d’entre eux.

Page 4 sur 6
III. Congruences dans ℤ
1. Définition
DEFINITION 3
Soit 𝑛 ∈ ℕ∗ et 𝑎 et 𝑏 deux entiers relatifs.
On dit que 𝒂 et 𝒃 sont congrus modulo 𝒏 si et seulement si 𝑎 et 𝑏 ont le même reste dans la division
euclidienne par 𝑛. On dit aussi que 𝑎 est congru à 𝒃 modulo 𝒏.
On note 𝑎 ≡ 𝑏 𝑚𝑜𝑑𝑢𝑙𝑜 𝑛 ou 𝒂 ≡ 𝒃[𝒏] ou 𝒂 ≡ 𝒃(𝒏) .

EXEMPLE : 31 ≡ 10[7] en effet 31 = 7 × 4 + 3 et 10 = 7 × 1 + 3.

8 ≡ −7[3] en effet 8 = 3 × 2 + 2 et −7 = 3 × (−3) + 2.

REMARQUE : 𝑎 ≡ 𝑎[𝑛]: on dit que la congruence est réflexive ;

si 𝑎 ≡ 𝑏[𝑛] alors 𝑏 ≡ 𝑎[𝑛]: on dit que la congruence est symétrique.

THEOREME 2
Soit 𝑛 ∈ ℕ∗ et 𝑎 et 𝑏 deux entiers relatifs.
𝑎 ≡ 𝑏[𝑛] ⟺ 𝑎 − 𝑏 est un multiple de 𝑛.

COROLLAIRE
 𝑎 ≡ 0[𝑛] ⟺ 𝑛 divise 𝑎.
 𝑟 est le reste de la division euclidienne de 𝑎 par 𝑛 ⟺ 𝑎 ≡ 𝑟[𝑛] et 0 ≤ 𝑟 < 𝑛

2. Propriétés de la congruence
PROPRIETE 6
Soit 𝑛 ∈ ℕ∗ et 𝑎, 𝑏 et 𝑐 trois entiers relatifs.
Si 𝑎 ≡ 𝑏[𝑛] et si 𝑏 ≡ 𝑐[𝑛] alors 𝑎 ≡ 𝑐[𝑛].
On dit que la congruence est transitive.

PROPRIETE 7
Soit 𝑛 ∈ ℕ∗ et 𝑎 et 𝑏 deux entiers relatifs. Si 𝑎 ≡ 𝑏[𝑛] alors :
 𝜆𝑎 ≡ 𝜆𝑏[𝑛] avec 𝜆 ∈ ℤ.
 𝑎 + 𝜆 ≡ 𝑏 + 𝜆[𝑛] avec 𝜆 ∈ ℤ.

REMARQUE : On dit qu’on peut ajouter un même entier aux deux membres d’une même congruence et
qu’on peut multiplier les deux membres d’une même congruence par un même entier.

ATTENTION, on ne peut pas diviser les deux membres d’une même congruence par un
même entier.
CONTRE-EXEMPLE : 18 ≡ 6[3] mais après avoir divisé par 3 , on n’a pas 6 ≡ 2[3].
En effet, 6 = 3 × 2 + 0 donc 6 ≡ 0[3] et = 3 × 0 + 2 donc 2 ≡ 2[3].

PROPRIETE 8
Soit 𝑛 ∈ ℕ∗ et 𝑎, 𝑏, 𝑎 et 𝑑 4 entiers relatifs. Si 𝑎 ≡ 𝑏[𝑛] et si 𝑐 ≡ 𝑑[𝑛] alors :
 𝑎 + 𝑐 ≡ 𝑏 + 𝑑[𝑛] (de même 𝑎 − 𝑐 ≡ 𝑏 − 𝑑[𝑛]).
 𝑎𝑐 ≡ 𝑏𝑑[𝑛].
 ∀𝑝 ∈ ℕ, 𝑎𝑝 ≡ 𝑏 𝑝 [𝑛].

REMARQUE : On dit que l’addition et la multiplication sont compatibles avec les congruences.

PROPRIETE 9
Tout entier relatif 𝑎 est congru à 0,1,2, … , 𝑛 − 1 modulo 𝑛 .

Page 5 sur 6
 DEMONSTRATION :
Dans la division euclidienne de 𝑎 par 𝑛, on sait que 𝑎 peut s‘écrire sous la forme :
𝑎 = 𝑘𝑛 + 0, 𝑎 = 𝑘𝑛 + 1 , 𝑎 = 𝑘𝑛 + 2 , … , 𝑎 = 𝑘𝑛 + (𝑛 − 1) avec 𝑘 ∈ ℤ
⟺ 𝑎 − 0 = 𝑘𝑛, 𝑎 − 1 = 𝑘𝑛, 𝑎 − 2 = 𝑘𝑛, … , 𝑎 − (𝑛 − 1) = 𝑘𝑛 avec 𝑘 ∈ ℤ
⟺ 𝑎 ≡ 0[𝑛], 𝑎 ≡ 1[𝑛], 𝑎 ≡ 2[𝑛], … , 𝑎 ≡ 𝑛 − 1[𝑛]
Donc, tout entier relatif 𝑎 est congru à 0,1,2, … , 𝑛 − 1 modulo 𝑛 .
Par exemple, tout entier relatif est congru à 0,1 ou 2 modulo 3.

3. Applications
a) Résoudre des équations dans à l’aide des congruences
Résoudre dans ℤ les équations suivantes : 𝑥 + 7 ≡ 3[8]; 3𝑥 ≡ 7[8]; 𝑥² ≡ 2[4].
METHODE : Pour résoudre une équation avec des congruences, on applique les
propriétés de la congruence ou on construit le tableau des restes des
congruences et on raisonne par disjonction de cas.

b) Déterminer un reste à l’aide des congruences

(1) Déterminer les restes des divisions euclidiennes de 2342 par 5 et de 2341 par 7.
METHODE : Pour déterminer le reste de la division euclidienne de 𝑎𝑛 par 𝑏, on
effectue la division euclidienne de 𝑎 par 𝑏 puis on essaie de déterminer le
plus petit exposant 𝑝 tel que 𝒂𝒑 ≡ 𝟏[𝒃] . On dit que la suite des restes est
alors périodique de période 𝑝.
On effectue ensuite la division euclidienne de 𝑛 par 𝑝.

(2) Quel est le reste de 𝑎 = 32𝑛+1 + 2𝑛+2 dans la division euclidienne par 7?
METHODE : On transforme l’écriture de l’expression afin d’obtenir une combinaison
de puissances de même exposant.

c) Etudier une divisibilité à l’aide des congruences

(1) Démontrer que l’expression 𝑎 = 𝑛(𝑛2 + 5) est divisible par 3, pour tout 𝑛 ∈ ℕ∗.

(2) Déterminer les entiers 𝑛 pour lesquels 𝑎 est divisible par 7.

METHODE : Pour étudier la divisibilité entre 𝑎 et 𝑏 à l’aide d’une congruence,

on montre que 𝑎 ≡ 0[𝑏] à l’aide du tableau des restes de la congruence.

OBJECTIF : Je dois savoir :

 Déterminer les diviseurs d’un entier ;
 Etablir un test de divisibilité ;
 Résoudre une congruence 𝑎𝑥 ≡ 𝑏[𝑛].

Page 6 sur 6