Pagina 1 di 2

172. Residui (parecchio) quadratici

Inviato: 13 gen 2014, 23:07
da Gottinger95
Trovare tutti gli interi positivi \(n\) che sono residui quadratici modulo tutti i primi maggiori di \(n\).

Scusate se ci ho messo tanto a postare il problema della staffetta! :D

EDIT: corretto, \(n\) positivi!

Re: 172. Residui (parecchio) quadratici

Inviato: 13 gen 2014, 23:39
da karlosson_sul_tetto
Interi positivi o anche negativi?

Re: 172. Residui (parecchio) quadratici

Inviato: 14 gen 2014, 12:26
da jordan
Non è necessario imporre che $n$ sia positivo; lascio l'esercizio a chi non lo conosce già..

Re: 172. Residui (parecchio) quadratici

Inviato: 14 gen 2014, 17:11
da spugna
Possiamo sempre scrivere $n=a^2b$ con $b$ libero da quadrati, da cui
$\left( \dfrac{n}{p} \right)=1$ $\forall p>n \Rightarrow \left( \dfrac{a}{p} \right)^2 \left( \dfrac{b}{p} \right)=\left( \dfrac{b}{p} \right)=1$ $\forall p>n$
Ora fattorizziamo $b$ in $q_1 q_2 ... q_k$: utilizzando ancora la moltiplicatività del simbolo di Legendre abbiamo
$\left( \dfrac{q_1}{p} \right) ... \left( \dfrac{q_k}{p} \right)=1$ $\forall p>n$
Notiamo che questi fattori primi devono essere tutti dispari perché se ci fosse il 2 basterebbe prendere $p \equiv 5$ $( \mod 8 )$ per avere $LHS=-1$; inoltre, tutti i $q_i \equiv 1$ $( \mod 4)$ non influiscono sul risultato (si ottiene un fattore $1$ indipendentemente da $p$), dunque possiamo limitarci a considerare quelli congrui a $3$, che chiameremo $r_1...r_h$, ma per $h \ge 1$ l'ipotesi non può essere sempre verificata perché basta imporre

-$p \equiv 3$ $( \mod 4)$
-$p \equiv 1$ $( \mod r_j)$ $\forall j \le h-1$
-$p \equiv -1$ $( \mod r_h)$

che per il teorema cinese portano a $p \equiv c$ $( \mod 4r_1...r_h)$, dove $c$ è sicuramente coprimo sia con $4$ sia con tutti gli altri primi, altrimenti una delle imposizioni precedenti risulterebbe falsa, dunque si può applicare Dirichlet per dedurre che esistono infiniti $p$ (e quindi infiniti maggiori di $n$) per i quali non vale l'ipotesi: tutto ciò si riassume dicendo che tutti i fattori primi di $n$ con esponente dispari devono essere congrui a $1$ modulo $4$

Re: 172. Residui (parecchio) quadratici

Inviato: 14 gen 2014, 17:51
da karlosson_sul_tetto
spugna ha scritto: dunque si può applicare Dirichlet
Cosa intendi di preciso con Dirichlet?
spugna ha scritto: tutto ciò si riassume dicendo che tutti i fattori primi di $n$ con esponente dispari devono essere congrui a $1$ modulo $4$
Forse sbaglio, ma $ 2^2\cdot 5^1=20^{\frac{23-1}{2}}=20^{11}\equiv 22 \pmod{23} $, dunque per il criterio di eulero $20$ non è residuo quadratico modulo $23$.

Re: 172. Residui (parecchio) quadratici

Inviato: 14 gen 2014, 19:58
da Triarii
Dirichlet nel sennso che esistono infiniti primi appartenenti ad una progressione aritmetica $an+b$ con $(a,b)=1$, $a>0$, e quindi esistono infiniti primi congrui a $c$ modulo $M$ con $(c,M)=1$ (come effettivamente è nel caso mostrato da spugna), ed in particolare ne esistono infiniti maggiori del numero iniziale considerato.
Poi non ho controllato il resto, quindi non so se la tua obiezione sia corretta

Re: 172. Residui (parecchio) quadratici

Inviato: 14 gen 2014, 20:18
da karlosson_sul_tetto
Triarii ha scritto:Dirichlet nel sennso che esistono infiniti primi appartenenti ad una progressione aritmetica $an+b$ con $(a,b)=1$, $a>0$, e quindi esistono infiniti primi congrui a $c$ modulo $M$ con $(c,M)=1$ (come effettivamente è nel caso mostrato da spugna),
Oddio che figata! Non lo conoscevo, grazie mille. :)

Re: 172. Residui (parecchio) quadratici

Inviato: 14 gen 2014, 20:44
da Gottinger95
Se non erro \( n=5\) soddisfa le tue ipotesi, ma non è residuo quadratico modulo \(p=7\). Di fatto
spugna ha scritto:
[...] tutti i \(q_i \equiv 1 \pmod 4 \) non influiscono sul risultato (si ottiene un fattore 1 indipendentemente da \(p\))
non è vero. Cioè, significherebbe che tutti i numeri \( \pmod{p} \) congrui a 1 \(\pmod{4}\) sono residui quadratici. Magari fossero distribuiti così facilmente! Magari volevi applicare reciprocità quadratica: in quel caso non conta la congruenza \(\pmod{4}\) di \(p\), ma ti rimane comunque un
\( \left ( \dfrac{p}{q_i} \right ) \)!

Qui invece non ho capito bene:
spugna ha scritto:
[...] questi fattori primi devono essere tutti dispari perché se ci fosse il 2 basterebbe prendere \(p \equiv 5 \pmod 8\) per avere \(LHS=−1\).
Cioè ok che \( \left ( \dfrac{2}{p} \right ) = -1\), ma magari gli altri \(q_i\) in tutto contribuiscono con un \(-1\), e allora il 2 può ben rimanere lì dov'è!

Last thing, che è più una sfida che altro: visto che dirichlet diciamo che è potente come cosa, si può risolvere anche senza, ma insomma, è pur sempre un teorema. Sono sempre indeciso su problemi etici di questo tipo, cioè su quanto è sleale usare certi fatti o meno :lol:

Re: 172. Residui (parecchio) quadratici

Inviato: 14 gen 2014, 21:02
da Drago96
karlosson_sul_tetto ha scritto:
Triarii ha scritto:Dirichlet nel sennso che esistono infiniti primi appartenenti ad una progressione aritmetica $an+b$ con $(a,b)=1$, $a>0$, e quindi esistono infiniti primi congrui a $c$ modulo $M$ con $(c,M)=1$ (come effettivamente è nel caso mostrato da spugna),
Oddio che figata! Non lo conoscevo, grazie mille. :)
Di più, la somma dei reciproci diverge!
Per altre informazioni, chiedi a wikipedia (tipo L-serie, L-funzioni e caratteri) o a enigma...

Re: 172. Residui (parecchio) quadratici

Inviato: 14 gen 2014, 21:25
da spugna
Chiedo scusa per la valanga di boiate che ho scritto: mi ricordavo male la regola per passare da $\left( \dfrac{p}{q} \right)$ a $\left( \dfrac{q}{p} \right)$ (potevo anche farlo un salto su wikipedia..! :oops: ) Vedo se riesco a metterla a posto...

Re: 172. Residui (parecchio) quadratici

Inviato: 14 gen 2014, 21:57
da Gottinger95
Tranquillissimo! :) Confido che riuscirai nei tuoi eroici intenti

Re: 172. Residui (parecchio) quadratici

Inviato: 14 gen 2014, 22:36
da spugna
Gottinger95 ha scritto:Tranquillissimo! :) Confido che riuscirai nei tuoi eroici intenti
Eroico intento N°1

Riparto da $b=q_1...q_k$ e suppongo per assurdo $q_1=2$: allora il controesempio lo trovo imponendo $p \equiv 5$ $( \mod 8 )$ e $p \equiv 1$ $( \mod q_i)$ per ogni $i \ge 2$, da cui $\left( \dfrac{2}{p} \right)=-1$ e $\left( \dfrac{q_i}{p} \right)=1$, che contraddice l'ipotesi

Eroico intento N°2

$\left( \dfrac{q_1}{p} \right)...\left( \dfrac{q_k}{p} \right)=\left( \dfrac{p}{q_1} \right)...\left( \dfrac{p}{q_k} \right) (-1)^{h \frac{p-1}{2}}$, dove $h$ è il numero dei congrui a $3$ modulo $4$, ma anche qui se $k \ge 1$ trovo un controesempio imponendo $p$ congruo a $1$ modulo $4$ e modulo tutti i primi tranne uno, e infine congruo a qualcosa che non è un quadrato modulo quello rimanente... e quindi se stavolta è giusto vanno bene solo i quadrati perfetti :roll:

Re: 172. Residui (parecchio) quadratici

Inviato: 14 gen 2014, 23:21
da jordan
Drago96 ha scritto:Di più, la somma dei reciproci diverge!
Di piu', puoi sapere quant'è la somma dei reciproci quasi esattamente :wink:

Re: 172. Residui (parecchio) quadratici

Inviato: 16 gen 2014, 23:41
da Gottinger95
@spugna: perfetto! Si vede che hai il cuore di un eroe :lol:
Vai col prossimo!

@Jordan: cavoli, mi interessano un sacco le cose analitiche sui primi, sai consigliarmi qualcosa sull'argomento? Magari da Dirichlet a "la somma degli inversi converge", e "lo so pure stimare" :P O insomma, una dispensa qualsiasi può andar bene

Re: 172. Residui (parecchio) quadratici

Inviato: 17 gen 2014, 02:34
da jordan
Salta i primi capitoli, per il resto questo a mio tempo mi è piaciuto molto! ;)