NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 02/07/2014

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                               

     

Théorie des Nombres

 

Débutants

Général

Le petit théorème

de Fermat

 

Glossaire

Général

 

 

INDEX

 

Théorie des nombres

Découverte

Exploration

Démonstration

Généralisation

Applications

Puissances

Avec Pascal

 

Sommaire de cette page

>>> Magie du théorème

>>> Approche

>>> Modulo et résidus

>>> Puissance 3 

>>> Puissance 4

>>> Puissance 5

>>> Puissance 7

 

 

>>> Notation finale

>>> Formulation classique

>>> Exemples de calculs

>>> Historique

>>> Anglais

 

 

 

 

PETIT THÉORÈME DE FERMAT

 

Nous allons approcher par l'expérience (et amusement) le Petit Théorème de Fermat (PTF) relatif à la divisibilité des nombres.

 

L'expérience est relativement simple et très amusante. Instructive de surcroît ! Laissez-vous prendre par la main… Vous aurez la satisfaction de comprendre un point important de la théorie des nombres.

 

Pour ceux qui ont des notions sur le modulo, vous pouvez allez directement voir Modulo et Fermat.

Impatient ! Tout de suite, donnez-moi la formulation du théorème.

 

 

C'est ce genre de découverte qui fait bouillir les sangs d'un mathématicien.

Marcus du Sautoy – La symphonie des nombres premiers

Voir Pensées & humour

 

 

 

La magie du théorème en un coup d'œil

 

Principe

p étant un nombre premier:

 

 

Un nombre et sa puissance p,

divisés par p

donnent le même reste.

 

 

Exemple

Trouvez le reste de la division de 87 par 7:

 

 

Il suffit de donner le reste de

la division de 8 par 7, soit 1.

En effet 87 = 2 097152 = 299 593 x 7 + 1

 

Comme souvent en maths, l'idée est de trouver des routes

plus simples, moins fastidieuses.

Ici on remplace la voie du bas, difficile à calculer,

par celle du haut qui donne un résultat immédiat.

 

Voir Magie

 

Exemples de divisibilités

 

Toutes ces configurations en puissance 3 sont divisibles par 3 (petit théorème de Fermat) et certaines aussi par le nombre (bleu). Les exclus sont les multiples de 3 (lignes de couleur bleu clair).

 

Voir Divisibilité

 

 

 

 

Approche

 

 D'abord 

 

*      Observons le tableau suivant qui donne la puissance 7 des nombres a de 1 à 6
et, également, le reste de leur division par 7 lui-même

 

a

a 7

a 7 / 7

Reste

1

1

0

1

2

128

18

2

3

2 187

312

3

4

16 384

2 340

4

5

78 125

11 160

5

6

279 936

39 990

6

 

Extraordinaire !

 

*     Le reste est égal au nombre de départ.

 

C'est le constat que Fermat a dû faire.

Mais d'une curiosité, il en a tiré un théorème.

Ce pourrait être du style:

Divisé par p, un nombre et sa puissance p donnent le même reste.

 

 

 

 

MODULO ET RÉSIDUS

Modulo m

Je divise par m et

ne m'intéresse qu'au reste.

15 mod 12 = 3

 

Pensez à 15 heures modulo 12  3 heures.

Résidu b

Le reste b de cette division.

3 est le reste ou résidu.

Voir explications complètes en Modulo 

 

 

 

PUISSANCE jusqu'à 3 modulo 3

 

Procédons par étapes

 

*     Nombres à la puissance 3.

*     On veut obtenir les résidus, et en dégager les propriétés.

  

Étape 1 - Exploration de la puissance des nombres jusqu'à n = 3

 

*     Calculons la puissance p de 1 à 3

de tous     les nombres a de 1 à 3.

  

m = 3

a =1

a =2

a =3

n = 1

11 = 1

21 = 2

31 = 3

n = 2

12 = 1

22 = 4

32 = 9

n = 3

13 = 1

23 = 8

33 = 27

 

 

Étape 2 - Résidus en modulo 3

 

*     Calculons les restes de la division par 3 de chacun des nombres du tableau.
Soit " les résidus de  N = a p modulo m avec m = 3 ".

 

m = 3

a = 1

a = 2

a = 3

n = 1

11 mod 3 = 1

21 mod 3 = 2

31 mod 3 = 0

n = 2

12 mod 3 = 1

22 mod 3 = 1

32 mod 3 = 0

n = 3

13 mod 3 = 1

23 mod 3 = 2

33 mod 3 = 0

 

*     C'est le même tableau que précédemment, mais en y reportant que les restes de la division par m = 3.

*    On va éliminer tout de suite la colonne triviale qui donne un reste évident de zéro, car a = m.

 

 

Étape 3 – Divisibilité

 

*     On va écrire ces résultats autrement.
Du nombre de départ, on soustrait son reste dans la division par 3.
Évidemment, le reste de la division par 3 du nouveau nombre devient nul!

 

En effet

4 / 3 donne un reste de 1, et, en retranchant le reste.

(4 – 1) / 3 donne un reste de 0.

 

Voici le tableau avec ce nouveau look

m = 3

a = 1

a = 2

n = 1

(11 – 1) mod 3 = 0

(21 – 2) mod 3 = 0

n = 2

(12 – 1) mod 3 = 0

(22 – 1) mod 3 = 0

n = 3

(13 – 1) mod 3 = 0

(23 – 2) mod 3 = 0

  

Étape 4 - Simplification de l'écriture

 

*     Le modulo m = 3 est sous-entendu: il est rappelé en rouge dans le coin du tableau

 

m = 3

a = 1

a = 2

n = 1

11 – 1

21 – 2

n = 2

121

221

n = 3

131

232

 

*     Rappel de notre notation: tous les nombres internes au tableau sont divisibles par 3.

*     Notons tout de suite les chiffres en rouge dans le cœur du tableau:

en puissance n = 2, on a toujours 1

en puissance n = 3, on a des chiffres qui tous valent a

 

Étape 5 – Propriétés

 

*     La ligne 1, de la puissance n = 1, est triviale : un nombre à la puissance 1 redonne le nombre. La différence est nulle.

*     La ligne 3, de la puissance n = m, redonne les nombres du départ: on dit qu'alors le " tableau est complètement reconstitué ". Nous verrons que cette propriété peut, parfois, apparaître plutôt sur une ligne.

*     La ligne 2, de la puissance n = m – 1, donne un résidu égal à 1.

 

 

Étape 6 – Expressions littérales

 

*     On remplace les chiffres par les lettres: n = 3, devient n = m

 

m = 3

a = 1

a = 2

On lit:

n = 1

11 – 1

21 – 2

 

n = m – 1

am–11

am–11

(am–11) mod m = 0

Un nombre a, à la puissance m–1 diminué de 1, est divisible par m.

n = m

ama

ama

(am   a) mod m = 0

Un nombre a, à la puissance m diminué de a, est divisible par m.

Vrai dans cet exemple! Est-ce toujours vrai? C'est ce que nous allons voir.

 

*     Remarquons toujours nos chiffres en rouge:

en n = m – 1 , on a 1.

en n = m, on a des chiffres qui valent a.  

*     En jaune, on rappelle la lecture du tableau avec le modulo.

 

 

Étape 7 - Théorème ? On peut déjà imaginer des propriétés générales.

 

 Avec diverses formulations équivalentes

an – a  divisé par m

donne 0 comme reste.

an – a  est un multiple de m.

Tout nombre a à la puissance m

divisé par m donne un reste a 

an / m donne a comme reste

an º a mod m

  

*     Mais attention à ne pas généraliser trop vite !!!

Nous allons voir que ça n'est pas complètement exact.

 

 

Étape 8 – Nous avons vu le cas de m = 3, voyons le même tableau avec m = 4 …

 

 

 

PUISSANCE jusqu'à 4 modulo 4

 

Tableau avec m = 4

 

m = 4

a =1

a =2

a =3

n = 1

11 – 1

21 – 2

31 – 3

n = 2

12 – 1

22 – 0

32 – 1

n = 3

13 – 1

23 – 0

33 – 3

n = 4

14 – 1

240

341

 

*     On rappelle la lecture du tableau:

Tous les nombres internes au tableau sont divisible par 4 (= 0 mod 4)..

Exemple: 32 – 1  = 9 – 1 = 8 et 8 est divisible par 4. 

 

Expressions littérales

 

m = 4

a = 1

a = 2

a = 3

n = 1

a1 – 1

a1 – 2

a1 – 3

n = 2

a2 – 1

a2 – 0

a2 – 1

n = 3 = m –1

am–1 – 1

am–1 – 0

am–1 – 3

n = 4 =  m

am – 1

am0

am1

  

Propriétés

 

*    Avec un nombre non premier comme m = 4, nos belles propriétés ne semblent pas se reproduire. La colonne 2 donne 0 (sauf première ligne).

*    La ligne n = m ne donne pas la belle liste des résidus égaux au nombre de départ a.

*    Les lignes 2 et 4 (puissances 2 et 4) sont identiques.

*    Il semble que 2, qui divise 4, entraîne la formation de sous tableaux.

 

Conclusion

*    Notre tentative de théorème ne semble par marcher avec un nombre composé, c'est-à-dire non premier.

 

Continuons notre exploration avec m = 5, qui est premier comme 3

*    Allons-nous retrouver les mêmes propriétés intéressantes que celles obtenues avec 3?

 

 

 

PUISSANCE jusqu'à 5 modulo 5

 

Tableau avec m = 5, ou plutôt p = 5, pour bien témoigner du fait que 5 est premier

 

p = 5

a = 1

a = 2

a = 3

a = 4

n = 1

11 – 1

21 – 2

31 – 3

41 – 4

n = 2

12 – 1

22 – 4

32 – 4

42 – 1

n = 3

13 – 1

23 – 3

33 – 2

43 – 4

n = 4

141

241

341

441

n = 5

151

252

353

454

 

*     Ouais ! ! !  Ça marche, nous retrouvons nos singularités sur les deux dernières lignes. L'effet nombre premier!

 

 

Expressions littérales

 

p = 5

a = 1

a = 2

a = 3

a = 4

n = 1

a1a

a1a

a1a

a1a

n = 2

a2 – 1

a2 – 4

a2 – 4

a2 – 1

n = 3

a3 – 1

a3 – 3

a3 – 2

a3a

n = 4 = p –1

ap–11

ap–11

ap–11

ap–11

n = 5 = p

apa

apa

apa

apa

  

Propriétés

 

*     On retrouve la ligne n = 5 = p qui semble donner une propriété générale

un nombre à la puissance p moins ce nombre est divisible par p.

 

a p – a est divisible par p

pour tout p premier.

 

*     C'est le petit théorème de Fermat qui pointe son nez !

 

*     La ligne n = 4 = p – 1 aussi, semble nous montrer une propriété:

 

a p–1 – 1  est divisible par p

pour tout p premier et pour tout a premier avec p.

 

*     Les deux formulations sont proches. Normal ! La seconde est la première dans laquelle on divise tout par a.

 

En effet, en effectuant la division

Or, le petit théorème de Fermat dit.

(a pa) / a = a p–1 – 1

(a pa)      = k.p

D'une manière générale

p est premier et

ne peut être divisé par a

C'est le facteur k qui l'est.

 

a p–1 – 1 = k.p / a

a p–1 – 1 = k/a . p

a p–1 – 1 = k' . p

Sauf, si a est un multiple de p

Alors c'est p qui est divisible par p

(k peut l'être aussi, mais on n'en sait rien)

Dans ce cas pas de conclusion possible.

a = h . p

 

a p–1 – 1 = k . p / (h.p)

a p–1 – 1 = k . h

D'où la divisibilité par p

pour tout a premier avec p.

 

a p–1 – 1 divisible par p

 

 

 

 

 

PUISSANCE jusqu'à 7 modulo 7

 

Tableau avec p = 7

 

*     Testons une dernière fois avec le nombre premier suivant

 

p = 7

a = 1

a = 2

a = 3

a = 4

a = 5

a = 6

n = 1

11 – 1

21 – 2

31 – 3

41 – 4

51 – 5

61 – 6

n = 2

12 – 1

22 – 4

32 – 2

42 – 2

52 – 4

62 – 1

n = 3

13 – 1

23 – 1

33 – 6

43 – 1

53 – 6

63 – 6

n = 4

14 – 1

24 – 2

34 – 4

44 – 4

54 – 2

64 – 1

n = 5

15 – 1

25 – 4

35 – 5

45 – 2

55 – 3

65 – 6

n = 6

161

261

361

461

561

661

n = 7

171

272

373

474

575

676

 

*     On retrouve bien nos propriétés sur les deux dernières lignes, routine, maintenant !

 

Symboles

 

p = 7

a = 1

a = 2

a = 3

a = 4

a = 5

a = 6

n = 1

a11

 

 

 

 

 

n = 2

 

 

 

 

 

a21

n = 3

 

a 31

 

a 31

 

 

n = 4

 

 

 

 

 

 

n = 5

 

 

 

 

 

 

n = 6 = p –1

ap–11

ap–11

ap–11

ap–11

ap–11

ap–11

n = 7 = p

apa

apa

apa

apa

apa

apa

  

 

 

Remarque

*    Pour chaque ligne, on a noté (cas bleue) la première apparition d'un résidu égal à 1. Alors n = 1, 2, 3 ou 6, tous les diviseurs de p – 1 = 6.

*    Ces exposants (1, 2, 3 et 6) sont les gaussiens de Z7

Le pourquoi de ce nom de baptême Z7, sera vu ultérieurement.

Notation simplifiée

*     Une fois bien familier à cette manière de présenter, on peut encore simplifier l'écriture:

On élimine la ligne 1 (puissance 1), et on ne note plus que les résidus.

 

 p = 7

1

2

3

4

5

6

Puissance 2

1

4

2

2

4

1

Puissance 3

1

1

6

1

6

6

Puissance 4

1

2

4

4

2

1

Puissance 5

1

4

5

2

3

6

Puissance 6

1

1

1

1

1

1

Puissance 7

1

2

3

4

5

6

 

*    Ces deux dernières lignes témoignent du petit théorème de Fermat.
 

 

 

 

FORMULATION CLASSIQUE

 

Formulations classiques (à retenir) du petit théorème de Fermat

 

Si p est un nombre premier,

alors divisé par p,

un nombre et sa puissance p

donne le même reste.

ap    a mod p

43 =  64 = 3 x 21 + 1

4 =            3 x   1 + 1

Si en plus, a et p sont étrangers,

la puissance p – 1 de ce nombre

divisée par p donne 1 pour reste.

ap–1  1 mod p

avec (a,p) = 1

42 =  16 = 3 x 5 + 1

 

(a,p) = PGCD et (a,p) = 1 indiquent que a et b sont étrangers (premiers entre eux)

 

 

Autres formulations

 

ap  a mod p

ap est congru à a modulo p.

 

ap – a  0 mod p

ap – a est congru à 0 modulo p.

 

ap – a divisé par p

donne 0 comme reste.

 

ap – a est un multiple de p.

 

ap / p donne

un multiple de  a comme reste.

ap – 1 – 1  0 mod p si (a,b) = 1

 

ap – 1        1 mod p si (a,b) = 1

ap – 1  est congru à 1 mod p si a et b sont étrangers.   

 

Quelques exemples pour bien se remettre en tête cette extraordinaire propriété:

22 – 1 = 0 mod 3

32 – 1  0 mod 3

42 – 1 = 0 mod 3

52 – 1 = 0 mod 3

62 – 1  0 mod 3

 

Tous les carrés sont de la forme 3k + 1 sauf pour les nombres divisibles par 3.

 

 

 

Exemples de calculs

 

*    Calculer le reste de la division par 37 de 252.

*    On extrait d'abord 37 de 52; reste 16. Le nombre 37 est premier et le petit théorème de Fermat (PTF) s'applique: 237 – 1  = 236 divisé par 37 donne 1 pour reste. Pour le second terme (216), son reste est obtenu par simple calcul ordinaire.


 

 

*    Calculer le reste de la division par 37 de 270.

 

Voir Calculs du même style

 

 

 

HISTORIQUE

 

*           En 1640, Fermat adresse une lettre à son ami Bernard Frenicle de Bessy et lui indique qu'il détient la preuve de ce théorème.

*           La démonstration est un peu longue et il promet de la lui envoyer plus tard. Ce qu'il ne fit pas.

*           En 1736, c'est Euler qui fournira la démonstration.

*           Il se permet de généraliser le petit théorème au nombre N produit de deux nombres premiers.

 

 

 

ENGLISH CORNER

 

Fermat's Little Theorem:

 

*    Let p be a prime and a any integer,
              then ap = a (mod p).

*    Let p be a prime which does not divide the integer a,
              then ap – 1 = 1 (mod p).

 

 

 

 

 

Suite

Le petit théorème de Fermat

*    Cas où a  = 2

*    Découverte

*    Exploration

*    Démonstration classique

*    Démonstration avec le triangle de Pascal

*    Application à la factorisation

*    Les puissances de 7 modulo 11

Voir

*    Nombre pseudo-premier

*    Test de primalité

*    Divisibilité par 11

*    Divisibilité par 42

Avancé

Voir un sujet complet utilisant ces notions:

*    Nombres de Carmichaël 

On y verra en particulier le cas de la puissance 15

Découvrir

*    Pierre de Fermat

 

*    Modulo & Congruences

*    Primalité

*    Nombres Premiers

*    Pseudo Premiers Absolus

*    Théorème de Fermat-Wiles

Cette page

http://villemin.gerard.free.fr/ThNbDemo/PtThFerm.htm