Congruence
Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
-
pozor16
- Membre Naturel
- Messages: 34
- Enregistré le: 30 Avr 2006, 18:04
-
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
-
jlb
- Habitué(e)
- Messages: 1886
- Enregistré le: 27 Jan 2013, 18:35
-
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!!
-
pozor16
- Membre Naturel
- Messages: 34
- Enregistré le: 30 Avr 2006, 18:04
-
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
-
Ben314
- Le Ben
- Messages: 21534
- Enregistré le: 11 Nov 2009, 22:53
-
par Ben314 » 01 Déc 2013, 20:51
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
-
jlb
- Habitué(e)
- Messages: 1886
- Enregistré le: 27 Jan 2013, 18:35
-
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?
-
jlb
- Habitué(e)
- Messages: 1886
- Enregistré le: 27 Jan 2013, 18:35
-
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)
-
pozor16
- Membre Naturel
- Messages: 34
- Enregistré le: 30 Avr 2006, 18:04
-
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
-
Ben314
- Le Ben
- Messages: 21534
- Enregistré le: 11 Nov 2009, 22:53
-
par Ben314 » 01 Déc 2013, 21:28
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
-
jlb
- Habitué(e)
- Messages: 1886
- Enregistré le: 27 Jan 2013, 18:35
-
par jlb » 01 Déc 2013, 22:19
et aussi avec 3^25=68 [125]
-
sylvainc2
- Membre Naturel
- Messages: 69
- Enregistré le: 12 Aoû 2012, 19:22
-
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
-
Ben314
- Le Ben
- Messages: 21534
- Enregistré le: 11 Nov 2009, 22:53
-
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é.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 56 invités