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 = 1. a prend les valeurs 4, 5, ….  

 

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