Annuler
connectez vous
- Arithmétique : divisibilité, PGCD et PPCM, Nombres premiers
- Des mathématiciens célèbres : Fermat et Gauss
- Fonction exponentielle - Fiche de Cours terminale
- Le raisonnement par récurrence : principe et exemples rédigés
- Fiche sur les nombres complexes - terminale
- Limites de fonctions - Cours sur les limites
- Cours sur les suites en Terminale S
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques LycéeOn parle exclusivement de maths, niveau lycée. TerminaleForum de terminale ArithmétiqueTopics traitant de Arithmétique [tout]Lister tous les topics de mathématiques
Niveau terminale
système R.S.A. (TS spé)
Posté par cb53
Bonjour,
Je rencontre quelques problèmes sur mon exercice de maths et j'aurais besoin d'aide; voici l'énoncé :
On considère deux nombres premiers p et q très grands et n=pq
On pose m= (p-1)(q-1) et e un entier naturel premier avec m
Pour un nombre entier naturel x donné, on pose y congu à xe (mod pq) soit y congu à xe (mod n)
1) Montrer que l'équation eD-km =1 d'inconnues D et k, admet des solutions et que si (D0; k0) est l'une des solutions particulières, les autres sont (D0 + zm; k0 +ze).
2) En déduire qu'il existe un unique entier d tel que 0 <= d <m et ed congru à 1 (mod m)
3) On suppose que x n'est ni divisible par p ni divisible par q. Que peut-on alors écrire ?
4) Montrer que x(p-1)(q-1) congru à 1 (mod p) et que x(p-1)(q-1) congru à 1 (mod q) en déduire que xm congru à 1 (mod n)
5) Déduire que xed congru à x (mod n) et que x congru à yd (mod n)
Pour la première question j'ai dis que comme e et m sont premiers entre eux alors il existe un couple d'entiers relatifs tel que eD-km=1 d'après le théorème de bézout. Mais je ne sais pas comment faire pour montrer que l'équation admet des solutions et que si (D0; k0) est l'une des solutions particulières, les autres sont (D0 + zm; k0 +ze).
Merci d'avance
tu oublies que e et m sont premiers entre eux
voir cours
tu connais une solution particulière D0 et k0 ...
[rouge][/rouge]
tu oublies que e et m sont premiers entre eux et que c'est un exercice d'arithmétique .
voir cours
tu connais une solution particulière D0 et k0 ...
salut
e.D - m.k = e.Do -m.ko soit
e.(D-Do) = m.(-ko+k) comme e et m sont premier entre eux
alors - ko+k = e.z ---> k = ko + e.z
D-Do = m.z ---> D = Do + m.z
Ah oui merci beaucoup je comprends mieux !
pour la question 2) vu que e et m sont premier alors e=mk+1
et comme d est strictement inférieur à m donc il y a qu'une solution
est-ce bien ou il faut détailler plus ?
pour la 4)
j'ai dis que x(p-1)(q-1) = xm
donc xm congru à 1 et comme p*q =n on peut ecrire : xm congru à 1 mod n
mais il me manque la première partie :/
Je suis désolé mais je n'avait pas compris vos propos contrairement aux siens c'est tout, mais cela ne répond pas à ma question...
Pour la 4, il faut utiliser le petit théoreme de Fermat: xp-1 = 1 mod p si p est premier, et x est premier avec p, et même chose pour xq-1 = 1 mod q.
Ensuite pour la premiere partie de la 5: puisque ed = 1 mod (p-1)(q-1) il existe un entier k tel que ed = 1 + k(p-1)(q-1) donc xed = x1 + k(p-1)(q-1) = x1 xk(p-1)(q-1) = x1 mod (pq) après utilisation de la question 4.