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

[Thiago Ferraiol <dizzy_mateca@xxxxxxxxxxxx>]

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!