Le petit thÈorËme de Fermat

Retour

HypothËses

Soient

p un nombre premier

et

a un entier naturel non divisible par p

ConsidÈrons les nombres suivants :

1a, 2a, 3a, ... , (p - 1)a

ou encore :

kaÝÝÝÝÝÝÝ (avec 1 £ k £ p - 1)

ka est-il divisible par p ?

Par hypothËse a non divisible par p

0 < k < p ÝÞ Ýk non divisible par p

le produit ka n'est donc pas divisible par p

Ainsi la division euclidienne de ka par p s'Ècrit :

ka = pq + r_kÝÝÝÝÝ avecÝÝÝ 0 < r_k < p

Montrons que les restes r_k sont deux ý deux distincts

On pose

0 < kÝ < pÝÝÝÝ etÝÝÝÝ 0 < k' < pÝÝÝÝ avec k ¼ k'

kaÝ = pqÝ + r_kÝÝÝÝÝÝ (avec 0 < r_kÝ < p)

k'a = pq' + r_k'ÝÝÝÝÝ (avec 0 < r_k' < p)

Raisonnement par l'absurde

kaÝ = pqÝ + r_kÝÝÝÝ ¤ ÝÝÝÝr_kÝ = kaÝ - pq

k'a = pq' + r_k'ÝÝÝÝ ¤ ÝÝÝÝr_k' = k'a - pq'

Supposons que r_k = r_k'

_ÝÝ r_kÝÝÝÝÝÝÝÝÝÝ =Ý r_k'

¤ ÝÝÝÝ kaÝ - pqÝ =Ý k'a - pq'

¤ ÝÝÝÝ a(k - k')Ý =Ý p(q - q')

Ainsi

p divise a(k - k')ÝÝÝÝ OrÝÝÝÝ p ne divise pas a

þ

ThÈorËme de Gauss

þ

p divise (k - k')

De plus

0 < kÝ < pÝÝÝÝ ¤ÝÝÝÝÝÝ 0 <ÝÝ kÝÝÝ < p

0 < k' < pÝÝÝÝ ¤ÝÝÝÝ -p <ÝÝ -k'Ý < 0

ÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝ ÝÝÝÝ ---------------

ÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝ ÝÝÝÝ -p < k - k' < p

D'o˜

p divise (k - k')ÝÝÝÝÝÝÝÝÝ etÝÝÝÝÝÝÝÝÝ -p < k - k' < p

þ

ÝÝÝ k - k' = 0ÝÝÝÝ ¤ ÝÝÝÝk = k'Ý

contradiction

car k ¼ k' par hypothËse

Donc

k ¼ k'ÝÝÝÝ Þ ÝÝÝÝr_k ¼ r_k'

Les restes r_k sont donc deux ý deux distincts

ConsÈquences pour r₁ , r₂ , r₃ , ... , r_{p - 1}

0 < r_k < p

donc

r_k peut prendre (p - 1) valeurs

En divisant les nombres 1a, 2a, 3a, ... , (p - 1)a par p, on effectue (p - 1) divisions dont les restes sont distincts deux ý deux.

Donc

{ r₁ , r₂ , r₃ , ... , r_{p - 1} } =Ý { 1, 2, ... , (p - 1) }

DÈmonstration de petit thÈorËme de Fermat

" k ‘{ 0, 1, ..., (p - 1) } : ka † r_kÝ (mod p)

Ecrivons alors

1aÝÝÝÝÝÝÝÝ † r₁ÝÝÝÝ (mod p)

2aÝÝÝÝÝÝÝÝ † r₂ÝÝÝÝ (mod p)

kaÝÝÝÝÝÝÝÝ † r_kÝÝÝÝ (mod p)

(p - 1)a † r_{p - 1} (mod p)

On peut multiplier membres ý membres les termes de plusieurs congruences donc :

ÝÝÝÝÝÝÝÝÝ 1a ¥ 2a ¥ ... ¥ (p - 1)a † r₁ ¥ r₂ ¥ r₃ ¥ ... ¥ r_{p - 1} (mod p)

¤ÝÝÝÝÝ (p - 1)!a^{p - 1}ÝÝÝÝÝÝÝÝÝÝÝÝÝÝ † r₁ ¥ r₂ ¥ r₃ ¥ ... ¥ r_{p - 1} (mod p)

On a montrÈ que

{ r₁ , r₂ , r₃ , ... , r_{p - 1} } =Ý { 1, 2, ... , (p - 1) }

Donc

r₁ ¥ r₂ ¥ r₃ ¥ ... ¥ r_{p - 1} = 1 ¥ 2 ¥ ... ¥ (p - 1)

ÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝÝ = (p - 1)!

Ainsi

ÝÝÝÝÝÝÝÝÝ (p - 1)!a^{p - 1}ÝÝÝÝÝÝÝÝ † (p - 1)!ÝÝ (mod p)

¤ÝÝÝÝÝ (p - 1)!(a^{p - 1} - 1) † 0ÝÝÝÝÝÝÝÝÝÝÝÝ (mod p)

¤ÝÝÝÝÝ p divise (p - 1)!(a^{p - 1} - 1)

p divise (p - 1)!(a^{p - 1} - 1)Ý OrÝ p ne divise pas (p - 1)!

þ

ThÈorËme de Gauss

þ

p divise (a^{p - 1} - 1)

Ainsi se trouve dÈmontrÈ le petit thÈorËme de Fermat

Le petit thÈorËme de Fermat

p est un nombre premier et a un entier naturel non divisible par p

þ

a^{p - 1} - 1ÝÝÝÝ est divisible par p

Prolongement

Du petit thÈorËme de Fermat on dÈduit aisÈment que :

Prolongement du petit thÈorËme de Fermat

p est un nombre premier et n un entier nature quelconque

þ

n^p - nÝÝÝÝ est divisible par p

Retour