4ème

Divisibilit dans ℤ

I - Diviseurs et multiples d entiers

Définition

Soit a ∈ ℤ et b ∈ ℤ∗
On dit que b est un diviseur de a ou que a est divisible par b, s’il existe q ∈ ℤ tel que
a = bq

Vocabulaire
Si un entier a est divisible par un entier non nul b, on dit que a est un multiple de b

Conséquence

Soit a ∈ ℤ et b ∈ ℤ∗
• Si b divise a alors −b divise a
• Les multiples de b sont les éléments de l’ensemble bℤ = {bq , q ∈ ℤ}

Propriétés

Soit (a; b) ∈ ℤ∗ × ℤ∗ et c ∈ ℤ
• Si a divise b et b divise a alors a = b ou a = −b
• Si a divise b et b divise c alors a divise c
• Si a divise b et a divise c alors a divise αb + β c pour tous entiers α et β

Démonstration
• a divise b ⇒ il existe q ∈ ℤ tel que b = qa
b divise a ⇒ il existe q ' ∈ ℤ tel que a = q ' b
Donc a = qq 'a ⇒ qq ' = 1 ⇒ q = q ' = 1 ou q = q ' = −1 alors a = b ou a = −b
• a divise b ⇒ il existe q ∈ ℤ tel que b = qa
b divise c ⇒ il existe p ∈ ℤ tel que c = pb
Alors c = pqa = p'a où p' = pq ∈ ℤ donc a divise c
• a divise b ⇒ il existe q ∈ ℤ tel que b = qa
a divise c ⇒ il existe n ∈ ℤ tel que c = na
Donc ∀α ∈ ℤ , β ∈ ℤ , αb + βc = αqa + β na = a(αq + β n) = an ' où n ' = (αq + β n) ∈ ℤ
Alors a divise αb + β c
II - Division euclidienne dans ℤ
Définition (Rappel)

Pour tout réel x, il existe et unique entier n tel que n ≤ x < n + 1 .Cet entier est appelé
partie entière de x, elle est notée E(x)

1
Définition

Soit (a; b) ∈ ℤ × ℤ∗
On appelle quotient de a par b l’entier q défini de la manière suivante :
a
• q est le plus grand entier inférieur ou égal à si b > 0
b
a
• q est le plus petit entier sup érieur ou égal à si b < 0
b

Exemples
Le quotient de 5 par 4 est égal à 1
Le quotient de 5 par −4 est égal à −1
Le quotient de −5 par 4 est égal à −2
Le quotient de −5 par −4 est égal à 2
Définition

Soit a ∈ ℤ , b ∈ ℤ∗
On appelle reste de a par b l’entier r tel que r = a − bq, où q est le quotient de a par b

Théorème

∀ a ∈ ℤ , b ∈ ℤ∗ il existe un unique couple d’entiers (q; r) tel que a = bq + r et 0 ≤ r < b

Démonstration
Pour l’existante, il suffit de prendre le quotient de a par b et le reste de a par b
Prouvons l’unicité
Supposons qu’il existe deux couples d’entiers (q; r) et (q ', r ') tels que
a = bq + r et 0 ≤ r < b et a = bq '+ r ' et 0 ≤ r ' < b
Il en résulte que b(q − q ') = r '− r ⇒ b q − q ' = r − r ' < b
Par suite b q − q ' = 0 ⇒ q = q ' et r = r '
Vocabulaire
L’écriture a = bq + r et 0 ≤ r < b s’appelle division euclidienne de a par b, q est le quotient
de a par b et r est le reste de a par b
Conséquence

Le reste de tout entier a dans la division euclidienne par un entier non nul b est un
élément de l’ensemble {0;1;2......; b − 1}

III Congruence modulo n

Définition et notation

Soit (a; b) ∈ ℤ 2 et n ∈ ℕ∗
On dit que a est congru à b modulo n (ou a et b sont congrus modulo n) si a − b est un
multiple de n .On note alors a ≡ b(mod n)

2
Théorème et définition
Soit n ∈ ℕ∗
∀ a ∈ ℤ il existe un unique entier r ∈ {0;1;2...; n − 1} tel que a ≡ r(mod n)
On dit que r est le reste modulo n de a

Conséquence

Soit n ∈ ℕ∗
Deux entiers sont congrus modulo n, si et seulement si, ils ont le même reste modulo n

Démonstration
Soit a = nq + r et b = nq + r ' où 0 ≤ r < n et 0 ≤ r ' < n
Si r = r ' alors a − b = n(q − q ') ⇒ n divise a − b ⇒ a ≡ b(mod n)
Réciproquement :
a ≡ b(mod n) ⇒ il existe k ∈ ℤ tel que a − b = nk
Donc r − r ' = a − nq − b + nq ' = a − b − n(q − q ') = nk − n(q − q ') = n(k − q + q ')
⇒ n divise r − r ' et puisque 0 ≤ r < n et 0 ≤ r ' < n alors r − r ' < 0 ⇒ r − r ' = 0 ⇒ r = r '
Propriétés
Soit a, b et c trois entiers et n un entier naturel non nul
• a ≡ a(mod n)
• Si a ≡ b(mod n) alors b ≡ a(mod n)
• Si a ≡ b(mod n) et b ≡ c(mod n) alors a ≡ c(mod n)

Démonstration
La preuve des deux premières propriétés est évidente
Dire que a ≡ b(mod n) et b ≡ c(mod n) ⇒ n divise a − b et n divise b − c
⇒ n divise a − b + b − c ⇒ n divise a − c ⇒ a ≡ c(mod n)
Propriétés

Soit a, b, c et d quatre entiers et n un entier naturel non nul

• Si a ≡ b(mod n) et c ≡ d(mod n) alors a + c ≡ b + d(mod n) et a × c ≡ b × d(mod n)
• Si a ≡ b(mod n) alors ∀ h ∈ ℤ, ha ≡ hb(mod n) et ∀ p ∈ ℕ∗ ,a p ≡ bp (mod n)

Démonstration
Soit a, b, c et d quatre entiers et n un entier naturel non nul
• Si a ≡ b(mod n) et c ≡ d(mod n) alors n divise a − b et n divise c − d
⇒ n divise (a − b) + (c − d) = (a + c) − (b + d) ⇒ a + c ≡ b + d(mod n)
De même : si a ≡ b(mod n) et c ≡ d(mod n) alors n divise a − b et n divise c − d
⇒ n divise (a − b)c + (c − d)b ⇒ n divise ac − bd ⇒ ac ≡ bd(mod n)
• Si a ≡ b(mod n) ⇒ n divise a − b ⇒ n divise h(a − b) ⇒ n divise ha − hb ⇒ ha ≡ hb(mod n)
p −1 p −1
•∀p ∈ ℕ∗ a p − bp = (a − b) ∑ a p−1− k b k = (a − b)α où α = ∑ a p−1− k b k , α ∈ ℤ
k =0 k =0

Donc a ≡ b(mod n) ⇒ n divise a − b ⇒ n divise (a − b)α ⇒ n divise a p − bp ⇒ a p ≡ bp (mod n)

Exercice :
Montrer que pour tous entiers naturels n, p et q ,4 n + 4 p + 4 q ≡ 0 (mod 3)

3
IV-Th or me de Fermat
Activité
Soit p un nombre premier
1) Montrer que p divise Ckp , pour tout k ∈ {1;2......; p − 1}
2) En déduire que pour tout entier naturel n, p divise (n + 1)p − (n p + 1)
3) Montrer par récurrence que ∀n ∈ ℕ , n p ≡ n (mod p)
4) En déduire que ∀n ∈ ℕ tel que n ∧ p = 1 , n p−1 ≡ 1(mod p)
5) Montrer que ∀a ∈ ℤ , a p ≡ a (mod p) et que si a ∧ p = 1 , a p−1 ≡ 1(mod p)
Réponse :
Soit p un nombre premier
1) Montrons que p divise Ckp , pour tout k ∈ {1;2......; p − 1}
p(p − 1)(p − 2)...(p − k + 1)
On a : Ckp = ⇒ k!Cpk = p(p − 1)...(p − k + 1) donc p divise k!Ckp et
k!
puisque k < p alors p ne divise aucun des entiers k;(k − 1),(k − 2),....,1 ⇒ p ne divise pas k!
donc p divise Cpk
2) Déduisons que pour tout entier naturel n, p divise (n + 1)p − (n p + 1)
p p−1 p−1
On a : (n + 1)p = ∑ Cpk n k = n p + 1 +∑ Cpk n k donc (n + 1)p − (n p + 1) = ∑ Cpk n k
k =0 k =1 k =1
p−1
Et puisque p divise Cpk , pour tout k ∈ {1;2......; p − 1} alors p divise ∑C k
p nk
k =1
p p
Donc p divise (n + 1) − (n + 1)
3) Montrons par récurrence que ∀n ∈ ℕ , n p ≡ n (mod p)
∗ Pour n = 0 , 0p ≡ 0(mod p)
∗ Soit n ∈ ℕ , Supposons que n p ≡ n (mod p) et montrons que (n + 1)p ≡ n + 1(mod p)
∗ On a par hypothèse n p ≡ n (mod p) ⇒ n p + 1 ≡ n + 1(mod p)
Et puisque p divise (n + 1) p − (n p + 1) alors (n + 1)p ≡ n p + 1(mod p)
Donc (n + 1)p ≡ n + 1(mod p)
Conclusion : ∀n ∈ ℕ , n p ≡ n (mod p)
4) Montrons que si n ∧ p = 1 alors n p−1 ≡ 1(mod p) , ∀n ∈ ℕ
p p p−1
On a : n ≡ n (mod p) ⇒ p divise n − n = n(n − 1) et puis que n ∧ p = 1 alors
p−1 p−1
p divise n −1 ⇒ n ≡ 1(mod p)
5) Montrons que ∀a ∈ ℤ , a p ≡ a (mod p) et que si a ∧ p = 1 , a p−1 ≡ 1(mod p)
∗ Le cas où a ∈ ℕ est déjà démontré
∗ Si a ∈ ℤ∗− alors (−a) ∈ ℕ ∗ donc :
Si p = 2 on a : a 2 − a = a(a − 1) ⇒ 2 divise a 2 − a car a(a − 1) est pair
Si p > 2 alors p est impair .Donc d’après ce qui précède (−a)p ≡ −a(mod p) car (−a) ∈ ℕ
⇒ −a p ≡ −a(mod p) ⇒ a p ≡ a(mod p)
Par suite ∀a ∈ ℤ , a p ≡ a (mod p)

a p ≡ a(mod)p p divise a p − a p divise a(a p−1 − 1) p−1

En plus si :  ⇒ ⇒  ⇒ p divise a − 1
a∧p =1 
 a∧p =1 
 a ∧ p = 1 

⇒ a p−1 ≡ 1(mod p)
4
Propriété
Soit p un nombre premier
Pour tout a ∈ ℤ , a p ≡ a(mod p)

Théorème de Fermat

Pour tout a ∈ ℤ et tout nombre premier p tel que a ∧ p = 1, a p−1 ≡ 1(mod p)