[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[obm-l] residuos quadráticos (ajuda!!!)



Pessoal...
 
Estou com uma dúvida para resolver congruencias do tipo x^2 = a (mod p) onde p é primo impar
 
Primeiro eu faço uma verificação se a é, ou não, um resíduo quadrático modulo p, ou seja, se x^2 = a (mod p) tem solução. Faço isso usando a lei da reciprocidade quadrática e o simbolo de jacobi (ou legendre)...
 
Depois meu problema se resume em duas situações:
 
1) se p = 3 (mod 4)
2) se p = 1 (mod 4)
 
No primeiro caso, é fácil achar a solução utilizando o critério de euler, que diz que se a é um quadrado modulo p, então a^((p-1)/2)=1 (mod p)...
Ou seja a^((p+1)/2) = a (mod p)
Fazendo algumas manipulações cheguei que x = a^((p+1)/4) é solução no caso em que p=3 (mod 4)... note que (p+1)/4 é inteiro
 
Mas no segundo caso (p+1)/4 não é inteiro, pois p=1 (mod 4)... Logo não posso agir da mesma forma...
 
Alguém pode me ajudar a resolver congurencias desse tipo (x^2 = a (mod p), onde p é primo tal que p=1 (mod 4))?????
 
No meio de um exercicio apareceu a seguinte congruência d^2 = 56 (mod 61)... alguém poderia me ajudar????
 
Obrigado!!!



Yahoo! Mail - Participe da pesquisa global sobre o Yahoo! Mail. Clique aqui!