Forme d’un nombre premier

Bonjour,
Une dernière (?) question :
Savez-vous si $3$ est le seul nombre premier de la forme $4^n-1$ $(n\in\mathbb{N})$ ?
Merci d’avance.

Réponses

  • oui car $4^n-1$ est toujours divisible par $3$.
  • Merci, Raoul.S.
    (Je revenais pour annuler mon message, ayant trouvé la réponse.)
  • Salut.
    On m'a déjà conseillé dans ce forum de chercher pendant un mois avant de poster mes résultats. J'y arrive pas parce que je préfère partager et vite voir mes erreurs s'il y en a. Je te donne quand mème @Sneg, le mème conseil en réduisant le délais à cinq jours.
  • Je te donne entièrement raison, babsgueye. Moi-même, je regrette d’avoir posté ce message en panique totale à 01h00 du matin.
    Je me suis d’ailleurs relevée à 02h00 pour le supprimer, mais raoul.S avait déjà eu la gentillesse de me répondre. Je le remercie à nouveau.

    Y aurait-il moyen de supprimer ce fil ? Merci d’avance.
  • Sneg: Pourquoi le supprimer?

    Babsgueye: Avant de poster les "démonstrations" stupéfiantes dont tu abreuves le forum, la bienséance commande que tu devrais t'assurer du mieux que tu le peux que ce que tu écris n'est pas rempli d'erreurs que tu aurais pu détecter toi-même. Quelque chose me dit que tu ne prends pas cette peine.

    PS:
    Errare humanum est perseverare diabolicum.
  • @ Fin de partie et tous :

    Si vous n'en avez pas assez des questions que je pose tous ces temps-ci, je me permets de vous en poser une de plus.
    Soyez rassurés, si toutes les pièces du puzzle s'emboîtent convenablement, cela devrait être la dernière avant un bon bout de temps. C'est ce que je souhaite. La voici :

    Soit $p$, un nombre premier qui ne divise pas $a$.
    D'après le petit théorème de Fermat, on a : $a^{p-1}\equiv \color{red}{1}\pmod{p}$.
    Maintenant, si j'ai en plus dans un raisonnement : $a^{m}\equiv \color{red}{1}\pmod{p}$
    puis-je en conclure que $p$ divise $a^{PGCD(p-1, m)}\color{red}{-1}$ ?

    Merci d'avance.
    Corrections en rouge après la remarque de Chaurien.
  • Revois ton petit théorème de Fermat, c'est $a^{p-1}\equiv 1\pmod{p}$.
    Sinon, tes questions sont tout à fait appropriées et tu n'as pas à te retenir de les poser.
    Bonne soirée.
    Fr. Ch.
  • Bonjour, Chaurien,
    Décidément, tu aimes entourer tes messages de mystère. Voilà que maintenant tu écris en LaTeX sans les signes $$ !
  • Inattention, j'ai corrigé.
  • Inattention, j’ai corrigé moi aussi. :-)
  • Soit $d=PGCD (p-1,m)$. Il existe $u \in \mathbb Z$ et $v \in \mathbb Z$ tels que : $(p-1)u+mv=d$ (Bézout).
    D'où : $a^d=a^{(p-1)u+mv} \equiv 1\pmod{p}$.
    Bonne soirée.
    Fr. Ch.
  • Mais oui ! C’est si simple quand je le vois écrit.
    (Mon intuition se fondait sur des exemples numériques et je n’arrivais pas à généraliser.)
    C’est une très bonne nouvelle pour moi.
    Mille mercis, Chaurien.
  • Attention, si l'on veut être tout à fait rigoureux, il y a une petite arnaque dans ma démonstration, un petit piège ;-). J'ai bien dit que $u$ et $v$ sont des entiers relatifs, et donc $a^u$ n'est pas nécessairement un entier. Pour que ce soit rigoureux, il faut passer dans $\mathbb Z / p\mathbb Z$, car dans le groupe multiplicatif des éléments non nuls de ce corps commutatif, les exposants négatifs sont autorisés, pour ainsi dire. Si l'on veut rester dans $\mathbb Z$, on peut écrire comme j'ai dit : $(p-1)u+mv=d$, et en déduire : $(p-1)(u+|u|)+m(v+|v|)=d+(p-1)|u|+m|v|$, et là tout le monde est positif.
    Il faut rester vigilant.
    Bonne soirée
    Fr. Ch.
  • Je ne vois pas en quoi le signe pose problème @Chaurien puisque $1^{u} \equiv 1^{-u} \equiv 1\pmod p$
  • Soit $a$ un entier naturel non divisible par $p$ dont la classe dans $\left(\left(\mathbb{Z}/p\mathbb{Z}\right)^\star,\times\right)$ est d'ordre $n$.
    Si $a^m\equiv 1\mod{p}$ alors $n$ divise $m$ (propriété 1)

    On peut appliquer la propriété 1 en prenant $m=p-1$ (cf. petit théorème de Fermat ou propriété des groupes finis) et si maintenant on prend un autre entier $m'$ qui vérifie cette propriété, $m'$ et $p-1$ sont divisibles par $n$ leur pgcd aussi.


    Or, $a^{kn}\equiv (a^n)^k\equiv 1^k\equiv 1\mod{p}$.

    PS:

    Démonstration du fait que si $n$ est le plus petit élément de l'ensemble $E=\{k \in \mathbb{N}^\star,a^k\equiv 1\mod{p}\}$ avec $p$ un nombre premier et $a$ un entier non divisible par $p$, alors $a^m\equiv 1\mod{p}$ entraîne que $m$ est divisible par $n$.

    $E$ est un sous-ensemble de l'ensemble des entiers naturels il possède un plus petit élément $n$ (qui est non nul puisque $E$ ne contient pas $0$ par définition)

    Si on a $a^m\equiv 1\mod{p}$ pour $m$ entier naturel.

    il existe des entiers naturels $q,r$ tels que $0\leq r<n$ et $m=qn+r$.

    $a^m\equiv a^{qn+r}\equiv a^r\equiv 1\mod{p}$

    On vient de trouver un entier naturel $r$ qui est strictement plus petit que $n$. De part la définition de $n$ cela n'est possible que si $r=0$. Donc $n$ divise $m$.

    PS:

    Je pense que c'est corrigé.
  • @Fdp il ne s'agit pas de deux entiers qui sont divisibles par $n$, mais plutôt du petit théorème de Fermat et d'un entier qui est divisible par $n$.
  • Babsgueye: le petit théorème de Fermat est un cas particulier d'une propriété des groupes finis:

    Si $G$ est un groupe fini d'ordre $n$ et si $g$ appartient à $G$ on a $g^n=e$ avec $e$ l'élément neutre de $G$.

    Le groupe $\left(\left(\mathbb{Z}/p\mathbb{Z}\right)^\star,\times\right)$ ($p$ est un nombre premier) est d'ordre $p-1$.
  • Mais $p -1$ n'est pas divisible par $p$ que je sache.
  • Il y avait des erreurs dans mon message ci-dessus merci de m'avoir fait prendre conscience de ça.

    Ce n'est pas parce qu'on a $a^{p-1}\equiv 1\mod{p}$ que $a$ est nécessairement d'ordre $p-1$ dans $\left(\left(\mathbb{Z}/p\mathbb{Z}\right)^\star,\times\right)$

    Mais si on a $a^m\equiv 1\mod{p}$ alors $m$ est divisible par l'ordre de $a$ dans $\left(\left(\mathbb{Z}/p\mathbb{Z}\right)^\star,\times\right)$

    PS:
    Quand deux entiers sont divisibles par un même entier $d$ alors le pgcd de ces deux entiers est aussi divisible par $d$.
    Tous les nombres entiers $m$ qui vérifient $a^m\equiv 1\mod{p}$ sont divisibles par l'ordre de $a$ dans $\left(\left(\mathbb{Z}/p\mathbb{Z}\right)^\star,\times\right)$ donc si on prend un nombre fini de tels $m$ leur pgcd sera divisible par l'ordre de $a$.
  • Merci Chaurien, Fin de partie et Babsgueye pour vos interventions.

    Chaurien, si tu me tends des pièges, maintenant... :-)

    J'avais immédiatement remarqué que $u$ et $v$ seraient de signes opposés mais cela ne m'a pas inquiétée outre mesure car j'avais un jour remarqué ceci :
    $3^{0}\equiv 3^{(11-1)-0}\pmod{11}$.
    $3^{-1}\equiv 3^{(11-1)-1}\pmod{11}$.
    $3^{-2}\equiv 3^{(11-1)-2}\equiv 3^{8}\pmod{11}$.
    Etc.
    Ainsi, $3^{7}*3^{-2}\equiv 3^{7-2}\equiv 3^{5}\equiv 3^{7+8}\equiv 7^{15}\equiv 1\pmod{11}$.
    L'astuce, c'est de retrancher $0$, $1$, $2$ ... non pas de $11$ mais bien de $\phi(11)$. Je ne sais pas l'expliquer. C'est peut-être l'objet même de vos explications.
    Je reviendrai probablement sur le sujet.

    A bientôt, et, demain, Bon Réveillon à vous !
  • Tu ne sais pas expliquer le fait que $3^{\varphi(11)} \equiv 3^{10} \equiv 1 \text{ mod } 11 \Rightarrow 3^{-1} \equiv 3^9 \text{ mod } 11$ ?
  • Non.
    Ce que je sais, c’est que $3^{-1}$ est l’inverse de $3$.
  • Eh bien ce sont juste les règles des puissances. Multiplie chaque côté de la congruence $3^{10} \equiv 1 \text{ mod } 11$ par $3^{-1}$.
  • Ah, oui, tiens !
    Mais alors, pourquoi s’inquiéter de puissances négatives ?
  • Parce que $3^{-1}$ ne désigne pas la classe de $\frac{1}{3}$ modulo $11$ (ce qui n'aurait pas de sens a priori), mais la classe inverse de la classe de $3$ modulo $11$.
  • Je regrette, mais je maintiens mon point de vue. Il faut savoir de quoi on parle. Au départ, le symbole $\equiv$ désigne une relation d'équivalence dans $\mathbb Z$, et l'égalité que j'ai donnée : $a^d=a^{(p-1)u+mv} \equiv 1\pmod{p}$ n'est donc pas prouvée car sa preuve serait : $a^{(p-1)u+mv} $$=(a^{p-1})^u (a^m)^v \equiv...$, or ces nombres $(a^{p-1})^u$ et $ (a^m)^v$ ne sont plus nécessairement des éléments de $\mathbb Z$, et alors « $...\equiv ...$ » n'a plus de sens.
    On pourrait donner un sens à cette équivalence en la définissant non plus dans $\mathbb Z$ mais dans l'anneau (local) $\mathbb A_p$ des fractions à dénominateur non multiple de $p$. C'est ainsi qu'on peut procéder par exemple pour démontrer un théorème de Wolstenholme.
    Une autre solution, comme j'ai dit plus haut, est de rédiger dans l'anneau résiduel $\mathbb Z /p \mathbb Z$, qui est un corps commutatif, et alors les puissances négatives des éléments non nuls existent.
    Il m'a semblé plus simple de rester dans $\mathbb Z$ en « positivant » les coefficients de Bézout, et je ne vois pas ce qu'on peut objecter à ce procédé.
    Bonne journée.
    Fr. Ch.
  • J’ai bien vu vos messages. Merci
    Je reviendrai bientôt.
    Bon réveillon de Noël !

    [Ajout]
    Sur l’heure de midi, je pense avoir trouvé une démonstration fondée sur des rudiments d’arithmétique modulaire et d’arithmétique élémentaire. (Avec moi, il ne faut pas s’attendre à quelque chose d’élaboré.)
  • Bonsoir,
    Voilà l'idée que j'ai eue hier pour résoudre le problème que j'ai posé huit messages à moi plus haut, c'est à dire ici http://www.les-mathematiques.net/phorum/read.php?5,2148962,2150054#msg-2150054 :

    Puisque $p$ est un nombre premier qui ne divise pas $a$, on peut dire d'après la théorie (Gauss, Recherches arithmétiques, n° 45 et suivants) :
    1) qu'il existe un plus petit entier strictement positif $t$ tel que $a^t\equiv 1\pmod{p}$.
    2) que, pour tout entier naturel $m$, on aura en général $a^{mt}\equiv 1\pmod{p}$ (n° 46).
    3) que, pour un entier strictement positif $k$, si $a^k\equiv 1\pmod{p}$, on aura $k\equiv 0\pmod{t}$, c'est-à-dire que $k$ sera un multiple de $t$ (n° 48).

    Dans le problème posé, puisqu'on a $a^{p-1}\equiv 1 \pmod{p}$ et $a^{m}\equiv 1 \pmod{p}$, il suit que $p-1$ et $m$ sont tous les deux multiples de $t$, qui existe même si on ne le connaît pas. Posons alors : $p-1=\alpha\cdot t$ et $m=\beta\cdot t$ (avec $\alpha$, $\beta$ entiers strictement positifs).

    Maintenant :
    Si $\alpha$ et $\beta$ sont premiers entre eux, alors PGCD$(p-1, m)=$PGCD$(\alpha\cdot t, \beta\cdot t)=t$, et l'on a bien $a^{PGCD(p-1, m)}=a^t\equiv 1\pmod{p}$.
    Si $\alpha$ et $\beta$ ne sont pas premiers entre eux, alors PGCD$(\alpha, \beta)=\gamma$ $(\gamma >1)$ tel que $\alpha=\gamma\cdot \alpha'$ et $\beta=\gamma\cdot \beta'$ (avec $\alpha'$ et $\beta'$ premiers entre eux). De sorte que PGCD$(p-1, m)=$ PGCD$(\alpha\cdot t, \beta\cdot t)=$ PGCD$(\gamma\cdot\alpha'\cdot t, \gamma\cdot \beta'\cdot t)=\gamma t$, et l'on a bien $a^{PGCD(p-1, m)}=a^{\gamma t}\equiv 1\pmod{p}$.

    Cela permet d'éviter la question des exposants négatifs. Je ne sais pas ce que vous en pensez.
  • C'est juste, sauf que c'est fastidieux. L'élément neutre a toujours un inverse, c'est lui même, qu'on soit dans $\mathbb{Z}$ ou dans $\mathbb{Z}/p\mathbb{Z}$.

    PS : de mon téléphone.
  • Fastidieux ?
    Admettons.
    Mais alors, c'est quoi, la méthode simple ?
  • Sneg:

    Une méthode simple pour démontrer que $a^{\text{PGCD}(m,p-1)}-1$ est divisible par $p$ si on a $a^m-1$ est divisible par $p$?

    J'en ai esquissé une plus haut.

    Soit $a$ un entier qui n'est pas divisible par $p$, un nombre premier.

    1)On montre que parmi les nombres entiers non-nuls $m$ qui vérifient $a^m\equiv 1\mod{p}$ il y en a un $n$ qui est plus petit que tous les autres et ce nombre a aussi la propriété que si $k$ est un entier naturel tel que $a^k\equiv 1\mod{p}$ alors $n$ divise $k$.
    Ainsi, si on a deux entiers naturels $m$ et $m'$ tels que $a^m\equiv 1\mod{p}$ et $a^{m'}\equiv 1\mod{p}$ alors $n$ divise $m$ et $m'$ donc il divise leur pgcd.
    L'application du petit théorème de Fermat permet de montrer que $a^{p-1}\equiv 1\mod{p}$

    2) Si $a^k\equiv 1\mod{p}$ alors $(a^k)^l\equiv 1\mod{p}$ avec $l,k$ des entiers naturels. On peut prendre $k=n$ cela permet de conclure la démonstration demandée puisque $\text{PGCD}(m,p-1)$ est divisible par $n$.
  • Sneg a écrit:
    Mais alors, c'est quoi, la méthode simple ?

    C'est que c'est pas la peine de ''s'amerder'' avec tout ça. Dans ce cas précis l'exposant négatif ne pose aucun problème. L'inverse de $1$ c'est $1$.
  • Merci, babsgueye. Cela dit, Chaurien ne semble pas d'accord. Je cherche une solution qui mettrait tout le monde d'accord.

    Merci aussi, Fin de partie, d'avoir répondu à la question que j'ai posée dans mon message précédent.
    Cela dit, je me demande si tu as vu le message que j'ai posté deux messages à moi plus haut. A première vue, nous disons la même chose, à ceci près que tu te contentes d'écrire "... alors $n$ divise $m$ et $m'$ donc il divise leur pgcd", alors que moi je me mets en devoir de démontrer la partie soulignée, que je ne trouve pas évidente à priori. Et pour cela, j'introduis les éléments $\alpha$, $\beta$ et $\gamma$ que tu trouveras sans doute superflus.
  • @ Sneg: j'interviens en espérant ne pas ajouter de la confusion supplémentaire....

    Un peu comme FdP :

    Soit n le plus petit diviseur de p-1 tel que a^n = 1 [p]

    Si m est tel que a^m = 1 [p] alors m = k*n ( j'espère qu'il n'y a pas besoin ici de le démontrer)

    Et comme n est diviseur de p-1, on peut écrire : p-1 = j*n

    PGCD(m, p-1)= PGCD(k*n, j*n ) = b*n, b pouvant valoir 1.

    donc a ^ PGCD(m,p-1) = a ^ (b*n) = ( a ^n ) ^ b = 1 ^ b = 1 [p]
  • C’est d’accord, nodgim. Il n’y a pas du tout de confusion. :-)
    La seule différence entre ta démonstration et la mienne, c’est que j’ai distingué deux cas (selon ta notation) :
    J et k sont premiers entre eux.
    J et k ne sont pas premiers entre eux.
    C’est vrai que cette distinction n’était pas indispensable.
  • OK. J'aime bien ma propre phrase : " ajouter du.... supplément ".

    ça me fait penser aux promotions commerciales, qui annoncent un rabais de -50%. Un rabais de -50%, c'est une hausse de + 50 % ?
  • Nodgim, deux messages à toi plus haut tu as écrit en une seule ligne, sans commentaire :
    « Soit n le plus petit diviseur de p-1 tel que a^n = 1 [p]. »

    Au n°49 de ses Disquisitiones Arithmeticae, Gauss en personne met une page entière pour démontrer que n est un diviseur de p-1.

    Cette remarque pour dire que les choses qui paraissent évidentes aux yeux des mathématiciens d’aujourd’hui ne l’ont pas toujours été et qu’elles restent encore bien compliquées aux yeux des personnes qui ne sont pas mathématiciennes.
    Ce serait bien si les profs de maths pouvaient garder cela à l’esprit.
  • Sneg a écrit:
    Cette remarque pour dire que les choses qui paraissent évident aux yeux des mathématiciens d’aujourd’hui ne l’ont pas toujours été et qu’elles restent encore bien compliquées aux yeux des personnes qui ne sont pas mathématiciennes.

    Sneg si j'ai bien compris tu fais des math (plus précisément de l'arithmétique) pour le plaisir. Pourquoi ne pas lire un cours d'arithmétique qui te permettrait d'acquérir les bases qui rendraient ce genre d'énoncé évident pour toi aussi ?
  • Pour montrer que n, min tel que a^n = 1 [p] je fais comme ça :

    1) les restes sont cycliques et si on part de 1, on revient sur 1. ( cycle car: antécédent unique, nombre de restes limité )
    2) il n'y a pas de 0, donc au max p-1 restes.
    3) si le cycle qui part de1 prend tous les restes c'est fini.
    4) Sinon, un reste manquant dans le cycle qui contient 1 établit un cycle de même longueur, car il suffit de multiplier ce reste pour tous les restes du 1er cycle.
    5) on fait la même chose pour tous les restes manquants.

    Exemple : p = 17 avec a = 2
    cycle du 1 = 1,2,4, 8,-1,-2,-4 -8
    cycle du 3 = 3*1, 3*2, 3*4, 3*8 3*-1, 3*-2, 3*-4, 3*-8 = 3, 6, -5, 7, - 3, -6, 5, -7.

    C'est le fait que, s'il y a plusieurs boucles, elles sont nécessairement de même longueur, que n divise p-1.

    PS: c'est en appliquant cette méthode qu'on se ramasse lamentablement avec la suite Fibonacci modulo p....
  • Grand merci pour tous ces détails, nodgim, mais il ne fallait pas ! Pardonne-moi.
    J’exprimais juste un sentiment, souvenir de mon catastrophique parcours mathématique, à l’école

    Tu as tout deviné, raoul.S.
    À la lecture d’ouvrages de mathématiques, je progresse lentement.:-) Sûrement ? Je ne sais pas.
Connectez-vous ou Inscrivez-vous pour répondre.