Autour du petit théorème de Fermat

Bonjour,
je travaille sur ce théorème dont voici l'énoncé.
Soit $p\in\mathcal{P}$.
(1) Si $a\in\mathbb{Z}$ est tel que $\mathrm{pgcd}(a,p)=1,$ alors $a^{p-1}\equiv 1[p]$.
(2) Si $a\in\mathbb{Z},$ alors $a^p\equiv a[p]$.
Voici la preuve.
(1) On sait que $\mathrm{pgcd}(a,p)=1\iff\bar{a}\in(\mathbb{Z}/p\mathbb{Z})^{\times}$.
D'où, $<\bar{a}>\subset (\mathbb{Z}/p\mathbb{Z})^{\times}$.
Par le théorème de Lagrange, on obtient $\mathrm{card}(<\bar{a}>)\mid \mathrm{card}((\mathbb{Z}/p\mathbb{Z})^{\times})$.
Ainsi, $o(\bar{a})\mid \phi(p)=p-1$.
Et, finalement, $\bar{a}^{p-1}=\bar{1}$, qui s'écrit $a^{p-1}\equiv 1[p]$.

(2) On distingue 3 cas, pour être rigoureux.
Cas 1. $a=0$
Dans ce cas, c'est évident.
Cas 2. $a\in\mathbb{Z}\setminus\{0\}$ tel que $\mathrm{pgcd}(a,p)=1$.
Dans ce cas, le point (1) permet d'écrire $a^{p-1}\equiv 1[p]$ et donc, en multipliant par $a\neq 0$, $a^{p}\equiv a[p]$.
Cas 3. $a\in\mathbb{Z}\setminus\{0\}$ tel que $\mathrm{pgcd}(a,p)>1$.
Dans ce cas, du fait $\mathrm{pgcd}(a,p)>1$, on déduit que $p\mid a$.

Par conséquent, $p\mid a(a^{p-1}-1)$.
Ce qui signifie que $a(a^{p-1}-1)\equiv 0[p]$ et donc $a^p\equiv a[p]$
Mes questions.
1 - J'ai une hésitation dans le cas 3. Est-ce que je n'écris pas de bêtise en affirmant que $p\mid a\Rightarrow p\mid a(a^{p-1}-1)$ ?

2 - Comment écrire avec des quantificateurs le petit théorème de Fermat ? Comment écrire avec des quantificateurs sa négation ?
Est-ce que j'écris les choses correctement en écrivant :

(1) $\forall p\in\mathcal{P},\ \forall a\in\mathbb{Z},\ \mathrm{pgcd}(a,p)=1\Rightarrow a^{p-1}\equiv 1[p]$.
(2) $\forall p\in\mathcal{P},\ \forall a\in\mathbb{Z},\ a^{p}\equiv a[p]$.

Et la négation :
(1) $\exists p\in\mathcal{P},\ \exists a\in\mathbb{Z},\ \lnot(\mathrm{pgcd}(a,p)=1\Rightarrow a^{p-1}\equiv 1[p])$.
(2) $\exists p\in\mathcal{P},\ \exists a\in\mathbb{Z},\ a^{p}\not\equiv a[p]$.

Je ne suis vraiment pas certain de moi sur ces écritures.
Pouvez-vous m'aider ?
D'avance merci.

Réponses

  • 1. C'est correct. Si $m \mid n$ alors $m \mid nl$ pour n'importe quel entier $l$.

    2. C'est correct, mais plutôt inutile. Ne t'enferme pas dans le formalisme, le plus important est de comprendre ce que ça veut dire.

    Je te fais remarquer que ton cas 1 dans la démonstration est inutile puisqu'il est inclus dans ton cas 3.
  • Merci !

    Si je veux l'écrire avec les quantificateurs, c'est pour comprendre pourquoi un nombre de Carmichael est un contre-exemple à la réciproque du petit théorème de Fermat ? Je ne le saisis pas
  • La réciproque ça serait "si $a^{p-1} \equiv 1$ mod $p$ pour tout entiers $a$ premiers avec $p$, alors $p$ est un nombre premier". Les nombres de Carmichael sont par définition les nombres qui sont des contre-exemples à cette propriété.
  • Ce qui veut dire que le petit théorème de Fermat s'écrit comme ceci :
    $\bigg[p\in\mathcal{P}\bigg]\Longrightarrow\bigg[\forall a\in\mathbb{Z},\ \mathrm{pgcd}(a,p)=1\Rightarrow a^{p-1}\equiv 1[p]\bigg]$.

    Et sa réciproque :
    $\bigg[\forall a\in\mathbb{Z},\ \mathrm{pgcd}(a,p)=1\Rightarrow a^{p-1}\equiv 1[p]\bigg]\Longrightarrow\bigg[p\in\mathcal{P}\bigg]$.

    Donc nier celle-ci, c'est écrire :
    $\lnot\bigg(\bigg[\forall a\in\mathbb{Z},\ \mathrm{pgcd}(a,p)=1\Rightarrow a^{p-1}\equiv 1[p]\bigg]\Longrightarrow\bigg[p\in\mathcal{P}\bigg]\bigg)$.
    $\iff \lnot\bigg[p\in\mathcal{P}\bigg]\wedge\bigg[\forall a\in\mathbb{Z},\ \mathrm{pgcd}(a,p)=1\Rightarrow a^{p-1}\equiv 1[p]\bigg]$.
    $\iff\bigg(p\not\in\mathcal{P}\bigg)\wedge\bigg(\lnot\bigg(\forall a\in\mathbb{Z},\ \mathrm{pgcd}(a,p)=1\bigg)\lor\bigg(a^{p-1}\equiv 1[p]\bigg)\bigg)$.
    $\iff\bigg(p\not\in\mathcal{P}\bigg)\wedge\bigg(\bigg(\forall a\in\mathbb{Z},\ \mathrm{pgcd}(a,p)>1\bigg)\lor\bigg(a^{p-1}\equiv 1[p]\bigg)\bigg)$.
    $\iff\bigg[\bigg(p\not\in\mathcal{P}\bigg)\wedge\bigg(\forall a\in\mathbb{Z},\ \mathrm{pgcd}(a,p)>1\bigg)\bigg]$$\lor\bigg[\bigg(p\not\in\mathcal{P}\bigg)\wedge\bigg(a^{p-1}\equiv 1[p]\bigg)\bigg]$.


    Avec $p=561$, je trouve que :

    (1) $\bigg(p=561\not\in\mathcal{P}\bigg)$ puisque $561=3\times 11\times 17$
    et
    (2) $\bigg(a^{561-1}\equiv 1[561]\bigg)$ pour $a\in\mathbb{Z}$ tel que $pgcd(a,561)=1$ puisque :

    $pgcd(a,561)=1\iff pgcd(a,3\times 11\times 17)=1 \iff pgcd(a,3)=1\wedge pgcd(a,11)=1\wedge pgcd(a,17)=1$

    Et donc en appliquant 3 fois le petit théorème de Fermat (sens direct), je trouve :
    $a^{2}\equiv 1[3]$
    $a^{10}\equiv 1[11]$
    $a^{16}\equiv 1[17]$

    J'en déduis que :
    $a^{560}\equiv 1[3]$
    $a^{560}\equiv 1[11]$
    $a^{560}\equiv 1[17]$

    Par conséquent :
    $3\mid a^{560}-1$
    $11\mid a^{560}-1$
    $17\mid a^{560}-1$

    D'où :
    $\mathrm{ppcm}(3,11,17)\mid a^{560}-1$

    Soit :
    $560\mid a^{560}-1$

    On a donc bien : $a^{561-1}\equiv 1[561]$.

    En conclusion, avec (1) et (2), on a donc :
    $\bigg[\bigg(p\not\in\mathcal{P}\bigg)\wedge\bigg(a^{p-1}\equiv 1[p]\bigg)\bigg]\iff$$\lnot\bigg(\bigg[\forall a\in\mathbb{Z},\ \mathrm{pgcd}(a,p)=1\Rightarrow a^{p-1}\equiv 1[p]\bigg]\Longrightarrow\bigg[p\in\mathcal{P}\bigg]\bigg)$.
  • Je t'ai déjà dit que ce genre de raisonnement était parfaitement illisible, je n'ai même pas envie de vérifier que tout est correct.
  • Je n'ai pas du tout le temps de tout lire, mais la négation de (1) peut s'écrire de manière plus sympathique en utilisant ceci :

    Si $A$ et $B$ sont des assertions, $A\implies B$ est équivalent à $(\lnot A) \lor B$ (c'est même souvent posé comme une définition de $\implies$), donc la négation de $A\implies B$ est $A \land (\lnot B)$.

    NB : $\lor$ est le « ou » logique, $\land$ le « et ».
  • S'il existe un entier $a$ tel que $a^{n-1}\equiv 1\mod{n}$ et tel que, pour tout facteur premier $p$ de $n-1$ on a $a^{\frac{n-1}{p}}\not\equiv 1\mod{n}$, alors $n$ est premier.
  • Bonjour brian,

    je connaissais l'équivalence, adopté comme définition, de : $\bigg[A\Rightarrow B\bigg]\iff\bigg[B\lor\lnot A\bigg]$.

    Mais ici, si je ne me trompe pas, on avait quelque chose du type : $\bigg[A\bigg]\Rightarrow \bigg[B\Rightarrow C\bigg]$. Un casse tête, comme le dit Poirot, c'est illisible !

    Et le message de fin de partie, je ne le comprends pas trop en fait.
  • BMaths: le titre de cette file est "Autour du petit théorème de Fermat".

    Le résultat que j'ai indiqué ci-dessus (dû à Edouard Lucas) est une espèce de "réciproque" au petit théorème de Fermat.
  • @BMaths Tu as écrit que la négation de (1) est $\exists p\in\mathcal{P},\ \exists a\in\mathbb{Z},\ \lnot(\mathrm{pgcd}(a,p)=1\Rightarrow a^{p-1}\equiv 1[p])$. Cette assertion se termine par la négation d'une implication. Avec ce que j'ai mentionné, on peut réécrire cette négation d'une manière plus simple qui permet d'énoncer toute la propriété en français de manière compréhensible. Cela n'a rien d'un casse-tête !
  • @Fin de partie.
    Je viens de faire la preuve du fait que si $p\in\mathcal{P}$ alors $\big((\mathbb{Z}/p\mathbb{Z})^*,\times\big)$ est cyclique. On y travaille avec $y_x:=x^{\frac{p-1}{q}}$. Faut-il y voir un lien ?
  • @brian.
    Ah oui, j'aurais dû le voir comme ça !
    On a :
    $\exists p\in\mathcal{P}\ \text{et}\ \exists a\in\mathbb{Z},\ \lnot(\mathrm{pgcd}(a,p)=1\Rightarrow a^{p-1}\equiv 1[p])$
    $\iff\exists p\in\mathcal{P}\ \text{et}\ \exists a\in\mathbb{Z},\ \lnot(a^{p-1}\equiv 1[p] \lor \mathrm{pgcd}(a,p)>1)$
    $\iff\exists p\in\mathcal{P}\ \text{et}\ \exists a\in\mathbb{Z},\ \lnot(a^{p-1}\equiv 1[p])\wedge\lnot (\mathrm{pgcd}(a,p)>1)$
    $\iff\exists p\in\mathcal{P}\ \text{et}\ \exists a\in\mathbb{Z},\ (a^{p-1}\not\equiv 1[p])\wedge(\mathrm{pgcd}(a,p)=1)$

    Est-ce bon ?
  • Oui, à part que la négation de $\operatorname{pgcd}(a,p)=1$ est $\operatorname{pgcd}(a,p) \neq 1$ ! Rappelons qu'un pgcd peut être nul (avec la « bonne » définition : celle utilisant la notion d'idéal d'un anneau).

    Tu peux alors énoncer la négation de (1) en français : « il existe un nombre premier $p$ et un entier relatif $a$ premiers entre eux et tels que $a^{p-1}$ n'est pas congru à 1 modulo $p$. » Ça se comprend bien, non ?

    Ou pour insister sur le fait que cela contredit (1) que l'on sait vraie : « il existe un nombre premier $p$ et un entier relatif $a$ tels que $a$ et $p$ soient premiers entre eux et pourtant $a^{p-1}$ non congru à 1 modulo $p$ ».

    Edit : utilisation de \operatorname{pgcd}.
  • brian a écrit:
    Oui, à part que la négation de $pgcd(a,p)=1$ est $pgcd(a,p) \neq 1$ ! Rappelons qu'un pgcd peut être nul (avec la « bonne » définition : celle utilisant la notion d'idéal d'un anneau).

    Tu peux m'en dire plus ?
    brian a écrit:
    « il existe un nombre premier $p$ et un entier relatif $a$ tels que $a$ et $p$ soient premiers entre eux et pourtant $a^{p-1}$ non congru à 1 modulo $p$ »
    Parfait merci !
    Deux remarques toutefois:

    - Il faut donc que je trouve un nombre $p$ premier, et un entier relatif $a$ premier avec $p$, tels que $a^{p-1}$ n'est pas congru à 1 modulo $p$ ?

    - Par la suite, je travaille avec les nombres de Carmichael. Donc p n'est pas supposé être premier au départ. Ainsi, formuler la négation comme ceci, ne permet pas de parler de ces nombres là. Ou alors quelque chose m'échappe ?
  • Le PGCD de $a$ et $b$ est le générateur positif de l'idéal/sous-groupe $a \mathbb Z + b \mathbb Z$ de $\mathbb Z$. Autrement dit, $d$ est le PGCD de $a$ et $b$ si et seulement si $a \mathbb Z + b \mathbb Z = d \mathbb Z$. Ça se voit avec la relation de Bezout. En particulier $PGCD(0, 0) = 0$. :-D
  • Je me fais toujours avoir sur les "cas spéciaux" ! Je pensais jusqu'à maintenant que le contraire de $\operatorname{pgcd}(a,b)=1$ était $\operatorname{pgcd}(a,b)>1$, je saurai dorénavant.

    Il faut que j'étudie plus avant la question des idéaux, j'y reviendrai.
  • Voilà, la définition du pgcd donnée par Poirot rend très simples les preuves des résultats arithmétiques élémentaires : il n'y a la plupart du temps aucun cas particulier à distinguer (i.e., pas besoin de traiter à part le cas de zéro ni de prétendre que le pgcd de zéro et quelque chose n'est pas défini). De plus, on a une définition analogue pour le ppcm (intersection des idéaux) et cette belle mécanique s'applique de manière identique à $\K[X]$, et plus généralement aux anneaux euclidiens (ou principaux, mais alors on n'a pas forcément la division euclidienne ; cela doit limiter ce que l'on peut faire).

    Concernant cette question :
    BMaths a écrit:
    Il faut donc que je trouve un nombre p premier, et un entier relatif $a$ premier avec $p$, tels que $a^{p-1}$ n'est pas congru à 1 modulo $p$ ?

    Hum, si tu y arrives, tu auras prouvé que le petit théorème de Fermat est faux. Tu deviendras alors probablement une célébrité mondiale en moins de temps qu'il ne faut pour le dire. :-D

    Quant à tes interrogations sur les nombres de Carmichael, désolé, je laisse ça aux spécialistes. Je suis un simple touriste de passage (le tourisme mathématique n'est pas interdit, lui ;-)).
  • BMaths:
    C'est plutôt une réciproque dont on a besoin:

    Sauf erreur: $n$ un entier naturel strictement plus grand que $1$. Si $\left(\left(\mathbb{Z}/n\mathbb{Z}\right)^\star,\times\right)$ est cyclique ET d'ordre $n-1$ alors $n$ est premier.

    NB:le groupe $\left(\left(\mathbb{Z}/n\mathbb{Z}\right)^\star,\times\right)$ peut être cyclique sans que $n$ soit premier.
    Mais dans ce cas-là l'ordre de ce groupe n'est pas $n-1$.

    PS:
    Le fait que $\left(\left(\mathbb{Z}/n\mathbb{Z}\right)^\star,\times\right)$ est une information superflue ici, ce qui compte est que l'ordre de ce groupe soit $n-1$.
  • Toujours sauf erreur,

    $n$, un entier naturel strictement plus grand que $1$, est premier si et seulement l'ordre de $\left(\left(\mathbb{Z}/n\mathbb{Z}\right)^\star,\times\right)$ est $n-1$

    Démonstration:

    L'ordre de $\left(\left(\mathbb{Z}/n\mathbb{Z}\right)^\star,\times\right)$ est le nombre d'entiers non nuls inférieurs ou égaux à $n$ qui sont premiers avec $n$.

    Le "sens direct" de l'équivalence est clair.

    Le "sens réciproque".
    Supposons que $n$ soit composé, et qu'il soit divisible par $1<d<n$. Cela signifie qu'il faut, au moins, retirer de la liste des nombres $1,2,...,n$ les nombres $d$ et $n$ et donc l''ordre de $\left(\left(\mathbb{Z}/n\mathbb{Z}\right)^\star,\times\right)$ est strictement inférieur à $n-1$ ce qui est contraire à l'hypothèse donc $n$ n'est pas pas composé, il est donc premier.
  • @FDP : sinon on utilise la formule $\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$.
  • Poirot:
    Je voulais faire très élémentaire. B-)-

    Le truc qui n'est pas totalement évident est pourquoi l'ordre de $\left(\left(\mathbb{Z}/n\mathbb{Z}\right)^\star,\times\right)$ est égal au nombre d'entiers naturels non nuls inférieurs ou égaux à $n$ et premiers avec $n$?

    Si $m$ est premier avec $n$ alors d'après le théorème de Bézout il existe $u,v$ entiers tels que $un+vm=1$
    Autrement dit, $vm=1-un$ , c'est à dire que $vm\equiv 1 \mod{n}$ donc $m$ est inversible modulo $n$.

    Réciproquement, si $m$ est inversible modulo $n$ alors il existe $u,v$ entiers tels que $vm=1+un$ c'est à dire $vm-un=1$ donc d'après le théorème de Bézout $m$ et $n$ sont premiers entre eux.

    Donc, le sous-ensemble de $\mathbb{N}$ constitué des entiers $1\leq m<n$ qui sont premiers avec $n$ est égal au sous-ensemble de $\mathbb{N}$ constitué des entiers $1\leq m<n$ qui sont inversibles modulo $n$.
  • brian a écrit:
    Hum, si tu y arrives, tu auras prouvé que le petit théorème de Fermat est faux. Tu deviendras alors probablement une célébrité mondiale en moins de temps qu'il ne faut pour le dire. :-D

    Oh, j'abuse ! La célébrité, ce n'est pas pour demain !

    Ce n'est pas la négation de (1) que je veux.
    C'est la réciproque de (1), d'où mon délire avec mes équivalences logiques !
  • Fin de partie a écrit:
    Toujours sauf erreur, $n$, un entier naturel strictement plus grand que $1$, est premier si et seulement l'ordre de $\left(\left(\mathbb{Z}/n\mathbb{Z}\right)^\star,\times\right)$ est $n-1$

    Comment puis-je utiliser ce résultat dans le cas présent ?
  • Dans le résultat de Lucas on a pour hypothèse qu'il existe $a$ entier tel que $a^{n-1}\equiv 1\mod{n}$ et pour tout nombre premier $p$ qui divise $n-1$ on a $a^{\frac{n-1}{p}}\not \equiv 1\mod{n}$

    Cela veut dire que si on prend deux entiers distincts parmi $1,a,a^2,....,a^{n-1}$ ils ne sont pas congrus modulo $n$.

    Par ailleurs, $a^{m}\times a^{s-m}=a^{s}$, et $s-m$ est un entier naturel si $0\leq m\leq s$
    (ce résultat on va l'appliquer pour $s=n-1$)
Connectez-vous ou Inscrivez-vous pour répondre.