NOMBRES - Curiosités, théorie et usages Accueil DicoNombre Rubriques Nouveautés Édition du: 30/03/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 >>> a et p jusqu'à 5 >>> Cas de a = 2 >>> Exceptions: les pseudo-premiers

PETIT THÉORÈME DE FERMAT

Ce théorème dit que  D = a ^p–1 – 1

est divisible par p sous certaines conditions.

Explorons ces conditions. Notion de pseudo-premier.

Paramètre a et p jusqu'à 5

Rappel du petit théorème de Fermat (PTF)

(1) - Si p est un nombre premier;

(2) - Si a et p sont premiers entre eux;

(3) - Alors, D = a ^{p –1} – 1 est divisible par p.

Exemple

Que dire de 17¹³ ?
Le PTF dit que ce nombre, divisé par 13, donne 17 (ou 17–13 = 4) pour reste.

Voir Magie du PTF

Méthode

On calcule D = a ^{p –1} – 1 pour a et p jusqu'à 5.

On donne aussi la valeur de la division D / p

On donne l'état des 3 conditions indiquées dans le théorème (1), (2) et (3)

Fermat dit: (1) et (2) => (3) Rangées en jaune

Mais, attention, il existe des cas où la divisibilité (3) existe sans que (1) et (2) soient satisfaites Cases en rose

Exemple de lecture

Théorème de Fermat vérifié (deux dernières rangées en jaune)

p premier, p et a premiers entre eux.	p = 2 a = 5	5^2–1 – 1 = 4	= 2 x 2 Ok divisible par p = 2
	p = 3 a = 5	5^3–1 – 1 = 24	= 3 x 12 Ok divisible par p = 3

Contre exemple (dernière case en rose)
montrant que la réciproque de Fermat est inexacte.

p NON premier, p et a premiers entre eux.

p = 4 a = 5

5^4–1 – 1 = 124

= 4 x 31 divisible par p = 4

Les autres cases roses sont triviales, car elles correspondent à n = 0

Cas de la base a =2 

Petit théorème de Fermat avec 2

2 ^{p – 1} 1 mod p

(1) - Si p est un nombre premier;

(2) - Si a et p sont premiers entre eux.

Exploration pour p premier ou non

p	3	4	5	6	7	8	9	10	11	…
2^p – 1 mod p	1	0	1	2	1	0	4	2	1
P premier	OUI		OUI		OUI				OUI

Le théorème est vérifié: le résidu est bien 1 pour les nombres premiers

p	340	341	342	343	344	345	346	347	348	349
2^p – 1mod p	8	1	86	162	128	31	2	1	308	1
P premier		NON						OUI		OUI

La réciproque n'est pas vraie pour 341. Il existe donc des nombres composés qui vérifient le test de Fermat: le résidu est 1 et p n'est pas premier.

Exceptions: les PSEUDO PREMIERS

Dans la traque des nombres premiers, le petit théorème de Fermat peut être utilisé comme un tamis: Il laissera passer tous les nombres premiers et, hélas, quelques autres non premiers, appelé pseudo premiers. Il s'agit des cas où la réciproque de Fermat n'est pas vérifiée: Ce sont les cas où la divisibilité (3) existe sans que les conditions (1) et (2) soient satisfaites pour a et p. Les nombres p, non premiers, tels que D = a ^p – 1 – 1 est divisible par p sont ainsi baptisés: "a - pseudo premier". Voici la liste de tels nombres: Pour a = 2: 341, 561, 645, 1105, 1387 … Pour a = 3: 91, 121, 286, 671, 703 … Pour a = 4: 15, 85, 91, 341, 435 … Etc.

Voir suite en Pseudo Premiers / Probablement premier

Suite	Le petit théorème de Fermat Démonstration Nombre pseudo-premier Divisibilité des formes
Voir	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/PtThFeEx.htm