Olimpíadas ⇒ (Coréia - 2000) Equação

[Hanon]

Mostre que dado um primo qualquer [tex3]p[/tex3], existem inteiros [tex3](x,y,z,w)[/tex3] satisfazendo:

[tex3]x^2+y^2+z^2-wp=0[/tex3].

Com [tex3]0 < w < p[/tex3]

[Ittalo25MOD]

Encontrei esta solução mas não consegui interpretar tudo: Mathematical Olympiads 2000-2001: Problems and Solutions from Around the World

Se [tex3]p=2[/tex3], então dá pra tomar [tex3](x,y,z,w) = (1,1,0,1) [/tex3].
_________________________________________________________________________________________________________________

Se p é ímpar, dá pra tomar que [tex3]-1 [/tex3] é resíduo quadrático módulo p, ou seja, existe b no conjunto [tex3]\{1,2,...,p-1\} [/tex3] tal que [tex3]b^2\equiv -1 \mod(p) [/tex3].
Tomando [tex3](x,y,z) = (b,1,0) [/tex3], sabemos que p divide [tex3]b^2+1^2+0^2 [/tex3].
Também sabemos que b é no máximo p-1, ou seja: [tex3]pw=b^2+1 \leq (p-1)^2 +1 < p^2 [/tex3]
Como [tex3]pw <p^2 [/tex3], basta escolher um w no conjunto [tex3]\{1,2,...,p-1\} [/tex3].
_________________________________________________________________________________________________________________

Agora a parte que não entendi completamente:

Agora se [tex3]-1 [/tex3] não é resíduo quadrático módulo p.

É preciso saber que se p é primo ímpar, então no conjunto [tex3]\{1,2,3,...,p-1\} [/tex3] existem [tex3]\frac{p-1}{2}[/tex3] resíduos quadráticos módulo p e [tex3]\frac{p-1}{2}[/tex3] não resíduos quadráticos módulo p.

Olhando para os números [tex3]a[/tex3] e [tex3]p-1-a[/tex3] no conjunto [tex3]\{1,2,3,...,p-1\} [/tex3].

Se [tex3]\frac{p-1}{2}[/tex3] é resíduo quadrático, então bastar tomar [tex3]a = \frac{p-1}{2}[/tex3]. (Por que?)

Se [tex3]-1 [/tex3] e [tex3]\frac{p-1}{2}[/tex3] não são resíduos quadráticos, então existem [tex3]\frac{p-1}{2}-2 = \frac{p-5}{2}[/tex3] números que não são resíduos quadráticos.

Separando em [tex3]\frac{p-3}{2}[/tex3] conjuntos com números daquela forma:

[tex3]\{1,p-2\}, \{2,p-3\}, \{3,p-4\},...,\{\frac{p-3}{2},\frac{p+1}{2}\}[/tex3].

Se [tex3]\frac{p-5}{2}[/tex3] não resíduos quadráticos, então nesses [tex3]\frac{p-3}{2}[/tex3] conjuntos existe pelo menos um conjunto com 2 números que são resíduos quadráticos. (Princípio da casa dos pombos)

Então é sempre possível tomar [tex3]\begin{cases}
x^2\equiv a \mod(p) \\
y^2\equiv p-1-a \mod(p)
\end{cases}[/tex3] e z = 1

E isso vai ficar no intervalo [tex3](0,p^2) [/tex3] (Por que?)