Re: E o Jacobi?

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Sat, 28 Aug 1999, Eduardo Casagrande Stabel wrote:

> Gostaria de saber como se descobre facilmente o numero de solucoes,
  de a = x^2 + y^2. E se for tao simples assim. Pergunto, quantas solucoes
  existem para 27625 = x^2 + y^2? Sendo x e y numeros inteiros.

Só a resposta, sem demonstração completa
Você está procurando todos os números complexos x + iy
com x e y inteiros e |x+iy|^2 = a.
Chamemos |x+iy|^2 de norma de x+iy.

O conjunto Z[i] dos números complexos da forma x+iy, x e y inteiros,
chamados de inteiros de Gauss, admite um teorema de fatoração única
semelhante ao que todos vocês conhecem em Z: todo número pode ser fatorado
de forma única como produto de primos (sem levar em conta a ordem).

Em Z[i] os primos são:

1+i (norma 2)
3, 7, 11, 19, 23, 31, ... (os primos em Z da forma 4k-1;
                           estem têm normas 3^2, 7^2, 11^2, ...)
2+i, 2-i, 3+2i, 3-2i, 4+i, 4-i, 5+2i, 5-2i, ...
                          (cada primo de Z da forma 4k+1 se fatora
                           em Z[i] como um produto de dois primos
                           distintos, como 5 = (2+i)(2-i),
                           13 = (3+2i)(3-2i), ... 
                           As normas destes primos são 5, 5, 13, 13, ...)

O número que você deu é 27625 = 5^3 * 13 * 17.
Existem em Z[i] dois primos de norma 5 (2+i e 2-i)
e devemos tomar três deles, contando com multiplicidades.
Há portanto aqui 4 escolhas possíveis.
Também existem dois primos de norma 13 (3+2i e 3-2i)
e dois de norma 17 (4+i e 4-i), e temos duas possibilidades
em cada caso.
Finalmente, podemos multiplicar a resposta final por 1, i, -1 ou -i
sem alterar a norma ou a fatoração.
Existem portanto 4*2*2*4 = 64 soluções:

                                 -101 + 132 I

                                 -132 - 101 I

                                  101 - 132 I

                                  132 + 101 I

                                  -27 + 164 I

                                  -164 - 27 I

                                  27 - 164 I

                                  164 + 27 I

                                  83 + 144 I

                                  -144 + 83 I

                                  -83 - 144 I

                                  144 - 83 I

                                  141 + 88 I

                                  -88 + 141 I

                                  -141 - 88 I

                                  88 - 141 I

                                  45 + 160 I

                                  -160 + 45 I

                                  -45 - 160 I

                                  160 - 45 I

                                  115 + 120 I

                                 -120 + 115 I

                                 -115 - 120 I

                                  120 - 115 I

                                  165 + 20 I

                                  -20 + 165 I

                                  -165 - 20 I

                                  20 - 165 I

                                  155 - 60 I

                                  60 + 155 I

                                  -155 + 60 I

                                  -60 - 155 I

                                  155 + 60 I

                                  -60 + 155 I

                                  -155 - 60 I

                                  60 - 155 I

                                  165 - 20 I

                                  20 + 165 I

                                  -165 + 20 I

                                  -20 - 165 I

                                  115 - 120 I

                                  120 + 115 I

                                 -115 + 120 I

                                 -120 - 115 I

                                  45 - 160 I

                                  160 + 45 I

                                  -45 + 160 I

                                  -160 - 45 I

                                  141 - 88 I

                                  88 + 141 I

                                  -141 + 88 I

                                  -88 - 141 I

                                  83 - 144 I

                                  144 + 83 I

                                  -83 + 144 I

                                  -144 - 83 I

                                  -27 - 164 I

                                  164 - 27 I

                                  27 + 164 I

                                  -164 + 27 I

                                 -101 - 132 I

                                  132 - 101 I

                                  101 + 132 I

                                 -132 + 101 I

>    Congruencia
> Tenho uma duvida. Seja a = b (mod n), entao aa' = bb' (mod n)
  se e somente se a' = b' (mod n)?

Isto é verdade se a e n forem primos entre si, mas em geral é falso.

http://www.mat.puc-rio.br/~nicolau