Goto English version or use

N premiers Petit Théoreme.

Définition

 

En mathématiques, le petit théorème de Fermat est un résultat de l'arithmétique modulaire, qui peut aussi se démontrer avec les outils de l'arithmétique élémentaire.

 

Il s'énonce comme suit. Si a est un entier non divisible par p tel que p est un nombre premier, alors a p-1 -1 est un multiple de p. Le corollaire de ce théorème est que, pour tout a entier et p nombre premier, alors a p -a est un multiple de p. (voir aussi clef_de_fermat.html#premice_du_petit_theoreme )

 

Il doit son nom à Pierre de Fermat (1601 - 1665) qui l'énonce la première fois le 18 octobre 1640.

Source Wikipédia http://fr.wikipedia.org/wiki/Petit_th%C3%A9or%C3%A8me_de_Fermat

 

Objection sur la définition factorisée:

L'on peut lire la factorisation  de la définition et si l'on divise par n alors

Or , si n est divisible par p cette définition n'est plus vrai : exemple : 10(5-1) -1 n'est pas divisible par 5

Que signifie  ?

 

Si nous divisons n par p le reste de la division est 0

exemple: le reste de 12 / 4 = 0 , sera noté :

 

Rappel de la formule clef de Fermat : formule des Poly-polygonaux

Soit la formule clef de Pierre de Fermat : et que nous développons le numérateur alors nous obtenons un expression du genre  ; (exp signifie exposant )

Notation n! = Factorielle n

au lieu d'écrire 1x2x3x4... n , l'on note n!

Exemple : 1x2x3x4 , se note 4! et est = à 24

par exemple pour =

Si l'on considère que Fermat a développé toutes ses théories (petit et grand théorème) pour toutes les puissances de n, il est bien sur totalement exclus , pour trouver tous les indices (exemple ci-dessus 1,21,175,735,1634,1764,720), que Fermat ai procéder un calcul manuel.Trouver chaque indice est fastidieux (voir le simplificateur d'equation de ce site) ; Néanmoins nous pouvons trouver très facilement la somme de ces indices.

 

Comment trouver la somme des indices?

 

Soit ,nous remplaçons n par 1 (n=1) alors nous obtenons

 

si n=1 alors

 

La somme des indices est égale a la factorielle du dénominateur , par exemple 1+21+175+735+1634+1764+720 = 5040

 

Développement du numérateur:

 

Si nous développons le numérateur alors la somme des termes de l'addition ainsi obtenue sera égale à la factorielle du nombre de facteurs du dénominateur.

soit p le nombre quelconque de facteur de n(n+1)(n+2)...

=

Le PREMIER exposant = le nombre de facteurs (comme pour un tableau de Pascal),  1p

Le PREMIER indice est égal à 1

Le DERNIER indice = factorielle -1 du nombre de facteurs.

 

Exemple : nombre de facteurs = 7

 

<=>

 

Le premier exposant = le nombre de facteurs : 1n7

Le premier indice est égal à 1 1+21+175+735+1624+1764+720=5040

Le dernier indice = factorielle -1 du nombre de facteurs. 1+21+175+735+1624+1764+720=5040,   1 x 2 x 3 x 4 x 5 x 6 =720

 

Remplacement de n par 1

si n = 1

Exemple : nombre de facteurs = 7

si n = 1 alors ,

 

1+21+175+735+1624+1764+720=5040 = 7!

 

Démonstration du petit théorème de Fermat

 

Nombres premiers et factorielle

Si un nombre est premier , c'est à dire divisible par lui même (ou par 1) alors seul le dernier facteur de la factorielle est divisible par ce nombre , par exemple , 7 est premier, alors 7! = 1 x 2 x 3 x 4 x 5 x 6 x 7 seul le dernier facteur : 7 est divisible par 7 , et non pas les autres facteurs : 2,3,4,5,6 (l'on obtient soit un décimal soit un réel)

L'on en déduit aussi que si un nombre est premier alors sa factorielle moins 1 n'est pas divisible par ce nombre., 2 x 3 x 4 x 5 x 6 n'est pas divisible par 7.

 

 

Termes de l'addition et nombres premiers:

 

Soit l'addition  issue du développement d'une factorielle n(n+1)(n+2).... dont le nombre de facteurs, p est premier et où nous remplaçons n par 1 alors : [1+ (a+b+c) ] + [(p-1)!] est divisible par p équivaut aussi à  [1] + [a+b+c]+ [(p-1)!]

 

Regroupement en 2 termes

 

Regroupons le développement de n(n+1)(n+2)....  en 2 termes :

p! =

1 + (a+b+c)

=

(p-1) x (p-1)!

+

  (p-1)!

exemple : 5! = 120

4(1x2x3x4)

+

1x2x3x4

Nous regroupons les premiers termes 1 + a + b+ c ...et l'on ajoute le deuxième terme (p-1)!

 

Exemple: n(n+1)(n+2)(n+3)(n+4) , si n=1 alors 1(1+1)(1+2)(1+3)(1+4) ; total des indices 5! = 120 ,  dernier indice = 4! =24 donc 120 = 96+24

si l'on factorise les deux termes par 24 alors 120 = 24(4+1)

120=4x24 + 1x 24 , le premier terme est égal a 4x4x3x2x1 , le dernier terme 4x3x2x1

 

Celà reste vrai pour un nombre de facteurs premiers ou non

 

Regroupement en 3 termes

P! est une somme de p termes don't le premier est égal à 1 et le troisième est = à (p-1)! , tous les termes intermédiaires étant regroupes en un deuxième terme.

Ce deuxième terme = à p!-1-(p-1)! = p!-(1+(p-1)!)

Dans notre exemple 120 = 1 + [120-(1+24)] + 24 = 1 + 95 + 24

 

n(n+1)...(n+p-1)=n^(p-1)+..(p-1)n ,p est le nombre de facteurs
Remplacement de n par 1 alors 1*2*3... = 1(1+1)(1+2)...
 
Premier terme
+ 2èm
Total
1x2=
1
1





1
2
1x2x3=
1
3
2




2
6
1x2x3x4=
1
6
11
6



6
24
1x2x3x4x5=
1
10
35
50
 


24
120
1x2x3x4x5x6=
1
15
85
225
274
 

120
720
1x2x3x4x5x6x7=
1
21
175
735
1624
1764
 
720
5040
1x2x3x4x5x6x7x8=
1
28
322
1960
6769
13132
13068
5040
 

Nota:le développement de n(n+1)(n+2)(n+3)(n+4) = 1n5+10n4+35n3+50n2+24n

Si p est premier , alors (p-1)! n'est pas divisible par p , 1+ [p!-(1+(p-1)!)] + (p-1)! est divisible par p

Dans l'expression [1] + [p!-(1+(p-1)!] + [(p-1)!] , 0 (mod p) sachant que (p-1)! n'est pas divisible par p alors 1+(p-1)! est divisible par p .

Plus de détails

p! =

(exemple p=5 => 1x2x3x4x5=120)

0 (mod p)

Premier + Deuxième terme

+

dernier terme

(p-1)(p-1)!

exemple : (5-1)(5-1)(5-2)(5-3)(5-4) = 4x4x3x2x1 = 96

4x4x3x2x1 non divisible par 5

+

(p-1)!

4x3x2x1 = 24

4x3x2x1 non divisible par 5

0 (mod p) =

 

0 (mod p)

premier terme = 1

+

+ termes intermédiaires

+

 dernier terme

1

+

p! - 1 - (p-1)! = p! - (1+(p-1)!)

120-1-24= 120 - (25) = 95

+

+ (p-1)!

1

+

p! -

1+(p-1)!

+

+ (p-1)!

0 (mod p)

 

0 (mod p)

= le premier + dernier terme

 

0 (mod p)

p! 0 (mod p) => , [1]+[1+(p-1)!]+[(p-1)!] =

[1+(p-1)!] + [1+(p-1)!]  0 (mod p) , les 2 termes étant égaux alors     

Conclusion

Soit l'expression n(n+1)(n+2)...(n+(p-1)) et p le nombre de facteurs , si l'on remplace n par 1 alors :

Si p est premier , 1+ 1*2*3...(p-1) est divisible par p

 

 

exemple p=7 alors 1+1*2*3*4*5*6 = 721 divisible par 7

Cette formule n'est pas un corollaire du petit théorème mais la formule qui y abouti.

n     0 (mod p ) signifie que le reste de la division de n  par p = 0 

n     0 (mod p ) signifie que le reste de la division de n  par p  est différent de 0

Si vous n'êtes pas familier avec la notation de l'arithmétique modulaire cliquez sur ce lien pour un petit rappel

Remplacement de 1 par n

Le développement de n(n+1)(n+2)...(n+p-1) = [1np]+[anp-1+bnp-2]+[(p-1)!n] donc

 

si 1+(p-1)! 0 (mod p) alors n[1+(p-1)!] 0 (mod p)

n+n(p-1)! 0 (mod p)

et aussi : n+n(p-1)! 0 (mod n)

 

Exemple , dans le dernier terme de  1n5+10n4+35n3+50n2+24n , 24n + n = 25n est divisible par 5 , donc le premier terme - n est divisible par 5 , ce qui revient à ajouter un n au dernier terme de l'addition dun développement de n(n+1)(n+2)... et le retirer au premier terme de l'addition des indices (c'est a dire np )

 

si n+n(p-1)! 0 (mod p) alors np - n 0 (mod p)

 

 Conjecture des nombres premiers en corollaire du petit théorème de Fermat

Rappel : nombres premiers de Mersenne :

si alors est-il premier?

non : ne fonctionne pas par exemple pour 211

 

alors n est premier  si  <=>  

Se lit : si le reste de  2n-2 / n est 0 <=> si le reste de 2n-1-1 /n est 0 : si vous n'ètes pas habitué avec et (mod) voir Arithmétique modulaire sur ce site

En corolaire du petit théorème de Fermat, a=2; si le reste (équivalence informatique: modulo(dividende/diviseur)  ou résidu) de a n-a/a  = 0 alors n est premier (sinon n n'est pas premier) Exemple: le reste de 25-2/5 <=> (32-2)/5 est = à 0

Ce n'est qu'une conjecture car il faut pouvoir le démontrer (*),2 n dépassant vite les capacités de calculs des calculateurs classique...

 

Il est trés important de considerer dans cette conjecture que seule une puissance de 2, sépare bien les nombres entiers en 2 ensembles de  nombres , premiers et non premiers

    

Se lit : si le reste de  2n-2 / n est différent de 0

(*) Le professeur Henry Cohen de l'université de Bordeaux note "On ne peut rien conclure si 2n-1 -1 est divisible par n, mais il est assez probable dans ce cas que n soit premier)

Histoire des nombres Edition Tallandier 2007, paragraphe l'intrigue des nombres premiersI

En effet, cette conjecture semble ne pas étre vrai pour (n< 1000) 341,561,645 !!!:

a p-1 -1 est un multiple de p est une conjecture prouvée en supposant que a/p b/p ce qui n'est pas forcément vrai...

Commentaires

 

 Matrice illustrant cette conjecture (a=2)

le petit théorème de Fermat n'isole pas les nombres non premiers:

 

Exemples :

a=3 n=6 , 6 n'étant pas premier , le reste de 36-3/3 devarit étre <> 0

nb: 3 tout comme 2 est premier...

 

n

36

36-3

 726/6

Reste

6 729 726 121 0

 

pour a=5 , n=10

 

n 510 510 -5 510 -5/5 Reste
10 9765625 9765620 976562 0

 

Il semblerai pour tout n/a = 2 ... CQFD

 

pour a= 4 c'est pire...

n 4n 4n-4 4n-4/4 r
2 16 12 6 0
3 64 60 20 0
4 256 252 63 0
5 1024 1020 204 0
6 4096 4092 682 0
7 16384 16380 2340 0

 

Petit préambule - notes:

 

si l'on veut savoir si un nombre est divisible par un autre de tête il suffit:

 

si il est pair : le diviser par 2

si il est impair: lui ôter une mesure (<- comme l'aurait écrit Fermat....)

 

Cet algorithme est issue d'un traitement binaire simple

 .

n 2n 2n – 2 2n – 2 / n Reste

1

2

0

0

0

2

4

2

1

0

3

8

6

2

0

4

16

14

3 1/2

1/2

5

32

30

6

0

6

64

62

10 1/3

1/3

7

128

126

18

0

8

256

254

31 3/4

3/4

9

512

510

56 2/3

2/3

10

1024

1022

102 1/5

1/5

11

2048

2046

186

0

12

4096

4094

341 1/6

1/6

13

8192

8190

630

0

14

16384

16382

1170 1/7

1/7

15

32768

32766

2184 2/5

2/5

16

65536

65534

4095 7/8

7/8

17

131072

131070

7710

0

18

262144

262142

14563 4/9

4/9

19

524288

524286

27594

0

20

1048576

1048574

52428 5/7

5/7

21

2097152

2097150

99864 2/7

2/7

22

4194304

4194302

190650 1/9

1/9

23

8388608

8388606

364722

0

24

16777216

16777214

699050 4/7

4/7

25

33554432

33554430

1342177 1/5

1/5

26

67108864

67108862

2581110 1/9

1/9

27

134217728

134217726

4971026 8/9

8/9

28

268435456

268435454

9586980 1/2

1/2

29

536870912

536870910

18512790

0

30

1073741824

1073741822

35791394 1/9

1/9

31

2147483648

2147483646

69273666

0

32

4294967296

4294967294

134217727 8/9

8/9

33

8589934592

8589934590

260301048 1/6

1/6

34

17179869184

17179869182

505290270 1/9

1/9

35

34359738368

34359738366

981706810 4/9

4/9

36

68719476736

68719476734

1908874353 5/7

5/7

37

137438953472

137438953470

3714566310

0

Si le reste de l'opération = 0 alors n est premier ... sinon n n'est pas premier

Note IMPORTANTE

si

exemple;

221 est-il divisible par 7?

221-7=214

214/2=107

107-7=100

50/2=27

27-7=20

20/2=10

10/2=5

221 n'est pas divisible par 7

(31*7 reste 4)

91 est t-il divisible par 7?

91-7=84

84/2=42

42/2=21

21-7=14

14-7=7

.

Etude modulaire de cette conjecture

Selon les formules des inverses modulaires (voir Arithmetique modulaire sur ce site ) l'on a: ou .

donc ou

 

Accès direct sur les inverses modulaires et les nombres premiers http://schemath.com/math_mod_inverse_modulaire_5.htm

 

Pour la suite cliquez ci dessous

Conjecture N premiers suite

Autres publications sur le sujet

De dominique Guillaume :

http://hal.inria.fr/inria-00076980                 (publication à l'INRIA)

http://link.springer.com/article/10.1007/BF01195532     (publication chez Springer).

Autres pages du site

L'arithmetica DiophanteNombres polygonauxLa clef de FermatN premiers Petit Théoreme. Arithmétique modulaireCarrés topologiquesBoite A outilsAvis / Contact
Accueil

  

Patrick Stoltz le 18/10/2009 maj 2014

pstoltz@shemath.com