172. Residui (parecchio) quadratici

[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!

EDIT: corretto, \(n\) positivi!

[karlosson_sul_tetto]

Interi positivi o anche negativi?

[jordan]

Non è necessario imporre che $n$ sia positivo; lascio l'esercizio a chi non lo conosce già..

[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$

[karlosson_sul_tetto]

dunque si può applicare Dirichlet

Cosa intendi di preciso con Dirichlet?

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$.

[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

[karlosson_sul_tetto]

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.

[Gottinger95]

Se non erro \( n=5\) soddisfa le tue ipotesi, ma non è residuo quadratico modulo \(p=7\). Di fatto

[...] 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:

[...] 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

[Drago96]

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...

[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..! ) Vedo se riesco a metterla a posto...

[Gottinger95]

Tranquillissimo! Confido che riuscirai nei tuoi eroici intenti

[spugna]

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

[jordan]

Di più, la somma dei reciproci diverge!

Di piu', puoi sapere quant'è la somma dei reciproci quasi esattamente

[Gottinger95]

@spugna: perfetto! Si vede che hai il cuore di un eroe
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" O insomma, una dispensa qualsiasi può andar bene

[jordan]

Salta i primi capitoli, per il resto questo a mio tempo mi è piaciuto molto!