Congruence

par **pozor16** » 01 Déc 2013, 20:12

Bonjour à tous,

Voila je dois résoudre le problème suivant : Résoudre

(mod 125) mais je n'y arrive pas.

Les symboles de Legendre nous permettent de dire si -1 est un carré dans Z/125Z mais ne nous donne pas les solutions non? Que faire alors?

Merci d'avance pour votre aide

par **jlb** » 01 Déc 2013, 20:19

pozor16 a écrit:Bonjour à tous,

Voila je dois résoudre le problème suivant : Résoudre (mod 125) mais je n'y arrive pas.

Les symboles de Legendre nous permettent de dire si -1 est un carré dans Z/125Z mais ne nous donne pas les solutions non? Que faire alors?

Merci d'avance pour votre aide

euh, un ptit programme!! tu n'as que 125 valeurs à essayer mais bon comme 125=5^3, on doit pouvoir trouver une feinte!!

par **pozor16** » 01 Déc 2013, 20:22

jlb a écrit:euh, un ptit programme!! tu n'as que 125 valeurs à essayer

je sais ahah j'y ai pensé mais je dois avouer ne pas avoir la motivation pour le faire lol. Je pense également qu'une solution plus générale existe et me permettrait de faire face à l'éventualité d'être confronté à un nombre un peu plus grand que 125 dans le futur ;-)

par **Ben314** » 01 Déc 2013, 20:51

Effectivement, ça marche avec x=2 :

par **jlb** » 01 Déc 2013, 20:59

salut, j'ai pensé à cela mais je ne sais pas si cela donne qlqchose: si x est une solution du pb modulo 125 alors x est solution du pb modulo 5, cela réduit bien le nombre de valeur à tester, non?

par **jlb** » 01 Déc 2013, 21:08

deux classes solutions 57 et 68 uniquement: 2+5*11 et 3+5*13 ( une solution du pb modulo 125 doit être une solution du pb modulo 5)

par **pozor16** » 01 Déc 2013, 21:09

Ben314 a écrit:Sinon, un truc à essayer, c'est d'utiliser le fait que donc pour tout x inversible de Z/125Z, tu as d'où et, si tu as du pot et que alors vérifie .
Aprés, les calculs de "grosses" puissance comme ça, tu les fait en utilisant et ce qui fait que tu as en faisant seulement 7 multiplications modulo 125 :
: 2 multiplications
: 1 multiplication
: 1 multiplication
: 2 multiplications
: 1 multiplication

Tout ça pour dire qu'à ta place, je "tenterais" , si ça marche pas, je "tenterais" etc : tu devrais trouver vite vu qu'il est fort probable que

C'est intéressant. Ca fait une sorte de dichotomie.

Merci ;-)

par **Ben314** » 01 Déc 2013, 21:28

Effectivement, ça marche avec x=2 :

par **jlb** » 01 Déc 2013, 22:19

Ben314 a écrit:Effectivement, ça marche avec x=2 :

et aussi avec 3^25=68 [125]

par **sylvainc2** » 02 Déc 2013, 20:13

Pour résoudre x^2 = y mod p^k, si p est premier > 2, et si on connait les solutions mod p, alors on peut utiliser la méthode appelée "Hensel lifting" pour trouver les solutions mod p^k:

Soit une solution x1 de x1^2 = y mod p, on cherche x2 telle que x2 ^2 = y mod p^2

On pose x2 = x1 + ap, et on substitue x2:
(x1 + a p)^2 = y mod p^2 --> x1^2 + 2 x1 a p + a^2 p^2 = y mod p^2

On substitue a^2 p^2 = 0 mod p^2 et on réarrange:

2 x1 a p = y - x1^2 mod p^2

On connait x1, y et p donc on peut résoudre pour a, puis on calcule x2. Ensuite pour passer à mod p^3 on remplace p^2 par p^3 et p par p^2, et x2 par x3 et x1 par x2 etc..

Donc pour x^2 = -1 mod 125, on commence par x1^2 = -1 mod 5 --> x1=2 et on résoud 2 x1 a p = y - x1^2 mod p^2:
2*2*a*5 = -1 - 4 mod 25
20a = -5 = 20 mod 25
a=1 donc x2 = 2+ 1*5 = 7, effectivement 7^2 = -1 mod 25

Ensuite pour mod 125:
2*7*a*25 = -1 - 49 mod 125
350a = -50 = 75 mod 125
a=2 donc x3 = 7 + 2*25 = 57 et 57^2 = -1 mod 125

Les racines carrées viennent par paire, 57 se trouve dans l'intervalle [1..62], et 57+5=62 donc l'autre racine correspondante dans [63..124] est 63+5=68

par **Ben314** » 02 Déc 2013, 23:35

Effectivement, dans le cas d'une puissance d'un (petit) nombre premier, c'est ce qui semble le plus adapté.

Congruence

congruence

Qui est en ligne