No residui quadratici

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

No residui quadratici

Messaggio da jordan » 17 gen 2009, 11:53

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} $? :wink:
The only goal of science is the honor of the human spirit.

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 19 gen 2009, 16:26

Toh, estremamente interessante...

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

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.
"Sei la Barbara della situazione!" (Tap)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 19 gen 2009, 19:41

Wo ke bello piè :D
rispondo a tutto tranquillo, ma se ti dico la fonte già faresti metà problema :twisted:
e comunque, si, l'enunciato è vero e gli strumenti utilizzati sono tutti olimpici :wink:
ps che fine ha fatto la tua r?troppi topolino? :lol:
The only goal of science is the honor of the human spirit.

piever
Messaggi: 645
Iscritto il: 18 feb 2006, 13:15
Località: Roma
Contatta:

Messaggio da piever » 20 gen 2009, 18:54

jordan ha scritto: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 :P ), 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!
"Sei la Barbara della situazione!" (Tap)

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 20 gen 2009, 19:58

piever ha scritto: se poi viene male è colpa tua :P )
Si vorrei proprio vederla se viene male :D a proposito su che la fai?
piever ha scritto: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 :wink:
The only goal of science is the honor of the human spirit.

Rispondi