Nombres premiers avec (p-1)(q-1)

Bonjour,

Je n'arrive pas à démontrer la propriété suivante :

Si $p$ et $q$ sont deux nombres premiers, alors il existe un nombre $e$ premier avec $(p-1) (q-1)$ tel que : $1 < e < (p-1) (q-1)$

J'ai appliqué Bézout en utilisant le fait que les nombres $p$ et $q$ sont premiers, mais je n'arrive pas à me ramener à $(p-1) (q-1) $.
Avez-vous une idée qui pourrait m'aider ?
Merci

Réponses

  • il suffit surement de les compter
    A demon  wind propelled me east of the sun
  • Le résultat est faux, j'ai un contre-exemple.
  • c'est sur qu'avec p = q = 2
    A demon  wind propelled me east of the sun
  • Trop facile, j'ai un autre contre-exemple.
  • 2 et 3.
  • 23 et -19 ?

    e.v.
    Personne n'a raison contre un enfant qui pleure.


  • ev, tu triches.
    Sans blague, il paraît plus sérieux de montrer que pour tout entier $n\geq 3$, il existe un entier $e$ premier avec $n$ tel que $1<e<n$ (j'en ai un en stock !).
  • Bu, je parie que c'est n-1, non ?!
  • What else ?
  • Effectivement , p et q sont > 3.

    Cela dit, cela ne m'aide pas vraiment .
    Les compter comment ? On ne connaît rien sur les nombres premiers dans le cas général.

    Cordialement
  • As-tu seulement réfléchi à la façon dont j'ai reformulé la question ? Clairon a trouvé sans problème, elle ! (:D
  • Voila ma démonstration :

    Pour tout entier n, il existe un entier e premier avec n tel que : 1 < e < n

    - Si n est premier c'est évident , tout nombre strictement inférieur à n est premier avec n.
    - Si n n'est pas premier , n se décompose en :
    n = p1n1x p2n2x ... pknk
    Tout nombre compris entre p1 et p2 convient alors.

    Est-elle correcte ?

    merci
  • jeremyjeff,

    Et $n-1$ et $n$, ça n'évite pas une démo générale, puisqu'on veut juste "il existe un...."!


    Cordialement, sk.
  • Jeremyjeff,
    Pour tout entier n, il existe un entier e premier avec n tel que : 1 < e < n

    Bizarre ! 1 est un entier.

    De plus tu semble confondre "n est premier" avec "n est premier avec ...". Du coup, la solution évidente qui t'a été proposée n'a pas fait tilt.

    Cordialement.
  • OK, je n'ai pas fais attention aux bornes.
    Un raisonnement par récurrence semble convenir.

    Je cherchais un démonstration plus jolie...
  • Pas besoin d'une récurrence !!

    Tu ne vois pas un nombre simple premier de façon évidente avec (31-1)(2003-1)=60060 ?
  • 8-)
    J'ai l'impression que tu passes complètement à côté de la plaque. Fais un "Ctrl-reset", et reprends les choses calmement en essayant de comprendre ce qui t'a été dit (ne tiens pas compte de la première réponse de "gilles benson"), en particulier la réponse que skyrmion a eu la faiblesse de te donner.
  • Ok, je viens de comprendre .
    On s'en sort avec : n - (n-1) = 1 et un certain Bez...
  • Oui,

    ou même avec le pgcd.
  • Bonjour,

    J'essaie de démontrer les formules de l'algorithme RSA, basé sur le théorème de Fermat.

    "Soient p et q deux nombres premiers distincts et >= 3.
    On pose : n = pq . Soit m un entier vérifiant : 0 <= m < n

    1°) Montrer qu’il existe au moins un entier e premier avec (p-1)*(q-1) et vérifiant : 1< e < (p-1) (q-1) .
    2°) Montrer qu’il existe un unique entier d vérifiant : ed congru à 1 modulo (p-1)*(q-1) et 1 <= d < (p-1) * (q-1) .
    3°) Montrer que med est congru à m modulo n, en montrant d’abord cette égalité modulo p et q."


    J'ai réussi à demontrer les questions 1°) et 2°) , je bloque pour la question 3°)
    Pour le 3°), j'arrive à : med = m * ( m (p-1)*(q-1) ) k
    Et là je bloque.
    je sens qu'on peut utiliser Fermat, mais je ne suis pas dans les hypothèses de Fermat.

    Avez-vous un indice ?

    Merci
  • Bonjour,

    J'essaie de démontrer les formules de l'algorithme RSA, basé sur le théorème de Fermat.

    "Soient p et q deux nombres premiers distincts et >= 3.
    On pose : n = pq . Soit m un entier vérifiant : 0 <= m < n

    1°) Montrer qu’il existe au moins un entier e premier avec (p-1)*(q-1) et vérifiant : 1< e < (p-1) (q-1) .
    2°) Montrer qu’il existe un unique entier d vérifiant : ed congru à 1 modulo (p-1)*(q-1) et 1 <= d < (p-1) * (q-1) .
    3°) Montrer que med est congru à m modulo n, en montrant d’abord cette égalité modulo p et q."

    J'ai réussi à démontrer les questions 1°) et 2°) , je bloque pour la question 3°)
    Pour le 3°), j'arrive à : med = m * ( m (p-1)*(q-1) ) k
    Et là je bloque.
    je sens qu'on peut utiliser Fermat, mais je ne suis pas dans les hypothèses de Fermat.
    Avez-vous un indice ?
    Merci

    [Inutile d'ouvrir une nouvelle discussion pour la suite de ton problème ! AD]
  • "J'ai réussi à demontrer les questions 1°)"
    Ce fut dur ;)

    Pour ta question : quel est l'ordre du groupe multiplicatif (des éléments inversibles) de $\Z/n\Z$ ? (Le théorème chinois peut être utile).
  • Ok, avec le théorème de Lagrange et l'ordre du sous groupe qui divise l'ordre du groupe, on peut le montrer de manière triviale.
    Mais peut-on le démontrer uniquement avec des notions de lycée ?

    Merci
Connectez-vous ou Inscrivez-vous pour répondre.