Petit théorème de Fermat
dans Arithmétique
Bonjour,
Comment peut-on démontrer le petit théorème de Fermat qui dit que pour $p$ premier et $a$ entier on a :
$$a^p \equiv a \mod{p}$$
Comment peut-on démontrer le petit théorème de Fermat qui dit que pour $p$ premier et $a$ entier on a :
$$a^p \equiv a \mod{p}$$
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Sans garantie : récurrence forte sur $a.$
Précisément. Qu'est-ce que tu penses de $(p-1)!\mod{p}$ et de $f(1)\times f(2)\times\cdots\times f(p-1)\mod{p}$ ?
Dans ce cas, puisque $p$ est premier, cela signifie que $p$ divise $a$ et il est clair que $a^p-a$ est,dans ce cas-là, divisible par $p$.
PS:
J'avais mal lu le premier message. Mais le message reste pertinent pour ceux qui croyaient qu'on doit supposer $a$ et $p$ premiers entre eux dans cette variante du petit théorème de Fermat.
D'accord, merci pour le conseil je vais essayer faire une récurrence.
@Fin de partie
Pourquoi $p$ premier divise $a$ ?
si $a$ et $p$ ne sont pas premiers entre eux cela signifie qu'ils ont un diviseur commun entier positif qui n'est pas $1$.
Vu que $p$ est premier n'a que deux diviseurs par définition, $1$ et lui-même cela limite le nombre de diviseurs qu'il peut avoir en commun avec un autre nombre.
PS:
Ce que je voulais dire initialement est que $a^p\equiv a\mod{p}$ est une trivialité dans le cas où $p$ et $a$ ne sont pas premiers entre eux. Le cas intéressant est quand $p$ ne divise pas $a$.
Une autre expression du petit théorème de Fermat est:
Si $p$ est premier et $p$ ne divise pas $a$ alors on a:
\begin{align}a^{p-1}\equiv 1\mod{p}\end{align}
PS2:
La version que tu cites du petit théorème à l'avantage qu'on ne fait aucune supposition sur $a$. Ce qui peut être pratique à l'occasion mais masque des trucs.
PS3:
Pour démontrer le petit théorème de Fermat par récurrence je pense qu'il faut connaître des propriétés de divisibilité de coefficients binomiaux par un nombre premier ce qui ne me semble pas être une connaissance ordinaire d'un lycéen (ou autre)
Pour la récurrence j'ai du mal à avancer car je suis bloqué avec la formule du binôme de Newton. Je ne la maîtrise pas vraiment j'arrive juste à la comprendre.
Il me faut montrer que $$\sum_{k=0}^{p} \binom{p}{k} \times a^k - a - 1$$ est un multiple de $p$.
Je prends $p = 5$, on a :
$$
(a+b)^5 = a^5+5a^4b+10a^3b^2+10a^2b^3+5ab^4+b^5
$$
Si on réduit modulo $5$, on trouve $(a+b)^5 = a^5+b^5 \pmod{5}$.
Dans le raisonnement par récurrence on est amené à développer $(a+1)^{p}=\sum_{k=0}^{p}\binom{p}{k}a^k$ sauf erreur.
Pas évident de continuer. Le premier terme est $1$ et le dernier est $a^p$ c'est un bon début mais il faudrait se débarrasser des autres termes "parasites".
En calculant le premier et dernier terme on a :
$$\sum_{k=1}^{p-1} \binom{p}{k} \times a^k + a(a^{p-1}-1)$$
qui doit être multiple de $p$.
Je vais essayer d'étudier ce que tu as proposé plus haut.
Ce qui veut dire que $1\times 2\times....\times (p-1)!\equiv a\times 2a\times 3\times...\times (p-1)a\mod{p}$ (attention il n'y a pas de !. Je laisse la coquille pour que la suite de l'échange soit compréhensible)
Ce qui veut dire aussi que: $(p-1)!\equiv a^{p-1}(p-1)!\mod{p}$
donc $(p-1)!\left(a^{p-1}-1\right)\equiv 0\mod{p}$
Ce qui veut dire que $(p-1)!\left(a^{p-1}-1\right)$ est divisible par $p$.
Or, $p$ est premier avec $(p-1)!$ donc d'après le théorème de Gauss, $p$ divise $a^{p-1}-1$
En effet, on sait que $(a+1)^p=1+a^p+....$ l'hypothèse de récurrence permet de "remplacer" $a^p$ par $a$. Il reste à montrer que la somme des termes restant est divisible par $p$ mais, en fait, il semble que chaque terme restant est divisible par $p$.
$p$ divise donc le membre de gauche mais il est premier avec $k!(p-k)!$ si $0<k<p$ car il ne le divise pas on peut appliquer le théorème de Gauss qui nous garantit donc que $p$ divise $\binom{p}{k}$ lorsque $0<k<p$.
si on multiplie $1,2,...,p-1$ on n'obtient aucun des nombres que tu indiques.
L'autre nombre est:
$(1\times a)\times (2\times a)\times ....\times \big((p-1)\times a\big)$
On peut regrouper les facteurs $a$ dans le produit (ils sont au nombre de $p-1$)
$\displaystyle (p-1)!=1\times 2\times ...\times (p-1)=\prod_{k=1}^{p-1}k$ si tu veux l'écrire sous cette forme-là.
Ce message-ci http://www.les-mathematiques.net/phorum/read.php?5,1783390,1783448#msg-1783448 contient une esquisse de démonstration complète.
Les deux messages qui suivent terminent d'esquisser une démonstration par récurrence de ce théorème.
L'application $x\rightarrow ax$ définie sur l'ensemble des classes modulo $p$ a la propriété qu'elle permute les classes entre elles donc en particulier le produit $1\times 2\times ....(p-1)$ est congru modulo $p$ à $a\times (2a)\times ...\times (p-1)a$
Un entier $1<k<p-1$ est congru à un seul entier $k'a$ avec $0<k'<p-1$. Si on prend deux entiers les " k' " obtenus sont obligatoirement différents.
$p$ ne joue aucun rôle particulier dans cette propriété, cela peut être n'importe quel entier naturel non nul. J'ai seulement garder $p$ pour essayer de faire le lien avec ce qui précède.
PS:
Une application bijective de cet ensemble dans lui-même ne fait que "permuter" les éléments de cet ensemble mais quand $k$ parcourt cet ensemble on a exactement $p-1$ valeurs différentes pour $f(k)$ qui sont dans cet ensemble. On ne veut pas avoir que $f(1)=f(2)$ par exemple.
> Ce qui veut dire que $1\times 2\times....\times
(p-1)!\equiv a\times 2a\times 3\times...\times
(p-1)a\mod{p}$
Est-ce que ça ne devrait pas plutôt être $1\times 2\times....\times(p-1)\equiv a\times 2a\times 3\times...\times(p-1)a\mod{p}$
avec le ! en moins ?
Regarder ici
Pour $a=1$, $a^p=1=a.$ On suppose que $a^p=a \mod(p).$ On calcule $(a+1)^p=a^p+...+1=a^p+1\mod(p)=a+1\mod(p)$ puisque les autres termes dans le développement du binôme de Newton sont divisibles par $p.$ Un message plus haut démontre cette propriété vraie pour $p$ premier. Voilà !
$$(p-1)! \equiv a \times 2a \times ... \times (p-1)a \mod{n}$$
Je ne sais pas vraiment ce que signifie la notion de bijection.
Est-il possible de faire une récurrence à l'envers, c'est à dire montrer que $P(n-1)$ est vrai si on suppose $P(n)$ vraie ?