Démontrer qu'une fonction est bijective et définir sa réciproque

Bonjour amis Mathforeux.

Oui, je sais, je n'aurais pas dû donner le titre en langue anglaise.
Aussi j'implore les intervenants de proposer leur(s) solution(s) en français.

Voilà le problème :
Soit E l'ensemble des entiers naturels de 0 à 526 (0 et 526 inclus).
Soit f l'application de E dans E définie par :
f(x) ≡ $x^{77}$ [modulo 527]
Démontrer que f est bijective et définir sa réciproque.

Bonne chance à tous.

Pour l'aspect pragmatique.

print sorted([(x**77)%527 for x in range(527)])==sorted(range(527))

shloub@shloub-laptop:~$ python math.py
True

Peut-être, mais je ne comprends pas.
Peux-tu traduire ?

range(527) c'est E.
D'un côté je prends la liste des (x**77)%527 pour tout x de E, de l'autre E.
Pour vérifier l'égalité des ensembles, je trie les deux listes et demande si l'égalité est vérifiée.
La réponse est oui en une fraction de seconde.

En termes mathématiques, si je comprends bien, tu vérifies que f(E) = E ?
Dans ce cas, tu prouves seulement que f est surjective.

De plus, un programme informatique constitue à mes yeux une simple vérification, pas une démonstration mathématique : il me suffit pour cela de remplacer 527 par une lettre, par exemple n, vérifiant certaines conditions.

Enfin, tu ne définis pas la réciproque.

Je pense que tu as compris l'idée.
f(E)=E montre entre autres que j'ai 527 images différentes pour 527 valeurs différentes, il me semble que ça définit une bijection discrète.

Informatique ou non, l'énumération est une preuve comme une autre. Je peux réaliser les même calculs à la main (ce sera -légèrement- plus long). Tu veux peut-être expliciter ces conditions pour que l'énumération naïve ne soit plus possible.

Je peux définir la réciproque de la même manière (je ne suis pas sûr qu'elle te plaise, elle est peu compacte).

l=sorted([((x**77)%527,x) for x in range(527)])
for i in l:
print "f("+str(i[0]).replace("L","")+")="+str(i[1])

http://pastebin.com/RE08bk8V

Bref, pour définir la réciproque, tu lis la table "à l'envers".
Ce n'est pas exactement ce que j'entendais par "définir".
Citation
Tu veux peut-être expliciter ces conditions pour que l'énumération naïve ne soit plus possible.Bon, je modifie mon énoncé :
Soit p et q deux entiers premiers impairs, et soit n = p.q.
Soit u un inversible de Z/φ(n)Z .
Soit f de Z/nZ dans lui-même, définie par f(x) = $x^u$
Démontrer que f est bijective et définir sa réciproque .
Tu as reconnu un codage RSA, (d'où le titre), mais il y a un petit piège.

J'ai en effet du mal à voir le piège.

Le codage est basé sur le théorème de Fermat-Euler, qui impose que x soit premier avec n.
f définit donc une bijection de (Z/nZ)* sur lui-même.
Il faut démontrer que c'est quand même une bijection de Z/nZ sur lui-même.

On traite ce cas particulier à l'aide du théorème des restes chinois si je me souviens bien.

(Pardon pour le double-post.)

Citation
On traite ce cas particulier à l'aide du théorème des restes chinois si je me souviens bien.Je ne vois pas bien comment : peux-tu détailler ?

Je t'avoue que je n'ai pas envie de détailler énomément, mais je crois que l'on montre n=0 mod pq <=> n=0 mod p et n=0 mod q.
Un sens est plus facile que l'autre, cela dit je crois que c'est assez direct avec l'isomorphisme Z/pqZ -> à (Z/pZ)*(Z/qZ) exhibé par ce fameux théorème.

Puisque n = p.q, on a évidemment n ≡ 0 modulo pq (ou modulo n)
De plus, n étant multiple de p, on a n ≡ 0 modulo p (pareil pour q).
Je ne vois pas bien ce que tu souhaites établir avec le théorème chinois.
J'espère que la notation (Z/nZ)* ne t'abuses pas :
il ne s'agit pas de Z/nZ {0} mais de l'ensemble des inversibles de Z/nZ.
Ainsi, Z* = {+1 ; -1}

Pardon, la lettre n était mal choisie, je crois qu'il s'agit plutôt de ton x en l'occurrence.

Ah. Mais pas besoin du théorème chinois.
si x n'est pas premier avec n, c'est soit un multiple de p, soit un multiple de q. Donc congru à 0 modulo p ou q.
Excuses-moi, mais pour le moment tu n'as rien démontré.
Peut-être pourrais-tu commencer par définir ce que pourrait être la réciproque de f ?

x -> x^(u⁻¹ mod (p-1)(q-1)) mod n ?

Exact.
Mais cela n'est valable que si x est premier avec n.
Tu dois donc établir le résultat lorsque x n'est pas premier avec n.
En d'autres terme, si tu notes v l'inverse de u modulo (p-1)(q-1), tu dois démontrer que $x^{uv}$ ≡ x modulo n , même dans ce cas.

Comme dit précédemment, si x n'est pas premier avec n, il est multiple de p ou q.
Par le théorème des restes chinois on peut vérifier la congruence en n par celle en p et celle en q. L'une des deux est évidente (les deux côtés sont multiples de p (ou q)). Pour l'autre on peut décomposer la puissance et obtenir le résultat de manière similaire à la démonstration via le théorème de Fermat.

Je ne vois pas.
Le théorème chinois établit l'isomorphisme entre le groupe multiplicatif (Z/nZ)* et (Z/pZ)× (Z/qZ)
Mais quel rapport avec la question posée où le but est précisément de se débarrasser des étoiles ?

Démontrer a = c mod(pq) revient à démontrer a=c mod(p) et a=c mod(q), je pense que c'est là l'intérêt de ce théorème.

Ce que tu dis est vrai, mais excuse mon ignorance, je ne vois pas le rapport avec la question posée :
"si tu notes v l'inverse de u modulo (p-1)(q-1), tu dois démontrer que $x^{uv}$ ≡ x modulo n , même lorsque x n'est pas premier avec n."

« démontrer que xuv ≡ x modulo n» est décomposable par ce moyen.

Peux-tu détailler ?
Je t'en serai reconnaissant.
P.S : faute de frappe : c'est évidemment $x^{uv}$ et pas xuv

Démontrer a = c mod(pq) revient à démontrer a=c mod(p) et a=c mod(q), je pense que c'est là l'intérêt de ce théorème.

a vaut x^(uv), c vaut x et n vaut pq donc on a
« démontrer que x^(uv) ≡ x modulo n» revient à démontrer que x^(uv) ≡ x modulo p et x^(uv) ≡ x modulo q, non ?

Exact, et comment démontrer que $x^{uv}$ ≡ 0 modulo p ?

Je dois avouer ne plus me souvenir cette partie.

Ce n'est pas urgent puisqu'il s'agit d'une énigme (dont je connais la réponse).
Toutefois, il est intéressant de réussir cette partie du problème, car c'est précisément là qu'est l'os hélas.
Tant que x est premier avec n, le résultat découle immédiatement du théorème de Fermat-Euler.
Mais il faut réussir à répondre à la question dans le cas où x n'est pas premier avec n, sinon adieu la bijection.

p étant premier, tout x est soit premier avec p soit multiple de p ?

Oui.

Dans un cas on peut utiliser Fermat, dans l'autre c'est évident ?

Fermat pour x non premier avec n (par exemple multiple de p) ?
Tu as donc $x^p$ ≡ x modulo p (mais pas modulo n).
Je te rappelle que c'est $x^{uv}$ qu'il faut calculer.

Mais on a uv - 1 = k(p - 1) comme p est premier.

Ce qui donne $x^{uv}$ = $x^{1+k(p-1)}$ = x. $x^{k(p-1)}$
Mais rien ne prouve que $x^{k(p-1)}$ ≡ 1 modulo n (ni même modulo p)

Si, m^(p-1) est congru à 1 modulo p par le théorème de Fermat.

C'est quoi m ?
De toute façon, m^(p-1) ≡ 1 modulo p à condition que m soit premier avec p.
Le piège est là.
Ici, x n'est pas premier avec p .

x, pardon.

p étant premier, tout x est soit premier avec p soit multiple de p

On est justement ici dans le cas où x est premier avec p (l'autre étant direct).

Non, tu mélanges apparemment.

Si x est premier avec n, il est premier avec p et avec q.
Et dans ce cas, le théorème de Fermat-Euler (qui n'est pas exactement le théorème de Fermat) indique que $x^{uv}$ ≡ x modulo n.
Terminé pour ce cas.

Si par contre x n'est pas premier avec n, c'est soit un multiple de p, soit un multiple de q (soit des deux), et dans ce cas le th de Fermat-Euler ne s'applique pas.
On a donc supposé que x était multiple de p (si on sait le faire pour p, on sait le faire pour q).
Mais alors, on n'a pas $x^{k(p-1)}$ ≡ 1 modulo p.

Je vais maintenant me déconnecter car à mon âge on ressent vite la fatigue.
On pourra continuer plus tard si tu le souhaites.
Bonne soirée.

Si x est multiple de p, x^(uv) ≡ 0 modulo p me paraît assez évident.

Citation
Si x est multiple de p, x^(uv) ≡ 0 modulo p me paraît assez évident.Évidemment, modulo p, mais modulo n ???