Somme di quadrati modulo p

[EvaristeG]

Ecco un lemmino estremamente semplice e stranamente utile.

Mostrare che, comunque assegnato un naturale n e un primo p, esistono x,y tali che
$ x^2+y^2\equiv n (\bmod p) $

Come ho detto, non è nulla di complicato, quindi gli "esperti" si astengano.

[dalferro11]

mmmmh........, ha forse a che fare con la scomposizione di un numero in quattro quadrati?

[EvaristeG]

no!
Ho detto che non era nulla di complicato ... se ci volesse quel teorema (che semplice semplice non è), sarebbe quanto meno difficilotto.

Inoltre, la via più elementare per dimostrare che ogni numero si scrive come somma di 4 quadrati usa proprio questo lemmino.

[EvaristeG]

UP!

[darkcrystal]

Carino... imbianco per sicurezza

n può assumere (mod p) esattamente p valori, mentre $ x^2 $ per un fatto noto ne può assumere $ \frac{p+1}{2} $. Ma allora, facendo variare x tra tutti i valori possibili, $ y^2 $ viene ad assumere $ \frac{p+1}{2} $ valori diversi, ma se nessuno di questi fosse un residuo quadratico si arriverebbe ad un assurdo, in quanto modulo p esisterebbero $ \frac{p+1}{2} $valori che sono residui quadratici e altrettanti che non lo sono, perciò esisterebbero esattamente p+1 valori distinti modulo p, assurdo.
Per quanto riguarda p=2 (che è un po' fuori dagli schemi...) direi che sia vero che la somma di due quadrati possa essere sia pari che dispari.
Ciao!

[EvaristeG]

ok

[HiTLeuLeR]

Mostrare che, comunque assegnato un naturale n e un primo p, esistono x,y tali che $ x^2+y^2\equiv n \bmod p $.

Se $ p = 2 $ oppure $ n $ è un residuo quadratico $ \bmod\;\! p $, la tesi è banale. Altrimenti, sia $ g $ una radice primitiva $ \bmod \;\!p $. Allora esiste $ h = 0, 1, \ldots, (p-1)/2 $ tale che $ n - g^{2h} $ è un residuo quadratico $ \bmod \;\!p $ (piccioni). Two lines is better than one!