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

[Fábio Dias Moreira <fabio@xxxxxxxxxxxxxxxxxxx>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Thiago Ferraiol <dizzy_mateca@yahoo.com.br> said:
> Pessoal...
>
> Estou com uma dúvida para resolver congruencias do tipo x^2 = a (mod p)
> onde p é primo impar
> [...]
> No meio de um exercicio apareceu a seguinte congruência d^2 = 56 (mod
> 61)... alguém poderia me ajudar????
> [...]

As únicas propriedades que você precisa saber para calcular um símbolo de 
Legendre são as seguintes:

* (ab/p) = (a/p)(b/p) se (a, b) = 1;
* (a^2*b/p) = (b/p);
* (p/q)(q/p) = (-1)^[(p-1)(q-1)/4] se p e q são primos ímpares;
* (-1/p) = (-1)^[(p-1)/2] se p é primo ímpar;
* (2/p) = (-1)^[(p^2-1)/8] se p é primo ímpar;

Note que 56 = 2^2*14. Então

(56/61) = (14/61) = (2/61)*(7/61) = (-1)*(61/7) = (-1)*(5/7) = -(7/5) = -(2/5) 
= 1.

Se você quiser ver demosntrações dos fatos acima, o livro do Plínio de Teoria 
dos Números, editado pela SBM, é uma boa referência.

[]s,

- -- 
Fábio Dias Moreira
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.3 (GNU/Linux)

iD8DBQFAzn1BalOQFrvzGQoRAjDYAJ4uLHCrRJmVO/ycntCVvzvFWClr3QCfagRy
o41Vi2y2wNjozmkHf783dZo=
=QD0D
-----END PGP SIGNATURE-----


=========================================================================
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
=========================================================================