Congruences mod n

[invite72334b6e]

Bonjour,

Soit n = 53 * 67 = 3551
On a :
2^10 = 17 mod 53
2^64 = 17 mod 67

Comment trouver x tel que 2^x = 17 mod n ?


Merci d'avance.
-----

[Amanuensis]

Bonjour,

Je (et d'autres) pourrais fournir le résultat, mais si c'est un exercice, il est d'abord demandé d'indiquer où on bloque exactement...

[invite72334b6e]

En fait, j'aimerai exprimer x en fonction de la puissance 10, et x en fonction de la puissance 64. Une fois ces équations obtenues, je pense que le résultat s'obtient assez facilement.
Mais je bloque sur le fait de trouver ses équations justement.

[Amanuensis]

La procédure que j'applique passe par les valeurs de x modulo 52 et modulo 66. Est-ce que cela vous dit quelque chose ?

[Est-ce un exercice ? Et si oui, quel niveau ?]

[A voir en vidéo sur Futura]

[invite72334b6e]

Non. Pourquoi prendrai t-on modulo 52 et 66 au lieu de 53 et 67 ?

Je pensais poser : 2^x = 2^x * (2^52)^a mod [53] et 2^x = 2^x * (2^66)^a mod [67]
mais cela ne m'avance guère.

[Amanuensis]

Non. Pourquoi prendrai t-on modulo 52 et 66 au lieu de 53 et 67 ?

Ce que vous écrivez juste après en donne la raison !

[invite72334b6e]

On aurait donc : x = 10 + a52 mod 53 et x = 64 + b66 mod 67
Mais comment trouver a et b à partir de ceci ? sachant que les modulo sont différents.

[Amanuensis]

On aurait donc : x = 10 + a52 mod 53 et x = 64 + b66 mod 67

Non, on x=10 mod 52 et x=64 mod 66

[invite72334b6e]

D'accord donc x = 10 + a52 et x = 64 + b66, on trouve a et b et on en déduit x.

Mais je ne comprend pas pourquoi x = 10 mod 52 ?

[Amanuensis]

Mais je ne comprend pas pourquoi x = 10 mod 52 ?

Parce que 2^52=1 modulo 53, donc savoir que 2^x=2^10 modulo 53 détermine x à un multiple de 52 près. (Et faut vérifier aussi que 2^26 n'est pas égal à 1 modulo 53, ce qui est le cas.)

Et le 52 c'est 53-1 parce que 53 est premier (petit théorème de Fermat).