No residui quadratici

[jordan]

E' vero che dato un primo dispari $ p $ esiste sempre un intero positivo $ a \le [\sqrt{p}+1] $ tale che $ p \nmid x^2-a, \forall x \in \mathbb{Z} $?

[piever]

Toh, estremamente interessante...

Le domande di rito (con i tuoi problemi non si può mai sapere ):

1) da dove viene il problema?

2) L'enunciato è vero o no? (se non vuoi sciupare la sorpresa al pubblico, potresti dirmelo per messaggio privato)

3) Nel caso in cui l'enunciato sia vero, conosci una dimostrazione che usa solo strumenti "olimpici"?

Gvazie pev l'eventuale visposta.

[jordan]

Wo ke bello piè
rispondo a tutto tranquillo, ma se ti dico la fonte già faresti metà problema
e comunque, si, l'enunciato è vero e gli strumenti utilizzati sono tutti olimpici
ps che fine ha fatto la tua r?troppi topolino?

[piever]

che fine ha fatto la tua r?

Non tvovi che la v sia più, come dive, avistocvatica?

Comunque, visto che questo dovrebbe essere un forum di matematica e che ho passato una quantità di tempo inimmaginabile su questo problema (invece di preparare la presentazione di un problema per il Winter - se poi viene male è colpa tua ), forse è il caso che posto una soluzione...

Supponiamo per assurdo che per un qualche primo dispari p la tesi sia falsa:

1) -1 è un residuo quadratico modulo p. Infatti se poniamo $ r=\lfloor \sqrt{p}\rfloor $ e $ s=p-r^2 $ abbiamo che $ -s $ e $ r-s $ sono entrambi residui quadratici (infatti $ s\equiv r^2-p\pmod p $ e $ r-s\equiv r(r+1) \pmod p $ dove, per ipotesi di assurdo, sia $ r $ sia $ r+1 $ sono residui quadratici) e almeno uno tra $ s $ e $ s-r $ è compreso nell'intervallo $ [0,r+1] $ ed è quindi un residuo quadratico. Visto che né s né s-r possono essere congrui a 0 modulo p (altrimenti r|p), abbiamo due residui quadratici il cui rapporto è -1, che è quindi un residuo quadratico.

2) sia q il più piccolo intero positivo che non è un residuo quadratico modulo p. Charamente q<p. Nell'intervallo $ [p-q+1,p] $ c'è almeno un multiplo di q e, visto che $ q\nmid p $ questo vuol dire che nell'intervallo $ [p-q+1,p-1] $ c'è un multiplo di q che chiameremo kq. Visto che $ k<\frac{p}{q}<\sqrt{p}<r+1 $ abbiamo che k è un residuo quadratico, dunque kq è un non residuo quadratico e, visto che -1 è un residuo quadratico, allora anche $ p-kq $ è un non residuo quadratico, ma $ 0<p-kq<q $, assurdo (avevamo supposto che q fosse il più piccolo non residuo quadratico positivo).

Ciau!

[jordan]

se poi viene male è colpa tua )

Si vorrei proprio vederla se viene male a proposito su che la fai?

2) sia q il più piccolo intero positivo che non è un residuo quadratico modulo p. Charamente q<p. Nell'intervallo $ [p-q+1,p] $ c'è almeno un multiplo di q e, visto che $ q\nmid p $ questo vuol dire che nell'intervallo $ [p-q+1,p-1] $ c'è un multiplo di q che chiameremo kq. Visto che $ k<\frac{p}{q}<\sqrt{p}<r+1 $ abbiamo che k è un residuo quadratico, dunque kq è un non residuo quadratico e, visto che -1 è un residuo quadratico, allora anche $ p-kq $ è un non residuo quadratico, ma $ 0<p-kq<q $, assurdo (avevamo supposto che q fosse il più piccolo non residuo quadratico positivo).

Perfetta come sempre direi