residui quadratici

[dalferro11]

Problema:
Dato un intero n>0 determinare il numero di residui quadratici, in altre parole determinare per quanti k la seguente congruenza è risolubile:

x^2 = k (mod n)

[piever]

Chiamiamo $ Q(n) $ il numero di quadrati perfetti modulo $ n $.

Allora, affrontiamo prima le potenze di 2.

$ Q(2^0)=1 $

$ Q(2^1)=2 $

$ Q(2^2)=2 $

Analizziamo ora il caso $ Q(2^j) $ con $ j\geq 3 $

I quadrati dispari sono $ 2^{j-3} $

Sappiamo che il massimo ordine moltiplicativo modulo $ 2^j $ è esattamente $ 2^{j-2} $

Poniamo $ ord_{2^j} (u)=2^{j-2} $

Abbiamo che esistono $ 2^{j-3} $ valori esprimibili come una potenza di $ u $ con esponente pari, che sono dunque quadrati perfetti.

Dimostriamo che non ce ne sono di più:

le basi possibili dispari sono $ 2^{j-1} $ e notiamo facilmente che $ n^2 \equiv (2^{j-1} -n)^2 \equiv (2^{j-1} +n)^2 \equiv (2^j-n)^2 \mod 2^j $ quindi i quadrati sono a quattro a quattro uguali.

Di conseguenza i quadrati perfetti sono al massimo, e quindi esattamente, $ 2^{j-3} $

Ora analizziamo i quadrati con base pari. Dividiamo per 2 la base e per 4 il modulo, e ripetiamo il pocedimento.

Otteniamo facilmente che per i j dispari $ Q(2^j)=\frac {4^{a}-1}{3}+2 $ dove $ 2a+1=j $

Per i j pari $ Q(2^j)=2* \frac {4^{a}-1}{3} + 2 $ dove $ 2a+2=j $

Adesso definiamo $ Q(p^k) $ per ogni primo dispari.

$ Q(p^0)=1 $

$ Q(p^1)=\frac {p-1}{2}+1 $

$ Q(p^2)=\frac {p^2-p}{2}+1 $

Analizziamo il caso $ k\geq 3 $

Ora abbiamo che i quadrati modulo $ p^k $ con base prima con p sono $ \frac {p^k-p^{k-1}}{2} $

Adesso dividiamo il modulo per $ p $ e la base per $ p^2 $ e ripetiamo il procedimento.

Otteniamo che, per $ k $ pari, $ Q(p^k)= p* \frac {p^{k}-1}{2(p+1)}+1 $

Per $ k $ dispari invece $ Q(p^k)= \frac {p^{k+1}-1}{2(p+1)}+1 $

Con il teorema cinese del resto si dimostra facilmente che, dati due interi positivi $ a,b $ se ($ a,b)=1 $ allora $ Q(ab)=Q(a)*Q(b) $

Quindi ora, dato un qualsiasi n, in base alla fattorizzazione di n, siamo in grado di determinare quanti quadrati perfetti distinti esistano in modulo n.

[dalferro11]

La soluzione è esatta...io avevo scritto tutto in forma di sommatoria di funzioni di eulero e un'altra in funzioni per ricorrenza.

[fields]

Oppure si può dare questa formula. Indicando con $ $Q(n)$ $ il numero dei quadrati perfetti modulo n, abbiamo

$ $Q(n)=\frac{\phi(n)}{2^{\alpha}}$ $

per un oppurtuno $ $\alpha$ $che non ho voglia di calcolare

[piever]

Piccola divagazione:

quella formula dà solo i quadrati la cui base è prima con n.

In ogni caso $ \alpha $ è il numero di primi dispari distinti che dividono n addizionato di 2 se 8|n, addizionato di 1 se 4||n, invariato negli altri casi.
Questo valore, $ 2^{\alpha} $, è il numero di distinte basi che ha ciascun quadrato. Sapendo questo si dimostra facilmente il teorema generalizzato di Wilson.

Fine della divagazione