[TS] démonstration : p | n^p - n

[prgasp77]

Bonjour à tous, je sèche sur une question d'un devoir : "Démontrez que pour tout naturel n, le nombre premier p divise n^p - n" Je sais que c'est faisable par récurence, mais je ne vois pas comment ... Je vous remercie de me mettre sur la voie.
-----

[invite9b7da66e]

Avec la formule du binôme (au rang n+1), ça a l'air de marcher ! Essaies de mettre en évidence l'hypothèse de récurrence.

[inviteea0d596d]

première démo qui me vient:

raisonnement par récurrence + par l'absurde.

supposons la propriété vraie jusqu'à (n-1)
Montrons qu'elle l'est aussi pour n.

Pour cela supposons par l'absurde qu'elle ne l'est pas pour n.
notons X=n^p-n

si p ne divise pas X alors il existe q et r entiers tel que X=pq+r
r non nul.

développons X pour obtenir X= r^p-r + pq.S S étant entier
comme r<n l'hypothèse de départ s'applique. donc p divise r^p-r
et comme p divise aussi pqS
on en déduit que p divise X. ce qui contredit l'hypothèse posée.
Donc p divise bien X et par récurrence la propiété devient vraie pour tout n.

[inviteea0d596d]

zut, y a une couille dans le fromage.

il faut reprendre la démo avec p à la place de n pour l'indice de récurrence.

[A voir en vidéo sur Futura]

[prgasp77]

Colas : Mais quelle est cette fameuse loi du binôme ?
Qu'entends-tu par "mettre en évidence l'hypothèse de récurrence" ? Etablir le propriété héréditaire ? Si c'est ca je ne vois que P(n) : "p | n^p - n". Il me faut alors démontrer que si p | n^p - n alors p | (n+1)^p - n - 1 ... mais comment ?

développons X pour obtenir X= r^p-r + pqS

Comment transformes-tu X = n^p - n = pq + r en X = r^p - r + pqS ?

[invite9b7da66e]

La formule du binôme : http://www.maths-express.com/bac-exo...oba/binome.htm (premier lien que j'ai trouvé).

Je suppose n^p-n divisible par p. Il faut donc montrer que (n+1)^p -n-1 est encore divisible par p. Avec la formule précédente c'est possible, je pense que tu l'as forcement vu sinon la démonstration risque d'être étrange (pardon Azrem mais ça ne m'a pas convaincu !!). Si tu ne trouves pas avec ça je donnerais plus de détails.

[invite63ea3fef]

C'est vrai pour n = 1 : quelque soit p dans N, premier ou pas premier d'ailleurs, on a 1-1 = 0 = 0*p.

Excuses c'est tout faux mon truc ...

[invite63ea3fef]

Bon si c'est vrai au rang n alors:
n^p-n = kp, k dans N, pour tout p premier dans N ou Z d'ailleurs...
-> au rang n+1 ça donne : (n+1)^p-n-1 = n^p-n+1-1+Ap, A dans N (on s'en fiche de A).
Les 1 s'en vont -> (n^p-n)+Ap->avec l'hypothèse de récurrence-> (k+A)*p CQFD, mais on n'utilise pas que p est premier
Faut voir ...

[g_h]

D'après le "petit" théoreme de Fermat :
n^p = n [p] (avec p premier)

donc n^p - n = 0 [p]
d'où p divise n^p - n

Sinon, cherche une démonstration du petit théorême de Fermat (il y en a plusieurs)

[prgasp77]

mais on n'utilise pas que p est premier

p premier est donné au debut de l'exercice. Cette démonstration n'est qu'une partie d'une question de l'exo. Mais le petit théorème de Fermat me parait le plus approprié (j'y avais pas pensé, ca m'enerve ...)

Merci à tous de votre aide.

[invite9b7da66e]

D'après le "petit" théoreme de Fermat :
n^p = n [p] (avec p premier)

donc n^p - n = 0 [p]
d'où p divise n^p - n

C'est le petit théorème de Fermat mot pour mot, et non une démonstration !

[inviteea0d596d]

désolé pour la démo foireuse que j'ai donné pendant ma pause déjeuner.



je vous la refais.

Par récurence.
pour n=1 évident ( je vous laisse le vérifier)
Supposons la propriété vraie jusqu'à n-1.
Et montrons que c'est vrai pour n.

1er cas: p divise n
alors p divise n^p-n donc la récurrence est vérifiée

2 ième cas: p ne divise pas n
alors il existe q et 0<r<n tel que n=pq+r

calculons n^p-n en substituant n par pq+r et en développant.

on obtient: r^p-r + pq.S ou S est un entier

comme r<n on a p qui divise r^p-r (hypothèse)
et p divise pq.S
d'où p divise n^p-n

CQFD

j'espère vous avoir convaincu cette fois.

[inviteea0d596d]

précision pour prgas77 :

utilise les coefficients Binomiaux pour développer (pq+r)^p et sort en les extrémités .

(pq+r)^p=(pq)^p+pq( .... ) + r^p

[invite63ea3fef]

D'après le "petit" théoreme de Fermat :
n^p = n [p] (avec p premier)

donc n^p - n = 0 [p]
d'où p divise n^p - n

Sinon, cherche une démonstration du petit théorême de Fermat (il y en a plusieurs)

Oui c'était l'application directe du petit théorème de Fermat !

En fait, ma récurrence était valable seulement si p est premier : (n+1)^p = n^p + 1 + Kp seulement si p premier ...

Cela donne une propriété remarquable qui peut servir dans des exos :
Pour tout p entier relatif premier, pour tout n entier relatif, (n+1)^p = n^p + 1 + Kp, où K est dans Z ...