[obm-l] Raizes quadradas mod m

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Outro problema que estah me dando trabalho eh o de se calcular o numero de
solucoes da congruencia x^2 == a (mod m), onde a eh um quadrado mod m (se a
nao for quadrado mod m, entao o numero de solucoes eh obviamente zero)

Eu consegui fazer isso no caso em que mdc(a,m) = 1:
Seja m = 2^k*p1^x1*...*pr^xr, a decomposicao de m em fatores primos onde os
pi sao primos impares distintos, k eh um inteiro nao-negativo e os xi sao
inteiros positivos. Entao, o numero desejado eh igual a R(k)*2^r, onde:
R(k) = 1, se k = 0 ou 1
R(2) = 2
R(k) = 4, se k >= 3.

No entanto, estou enrolado no caso em que a nao eh primo com m.

Nem preciso dizer que qualuer ajuda serah muito bem-vinda.

[]s,
Claudio.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================