Le petit théorème de Fermat.
La
démonstration qui va suivre ne fait pas appel à la notion de congruence. Elle
est donc destinée plus particulièrement aux personnes peu ou pas familiarisées
avec cette notion.
Enoncé du théorème : Si p est un nombre premier et a un entier positif, alors
ap – a
est divisible par p.
On considère d’abord le nombre de combinaisons noté Cpt .
Cpt est le nombre des sous-ensembles comptant t éléments, ceux-ci étant pris dans un ensemble comptant lui-même p éléments. Cpt est donc le nombre des combinaisons de p éléments pris t à t. t peut prendre chacune des valeurs 0, 1, 2, …, p.
Exemple : Il y a 3 sous-ensembles à 2 éléments, ceux-ci étant pris dans un ensemble à 3 éléments.
Ensemble à 3 éléments : {A ; B, C}
Sous-ensembles à 2 éléments [3 éléments pris 2 à 2] : {A, B}, {AC}, {B, C}.
Donc : C32 = 3.
Une des formules permettant le calcul de Cpt est :
Pour 0 < t < p :
Cpt = p/1 ·
p-1/2 · p-2/3 ·
… p-t+1/t
Pour t = 0 et t = p
Cp0 = Cpp = 1
Des simplifications apparaissent dans le calcul pour le cas 0 < t < p car, entre les nombres figurant aux numérateurs et ceux figurant aux dénominateurs des fractions, il y a des facteurs communs.
Exemple : C63 = 6/1 · 5/2 · 4/3 = 20.
Dans cet exemple, 6 (numérateur de la 1ère fraction) est divisible par 2 (dénominateur de la 2e fraction) et par 3 (dénominateur de la 3e fraction).On a donc C63 = 1/1 · 5/1 · 4/1 = 20.
Si p est un nombre premier, il n’est divisible par aucun des nombres figurant aux dénominateurs des fractions, tous < p. Il en résulte que Cpt est, dans ce cas, divisible par p pour toutes les valeurs de t, sauf 0 et p.
Exemple pour p = 7 (7 est un nombre premier) :
C71
= 7/1 = 7
C72 = 7/1 ·
6/2 = 7 · 3 = 21
C73
= 7/1 · 6/2
· 5/3
= 5·7 = 35
C74 = 7/1 ·
6/2 ·
5/3 ·
4/4 = 7
· 5 = 35
C75
= 7/1 · 6/2
· 5/3
· 4/4
· 3/5
= 7 · 3 = 21
C76 = 7/1 ·
6/2 ·
5/3 ·
4/4 ·
3/5 ·
2/6 = 7
Note : On remarque dans cet exemple que Cpp-t = Cpt . Cela est le cas de façon générale.
Les nombres de combinaisons Cpt apparaissent dans la formule du binôme de Newton qui est la suivante :
(x + y)p = Cp0
xp + Cp1 xp-1 y + Cp2
xp-2 y2 + … + Cpp
yp
Exemple pour x = 3, y = 2 et p = 4 :
(x + y)4 = C40 x4
+ C41 x3 y + C42 x2
y2 + C43
x y3 + C44
y4
(3 + 2)4 = 1 · 34 + 4 · 33
· 2 + 6 ·32 · 22 + 4 · 3 · 23 + 1 ·
24
54 = 1 · 81 + 4 · 27 · 2 + 6 · 9 · 4 + 4
· 3 · 8 + 1· 16 = 81 + 216 + 216 + 96 + 16 = 625
Reprenons la formule du binôme de Newton en posant que p est un nombre premier et que a = x + y, x = 1 et y = 1. Il vient, compte tenu que, pour tout t, 1t = 1, et que Cp0 = Cpp = 1, que Cpt est divisible par p pour 0 < t < p :
ap
= 2p = (1 + 1)p = 1 + Cp1 + Cp2
+ … + Cpp-1 + 1
En posant : Cp1 + Cp2 +
… + Cpp-1 = p · M2 , on obtient
2p = 2 + p · M2
soit 2p - 2
= p · M2
2p
– 2 est donc divisible par
p.
Reprenons encore la formule du binôme de Newton en posant cette fois x = 2, y = 1 et toujours que p est un nombre premier. Il vient :
3p
= (2 + 1)p = 2p + Cp1 2p-1
+ Cp2 2p-2 + … + Cpp-1
2+ 1
En remplaçant 2p par 2 + p · M2 et en posant Cp1 2p-1 + Cp2 2p-2 + … + Cpp-1 2 = p · M3
Il vient :
3p = 3 + M2p + M3p soit
3p - 3 = p · (M2 + M3)
3p
– 3 est donc divisible par
p.
On peut
continuer avec x = 3, 4, …. ;
y restant =
Exemple pour p = 5 :
(1 + 1)5 = 25 = 32 =
= 1 + 5 · 14 ·11 + 10· 13 ·12 + 10· 12 ·13 + 5· 11 ·14 + 1 =
= 1 + 5 + 10 + 10 + 5 + 1 =
= 2 + 6 · 5
25- 2 =
32 - 2 = 30 = 6·
5 divisible par 5
M2 = 6
(2 + 1)5 = 35 = 243 =
= 25 + 5 · 24 ·11 + 10· 23 ·12 + 10· 22 ·13 + 5· 21 ·14 + 1 =
= 2 + 6 · 5 + 80 + 80 + 40 + 10 + 1 = 243
= 3 + 48 · 5
35- 3 = 243 - 3 = 240 = 48· 5 divisible par 5 M3 = 42
M2 + M3 = 48
(3 + 1)5 = 45 = 1’024 =
= 35 + 5 · 34·11 + 10· 33 ·12 + 10· 32 ·13 + 5· 31 ·14 + 1 =
= 3+ 48· 5 + 405 + 270 + 90 + 15 + 1 = 1’024
= 4 + 204 · 5
45- 4 = 1’024 - 4 = 1’020 = 204· 5 divisible par 5 M4 = 156
M2 + M3 + M4 = 204
On établit ainsi par récurrence la validité générale que, pour tout entier positif a, ap – a est divisible par p si p est un nombre premier (Enoncé du petit théorème de Fermat).
Corollaire :
En divisant par a, on peut tirer de « ap – a divisible par p » que ap-1 – 1 est aussi divisible par p. Mais cette dernière expression cesse d’être vraie si a est un multiple de p. Dans ce cas en effet ap-1 est divisible par p et ap-1 – 1 ne l’est évidemment pas.
Exemple pour
p = 3
Posons a = 6, 6 = 2 · 3 est un multiple de p.
Il vient 63 – 6 = 216 – 6 = 210 = 70 · 3, 63 – 6 est divisible par 3
Mais 62 – 1 = 36 – 1 = 35, 62 – 1 n’est pas divisible par 3
Posons a = 7, 7 n’est pas un multiple de p.
Il vient 73 – 7 = 343 – 7 = 336 = 112 · 3, 73 – 7 est divisible par 3
Et 72 – 1 = 49 – 1 = 48 = 16 · 3, 72 – 1 est divisible par 3.
Réciproque :
Si p n’est pas un nombre premier, ap – a peut être ou ne pas être divisible par p.
Exemples :
Posons p = 4, nombre non premier
34 – 3 = 78 non divisible par 4.
54 – 5 = 620 = 155 · 4 divisible par 4
Posons p = 6 nombre non premier
26 – 2 = 62 non divisible par 6.
36 – 3 = 726 = 121 · 6 divisible par 6
Posons p = 8 nombre non premier
58 – 5 = 390’620 non divisible par 8
98 – 9 = 43'046’712 = 5'380'839 · 8 divisible par 8.
Retour à l'article principal Le petit
théorème de Fermat se trouvant
sur Wikipédia