Petit théorème de Fermat

[invite616a69c2]

Bonjour,

j'ai besoin d'un petit coup de main pour démontrer le petit théorème de Fermat.
Je rappelle le théorème:
Soit p un nombre premier et a un entier naturel non nul tel que pgcd(a,p)=1
alors

J'ai vu des démonstration sur internet, qui passe par le binôme de Newton et démontrent au préalable que .

Je tiens à préciser que je fais une leçon et que je ne peux pas montrer que puisque ce corollaire est situé juste après le théorème.

Puis je procédé comme cela:
on effectue une démonstration par récurrence sur a. Pour a=1 c'est vérifié. Supposons que c'est vrai jusqu'au rang a, montrons pour a+1

Or .
On a alors .
D'où .

Est ce juste?

Merci de votre aide

Amanda
-----

[Amanuensis]

Or .

Faute de frappe, lire :

On a alors .
D'où .

L'inférence est valide uniquement si a+1 différent de 0 modulo p, il faut le préciser.

Enfin mettre des parenthèses et des espaces présenteraient mieux, par exemple . Et en LaTeΧ on peut remplacer '*' par

[invite616a69c2]

D'accord, merci beaucoup.

[Médiat]

Bonjour,

Votre récurrence ne peut pas marcher, en tout cas sous cette forme.

Vous voulez démontrer que :


Or en choisissant p = 3 et a = 5, on a bien

par contre on n'a pas
.

cf. la remarque de Amanuensis, sauf qu'il ne suffit pas de le préciser : cela invalide la récurrence !

[A voir en vidéo sur Futura]

[invite616a69c2]

oui je suis d'accord, je cherchais comment rédiger mais je ne trouve pas...

Puis-je rédiger comme cela:
on veut prouver par récurrence sur a la proposition suivante:.

Et ensuite je met la suite.

c'est bon la?

[Amanuensis]

cf. la remarque de Amanuensis, sauf qu'il ne suffit pas de le préciser : cela invalide la récurrence !

Elle reste valide jusqu'à p-1. Impossible d'aller plus loin par récurrence, effectivement.

Gérer les valeurs au-delà de p+1 demande un complément de démonstration autrement que par récurrence, mais ce n'est pas bien difficile. (Que vaut (p+a)ⁿ modulo p ?)

[invite616a69c2]

Je suis un peu perdue, ce n'est pas la formule du binôme de Newton qui nous aide à prouver cela?

[invite616a69c2]

La formule du binôme nous donne

[invite616a69c2]

Je résume car je suis perdue:
on veut montrer que avec p premier, a entier naturel non nul et pgcd(a,p)=1.
on montre par récurrence sur a le proposition suivante:
.
Pour a=1 c'est évident.
Réurrence
Si a<p, comme p est premier, il est premier avec les termes de 1 à p-1
donc
et
Si a>p, par exemple a=p+1, le binome de Newton nous donne

Et la je bugge, on peut mettre p+a ou il faut mettre p+b???

[inviteaf1870ed]

Ne peut on pas simplement développer le binôme de Newton (a+1)^p=a^p+pa^(p-1)+.......+pa+1 =a^p+1 mod(p) ?

[Amanuensis]

La formule du binôme nous donne

Utiliser le binôme est de la grosse artillerie inutile ! C'est tout simplement une conséquence de ab mod p = (a mod p)(b mod p).

[invite616a69c2]

Oui c'est vrai
Mais pourquoi calculer
On est dans le cas a>p, non?
on doit calculer et comme , on obtient .
C'est ça??
Mon résumé est-il juste aussi??

[Amanuensis]

Oui c'est vrai
Mais pourquoi calculer

Plus clair si on écrit , avec ?

Mon résumé est-il juste aussi??

Pas la dernière partie. Pas faux, mais insuffisant.

[invite616a69c2]

Je ne vois toujours pas pourquoi on calcule ou
d'abord je ne comprend pas pourquoi la puissance est n.

[inviteaf1870ed]

Oui c'est vrai
Mais pourquoi calculer
On est dans le cas a>p, non?
on doit calculer et comme , on obtient .
C'est ça??
Mon résumé est-il juste aussi??

En fait la démonstration par le binôme démontre d'abord que a^p=a mod(p) et en déduit a^p-1=1 mod(p)

cf : http://fr.wikipedia.org/wiki/Petit_t...A8me_de_Fermat

[Amanuensis]

Je ne vois toujours pas pourquoi on calcule ou
d'abord je ne comprend pas pourquoi la puissance est n.

Parce que c'est vrai pour tout n, donc aussi pour p-1. Pas de raison de limiter une propriété simple à un cas particulier.

Que vouliez-vous dire par "je fais une leçon " ?

[invite616a69c2]

ericcc: je ne peux pas mettre le corollaire du th avant le théorème sinon ça ne tient plus debout

Amanuensis:
Je prépare une des leçons pour le capes, celle ci a pour titre: congruence dans Z.
Et j'y ai mis le petit théorème de Fermat.
La puissance est p-1, elle ne bouge pas puisque p est fixé, non??

[invite616a69c2]

plus personne pour me répondre???
S'il vous plait

[Amanuensis]

À quelle question ?

[invite616a69c2]

En fait je n'ai pas compris pourquoi on dois calculer ou . Je suis d'accord pour la puissance, on la démontre par la formule du binôme, c'est vrai pour tout n.
On en est au stade a>p, on doit donc prendre quelque chose de plus grand que a, pourquoi se restreint-on a a+p???
Et a-kp je ne vois pas d'où il sort

[Amanuensis]

En fait je n'ai pas compris pourquoi on dois calculer ou . Je suis d'accord pour la puissance, on la démontre par la formule du binôme, c'est vrai pour tout n.
On en est au stade a>p, on doit donc prendre quelque chose de plus grand que a, pourquoi se restreint-on a a+p???
Et a-kp je ne vois pas d'où il sort

La première partie de la démonstration montre le théorème pour a entre 1 et p-1 compris.

Pour un a en dehors de cet intervalle, on peut se ramener à a-kp dans l'intervalle 0 à p-1, et donc utiliser la propriété démontrée pour cet intervalle.

On utilise la propriété que pour tout a, il existe k entier relatif tel que a-kp = b et b dans l'intervalle 0 à p-1.

(Et je répète qu'utiliser le binome est plus compliqué que nécessaire --et donc peu pédagogique, àmha-- : que la multiplication commute avec la prise de modulo est une propriété de base du modulo.)

[invite616a69c2]

Merci ça y est je viens de percuter pourquoi a-kp!!!
a est plus grand que p donc on peut enlever un certain nombre de fois p pour se ramener au cas précédent.
Maintenant que j'ai compris je ne vois pas en fait pourquoi j'ai bloquée la dessus.

Merci beaucoup pour cette aide précieuse et promis je ne me borne plus avec le binôme

Encore merci et bon week end

[invite616a69c2]

Je suis désolée, j'ai repris cette démonstration et je n'arrive pas à la rédiger
J'essaie:
On veut montrer la proposition P(a): "pour tout a, ".
Si , on montre la proposition par récurrence.
Initialisation: a=1 évident.
Hérédité: Supposons que la proposition p(a) soit vraie, montrons P(a+1)
et .
De plus donc .
p est premier alors p est premier avec les termes de 1 à p-1.
mais on a pas que pgcd(a+1,p)=1!! on a pgcd(a,p)=1

Si a>p, et et pgcd(a-kp,p)=1.
donc

Et si je montre l'hérédité en supposant que P(a-1) est vraie, je dois prouver que a^{p-1}=1mod(p).
Je suis encore bloquée pour la rédaction mais j'ai compris le principe.

[invite616a69c2]

Je vous embête encore, juste un petit coup de main
pour la rédaction s'il vous plait.