172. Residui (parecchio) quadratici

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

172. Residui (parecchio) quadratici

Messaggio 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!
Ultima modifica di Gottinger95 il 13 gen 2014, 23:47, modificato 1 volta in totale.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: 172. Residui (parecchio) quadratici

Messaggio da karlosson_sul_tetto »

Interi positivi o anche negativi?
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 172. Residui (parecchio) quadratici

Messaggio da jordan »

Non è necessario imporre che $n$ sia positivo; lascio l'esercizio a chi non lo conosce già..
The only goal of science is the honor of the human spirit.
spugna
Messaggi: 421
Iscritto il: 19 mar 2009, 22:18
Località: Forlì

Re: 172. Residui (parecchio) quadratici

Messaggio 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$
"Bene, ora dobbiamo massimizzare [tex]\dfrac{x}{(x+100)^2}[/tex]: come possiamo farlo senza le derivate? Beh insomma, in zero fa zero... a $+\infty$ tende a zero... e il massimo? Potrebbe essere, che so, in $10^{24}$? Chiaramente no... E in $10^{-3}$? Nemmeno... Insomma, nella frazione c'è solo il numero $100$, quindi dove volete che sia il massimo se non in $x=100$..?" (da leggere con risatine perfide e irrisorie in corrispondenza dei puntini di sospensione)

Maledetti fisici! (cit.)
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: 172. Residui (parecchio) quadratici

Messaggio 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$.
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
Triarii
Messaggi: 464
Iscritto il: 18 nov 2010, 21:14

Re: 172. Residui (parecchio) quadratici

Messaggio 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
"We' Inge!"
LTE4LYF
Avatar utente
karlosson_sul_tetto
Messaggi: 1452
Iscritto il: 10 set 2009, 13:21
Località: Napoli

Re: 172. Residui (parecchio) quadratici

Messaggio 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. :)
"Inequality happens"
---
"Chissa se la fanno anche da asporto"
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: 172. Residui (parecchio) quadratici

Messaggio 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:
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Avatar utente
Drago96
Messaggi: 1147
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: 172. Residui (parecchio) quadratici

Messaggio 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...
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
spugna
Messaggi: 421
Iscritto il: 19 mar 2009, 22:18
Località: Forlì

Re: 172. Residui (parecchio) quadratici

Messaggio 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...
"Bene, ora dobbiamo massimizzare [tex]\dfrac{x}{(x+100)^2}[/tex]: come possiamo farlo senza le derivate? Beh insomma, in zero fa zero... a $+\infty$ tende a zero... e il massimo? Potrebbe essere, che so, in $10^{24}$? Chiaramente no... E in $10^{-3}$? Nemmeno... Insomma, nella frazione c'è solo il numero $100$, quindi dove volete che sia il massimo se non in $x=100$..?" (da leggere con risatine perfide e irrisorie in corrispondenza dei puntini di sospensione)

Maledetti fisici! (cit.)
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: 172. Residui (parecchio) quadratici

Messaggio da Gottinger95 »

Tranquillissimo! :) Confido che riuscirai nei tuoi eroici intenti
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
spugna
Messaggi: 421
Iscritto il: 19 mar 2009, 22:18
Località: Forlì

Re: 172. Residui (parecchio) quadratici

Messaggio 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:
"Bene, ora dobbiamo massimizzare [tex]\dfrac{x}{(x+100)^2}[/tex]: come possiamo farlo senza le derivate? Beh insomma, in zero fa zero... a $+\infty$ tende a zero... e il massimo? Potrebbe essere, che so, in $10^{24}$? Chiaramente no... E in $10^{-3}$? Nemmeno... Insomma, nella frazione c'è solo il numero $100$, quindi dove volete che sia il massimo se non in $x=100$..?" (da leggere con risatine perfide e irrisorie in corrispondenza dei puntini di sospensione)

Maledetti fisici! (cit.)
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 172. Residui (parecchio) quadratici

Messaggio da jordan »

Drago96 ha scritto:Di più, la somma dei reciproci diverge!
Di piu', puoi sapere quant'è la somma dei reciproci quasi esattamente :wink:
The only goal of science is the honor of the human spirit.
Gottinger95
Messaggi: 486
Iscritto il: 01 lug 2011, 22:52

Re: 172. Residui (parecchio) quadratici

Messaggio 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
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 172. Residui (parecchio) quadratici

Messaggio da jordan »

Salta i primi capitoli, per il resto questo a mio tempo mi è piaciuto molto! ;)
The only goal of science is the honor of the human spirit.
Rispondi