Voila j'ai un DM sur le systeme RSA, et je bute sur une question, alors si quelqu'un pouvait m'aider:  
e est un entier naturel, premier avec (p-1)*(q-1) (sachant p et q deux nombres premiers distinct)
 
Demontrer que l'on peut choisir deux entiers naturels d et k tels que de = k (p-1)(q-1)+1
 
Si quelqu'un a un coup de genie merci ( ou s'il a deja fait l'activité: specialité math TS, collection hyperbole, act5p79)

Application directe du cours : théorème de Bezout !!!

a putain merci jercmoi, meaculpa pour ce topic!honte a moi! le probleme c'est que c'a fait trois moi qu'on a pas touchée a sa donc ca a du mal a revenir.
 
si ta une autre idée dans le genre, on a prouvé pour a premier avec n=p*q, puis pour a=r*p, r entier naturel <q (donc a<n) que a^(k(p-1)(q-1)+1) est congru a a modulo n.
 
il faut maintenant le prouvé pour tout entiers naturels a et k

Y'aurait pas un petit théorème de Fermat qui traîne : a^n congru à a modulo n ssi a et n sont premier entre eux ???

le probleme c'est que pour tout entier a, et bah a et n ne sont pas premier entre eux.  
et d'ou tu sors que n=k(p-1)(k-1)+1???

Quelles sont tes hypothèse exactes ? a premier avec p, q et n ?

dans un premier temps on a prouvé pour a premier ac n dc avec p et q, puis apres avec a=r*p,r entier natuerl <q
 
l'enoncé exacte  
question etude de fonctionnemet 3)

Tu as réussi à démontrer la première partie de la question 2-c) : a^(q-1) congru à 1 mod(q) et a^(k(p-1)(q-1) congru à 1 mod(q) ? Si tu as réussi à le faire, la suite me semble simple.
Tu es bloqué sur quelle question exactement ? la 3, ou avant ?

j'ai tout fait sauf la 3 mais te prends pas la tete pour rien, si il me manque une question c'est pas grave (merde alors, sa voudrait dire que j'ai fait le topic pour rien? )

je suis en train de faire la 3. je vais te guider. je la finis juste avant pour avoir le raisonnement complet.

On va pour l'instant se restreindre au cas a<n. On verra à généraliser (c'est très facile) après.
Il y a plusieurs cas :
- soit a et n sont premiers entre eux : déjà traité,
- soit a et n ne sont pas premiers entre eux, on a encore 2 cas :
  * soit p divise a : déjà traité
  * soit q divise a : les résultats de la question 2 restent vrais, en remplacant p par q. On débouche au même résultat (assez évident).
Maintenant, la généralisation : si a>=n, alors a est de la forme a = c*n + d*a', où a'<n. Comme on raisonne modulo n, le résultat est immédiat (on est rammené au cas précédent).
 
ca te semble correct ?

j'avais pensée pour le *soit q divise a mais j'avais plus pensée que p et q etaient premier donc je metais dit que cela n'allait pas, mais en fait si!
pour la generalisation, pourquoi le d devant a'?
 
En tout cas, c'est comme toujours avec la spé, quand tu connais le resultat ca semble evident!Sinon tu fais koi comme etude pour avoir 21ans et te rappeler du programme de spé maths de term?

Tu as raison, le d devant le a' n'a pas de raison d'être. Pour répondre à ta question, je suis à la fac après deux ans de prépa (MPSI puis MP), donc les maths ...

ok je comprend alors!En tout cas merci beaucoup

Pas de problème, et en plus ça me permet d'entretenir mes acquis et de ne pas tout oublier (car je ne fais plus des choses comme ça à la fac ... )

En meme temps si t'en a pas besoin!Tu doit apprendre plein de choses aussi interessante.Tiens au fait c'est quoi comme fac?

La fac d'Orsay (Paris Sud), et je suis en licence d'électronique.

en effet j'imagine que des congruences tu doit pas en faire tous les jours!

Effectivement ...

Je crois on va arreter de parlé sinon on va bientot nosu dire que le forum n'est pas un chat! Encore merci, pi la prochaine fois j'ai un probleme je t'attend!lol