Petit théorème de Fermat
dans Arithmétique
Bonsoir,
Soit $p$ un nombre premier.
Je viens de prouver que $\forall (a,b) \in \Z^2 \ (a+b)^p \equiv a^p + b^p [p]$
Petit théorème de Fermat :
Pour tout nombre premier $p$ et pour tout entier relatif $n$ on a : $n^p \equiv n[p]$
La démonstration est facile quand $n \in \N$. Je ne comprends pas le passage suivant :
Par compatibilité de la congruence avec la multiplication, la classe de $n^p$ modulo $p$ ne dépend que de la classe de $n$.
Je n'ai pas compris cette remarque ni le rapport avec la démonstration.
Comme tout entier relatif est congru modulo $p$ à un entier naturel, il suffit donc de prouver le résultat lorsque $n$ est un entier naturel.
Je n'ai pas compris non plus le rapport entre le fait que tout entier soit congru à un entier naturel et le fait qu'il suffit de prouver le résultat avec $n$ entier naturel.
Soit $p$ un nombre premier.
Je viens de prouver que $\forall (a,b) \in \Z^2 \ (a+b)^p \equiv a^p + b^p [p]$
Petit théorème de Fermat :
Pour tout nombre premier $p$ et pour tout entier relatif $n$ on a : $n^p \equiv n[p]$
La démonstration est facile quand $n \in \N$. Je ne comprends pas le passage suivant :
Par compatibilité de la congruence avec la multiplication, la classe de $n^p$ modulo $p$ ne dépend que de la classe de $n$.
Je n'ai pas compris cette remarque ni le rapport avec la démonstration.
Comme tout entier relatif est congru modulo $p$ à un entier naturel, il suffit donc de prouver le résultat lorsque $n$ est un entier naturel.
Je n'ai pas compris non plus le rapport entre le fait que tout entier soit congru à un entier naturel et le fait qu'il suffit de prouver le résultat avec $n$ entier naturel.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
En ce qui concerne la première phrase, c'est faux, elle dépend aussi de $p$ :-D. Plus sérieusement, cette histoire de compatibilité de la multiplication ne signifie que ça $\forall (a,a',b,b',n)\in \mathbb{Z}^3,\ a=a'\pmod n\wedge b=b'\pmod n\rightarrow ab=a'b'\pmod n$, ce qui implique évidemment (il faut faire une petite récurrence quand même) que $\forall (n,m,p)\in \mathbb{Z},\ n=m\pmod p\rightarrow n^p=m^p\pmod p$.
En ce qui concerne la deuxième phrase, je suis très content de la lire, je désespérais parce que mes exercices sont tout pourris et mon style chiant et tout plein d'expressions inutiles, l'auteur de ton bouquin a largement prouvé qu'on peut faire pire en terme de phrases inutiles et passer professionnel (cool !). À part cet aspect psychologique, c'est oubliable, passe à la suite !
Par exemple, modulo $3$ , si on veut remplacer $-1$ par un entier comme représentant d'une classe modulo $3$
on lui rajoute des $3$ jusqu'à obtenir un nombre entier naturel: $-1+3=2$ et c'est un bien un entier naturel qui est congru à $-1$ par construction: on a bien que $-1-2$ est un multiple de $3$.
Si on veut faire la même chose avec $-19$ modulo $7$
$-19+7=-12$
$-12+7=-5$
$-5+7=2$
donc $-19$ et $2$ sont congrus modulo $7$.
(il faut que leur différence soit un multiple de $7$ ce qui est le cas par construction)
Pour le point 1) cl(a.b)=cl(a).cl(b) donc en particulier si $a=b$, $\text{cl}(a^2)=\text{cl}(a)^2$ , $\text{cl}(a^p)=\text{cl}(a)^p$
cl(a) est la classe de $a$ dans la relation de congruence.
Je ne comprends pas pourquoi il suffit de prouver le petit théorème pour les entiers naturels.
@Fin de partie
Je suis d'accord avec votre remarque mais je n'ai toujours pas compris les remarques de l'auteur.
Vos remarques sont pertinentes mais je ne comprends toujours pas les passages en rouge de mon livre.
Ce que je ne comprends pas c'est que si $n \in \Z^{-}$ et qu'on veut montrer que $n^p \equiv n[p]$.
On sait que $n \equiv r [p]$ avec $r \geq 0$ donc on veut montrer que $n^p \equiv r [p]$ ? Le $r$ est différent du $n$ donc on démontre pas le petit théorème non ?
Bref je n'ai pas compris.
Et l'histoire de la classe de $n^p$ modulo $p$ qui ne dépend que de la classe de $n$ je ne comprends pas non plus. Et à quoi ça nous sert ici ?
Par compatibilité de la congruence avec la multiplication, la classe de $n^p$ modulo $p$ ne dépend que de la classe de $n$.
Comment le montrer et quel est l'intérêt de ce résultat dans cette démonstration ?
Ne sachant pas de quelle démonstration tu parles (il existe plusieurs démonstrations du petit th. de Fermat) je ne sais pas quoi te répondre.
PS:
Il y avait un problème dans les produits, je pense que c'est correct maintenant.
Mais je ne comprends pas ce que veux dire le "la classe de $n^p$ modulo $p$ ne dépend que de la classe de $n$."
L'auteur utilise cet argument pour justifier qu'il suffit de démontrer le théorème de Fermat pour $n \in \N$.
La démonstration ne me pose pas de souci.
Application : Quelle est la classe de $1300001^{13}$ modulo 13 ?
Si tu ne précises pas de quelle démonstration tu parles, je ne sais pas répondre précisément à ta question.
Par ailleurs une autre formulation du petit th. de Fermat est: $p$ premier, $n^p\equiv n\mod{p}$
Ce qui veut dire que $n^p$ et $n$ sont dans la même classe de congruence modulo $p$ si $p$ est premier.
A condition que les seules opérations faites soient: additions/soustraction/multiplication/élévation à une puissance entière.
ON NE DIVISE PAS dans ce contexte. Le quotient de deux classes modulo $n$ n'existe pas nécessairement.
On a démontré (par récurrence sur $n$) que pour tout nombre premier $p$ et pour tout $n \in \N$ on a : $n^p \equiv n[p]$.
Si maintenant $n \in \Z$, $n<0$, et si $p>2$, alors $p$ est impair d'où : $-n^p=(-n)^p \equiv -n[p]$, et par suite $n^p \equiv n[p]$.
Et si $p=2$, etc.
Bonne soirée.
Fr. Ch.
Merci.
Je suis d'accord avec vous. Inutilement compliqué.
Votre preuve est bien plus claire et simple à comprendre.
@Gerard
130000113 modulo 13 ?
$130000113=10000008 \times 13 + 9$
Or $9 \equiv -4 [13]$ donc $ 130000113 \equiv (-4)^{13} [13] \equiv -67108864 [13]$
J'ai pas terminé en effet, la classe modulo 13 appartient à l'ensemble $\{0,\cdots 12 \}$. J'ai effectué des divisions euclidiennes successives.
Je trouve une classe de $-4$ modulo $13$ soit $9$ modulo $13$.
Une démonstration classique du petit théorème de Fermat.
Soit $p$ un nombre premier. On cherche à démontrer que $a^{p-1}$ est congru à $1$ modulo $p$ quand $a$ est premier à $p$ (c'est à dire quand $a$ n'est pas un multiple de $p$)
On considère les $p-1$ classes d'équivalence dans la relation modulo $p$. On laisse de côté la classe de $0$ qui ne nous intéresse pas ici.
On définit l'application $f$ sur l'ensemble de ces $p-1$ classes d'équivalence par:
Si $x$ est un représentant d'une classe on considère le nombre $ax$.
Cela définit bien une application de l'ensemble des classes vers l'ensemble des classes.
(si on change de représentant on "atterrit" toujours dans la même classe d'équivalence modulo $p$)
Cette application est une bijection sur l'ensemble des classes d'équivalence.
Cette application permute les classes d'équivalences.
En particulier, cette propriété permet d'affirmer que les nombres $1\times 2\times ...\times (p-1)=(p-1)!$ et $a\times 2a\times ...\times (p-1)a=a^{p-1}(p-1)!$ sont dans la même classe d'équivalence.
Ainsi leur différence est un multiple de $p$: $a^{p-1}(p-1)!-(p-1)!=(p-1)!(a^{p-1}-1)$
Mais $p$ et $(p-1)!$ sont premiers entre eux donc, d'après le th. de Gauss, $p$ divise $a^{p-1}-1$.
Si l'on veut se placer dans $\mathbb Z/p \mathbb Z$, le plus court est d'observer que c'est un corps et que les éléments non nuls forment donc un groupe multiplicatif $ (\mathbb Z/p \mathbb Z)^*$, comprenant $p-1$ éléments, et que comme dans tout groupe fini, pour tout x élément de ce groupe on a : $x^{p-1}=1$.
Le même argument vaut pour le théorème d'Euler $x^{\phi(n)} \equiv 1 \pmod {n}$ si $x$ est premier avec $n$.
Mais si l'on veut rester dans $\mathbb Z$, il y a aussi plusieurs possibilités : https://en.wikipedia.org/wiki/Proofs_of_Fermat's_little_theorem
Bonne soirée.
Fr. Ch.
Je n'ai pas le temps, tout de suite maintenant, de vous trouver des références, dès que j'aurais quelques heures de libre j'essaie de le faire si quelqu'un ne fournit pas une référence avant.
C'est signalé sur la page Wikipedia que j'ai citée.
Je n'ai pas trop le temps non plus mais j'essayerai de retrouver les références et de me replonger dans les détails de la démonstration.
Les preuves combinatoires sont très éclairantes.
...
Dans le problème des colliers, on considère comme identiques des colliers qui se déduisent par rotation.
ps: question intéressante à la fin de l'extrait: à quand une preuve combinatoire du grand théorème de Fermat ?
...
Cette démonstration est mentionnée, si je me rappelle bien, dans le bouquin de Dickson, History of the theory of numbers*.
Il y a plein de démonstrations du petit théorème de Fermat mais ce sont essentiellement des variantes qui s'appuient sur les propriétés de divisibilité des coefficients binomiaux par un nombre premier.
Mais ce livre ne mentionne pas, si me souviens bien, de démonstration liée à un système dynamique (le livre est ancien).
*Voir: https://archive.org/details/historyoftheoryo01dick/page/n6/mode/2up