Non che voglia "imporre" i miei problemi sul forum, però riporterei all'attenzione questi due esercizi la soluzione dei quali richiede per entrambi un "trucchetto" molto astuto...
I) Siano $ p $ e $ q $ due numeri primi gemelli.
Trovare la condizione necessaria e sufficiente affinchè $ p $ sia un residuo quadratico modulo $ q $.
II) Trovare la somma
$ \displaystyle \sum_{n=1}^{p}{\left(\frac{n^2+b n+c}{p} \right)} $
dove $ p $ è un numero primo, $ b $ e $ c $ sono numeri interi e $ \displaystyle \left(\frac{a}{b} \right) $ è il simbolo di Legendre.
Esercizi simpatici
Esercizi simpatici
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
Andiamo col 2) allora... anzi, il 2 è meglio saltarlo. p è un primo dispari. Ora, com'è noto, possiamo ricondurci al caso b=0 poichè:
$ ~ n^2+bn+c = (n+2^{-1}b)^2 + (c-2^{-2}b^2) $.
Ora, se per caso $ ~ n^2+c $ è un residuo, cioè esiste un a con $ ~ n^2+c=a^2 $, allora $ ~ (n+a)(n-a) = -c $. Visto che questa equazione è più trattabile, vediamo, fissato c, quante coppie (n,a) la risolvono.
Non è difficile convincersi che sono tante quante le coppie $ ~ (x,y) $ tali che $ ~ xy=-c $, vedendo poi che $ ~ n = \frac{x+y}2,\ a = \frac{x-y}2 $, biunivoca. Quindi, se c non è 0, abbiamo p-1 coppie. (se c = 0 tutti quelli nella somma son residui eh).
Nella sommatoria, abbiamo tanti residui quanti sono i primi membri dell'insieme delle coppie (n,a). Supponiamo che per un certo n, ci sia la coppia (n,a). Allora è facile vedere che l'unica altra soluzione che inizia per n è (n, -a). a,-a sono distinti se e solo se a è diverso da 0. Inoltre c'è una soluzione con a=0 se e soltanto se -c è un residuo quadratico. Quindi abbiamo i casi:
$ ~ n^2+bn+c = (n+2^{-1}b)^2 + (c-2^{-2}b^2) $.
Ora, se per caso $ ~ n^2+c $ è un residuo, cioè esiste un a con $ ~ n^2+c=a^2 $, allora $ ~ (n+a)(n-a) = -c $. Visto che questa equazione è più trattabile, vediamo, fissato c, quante coppie (n,a) la risolvono.
Non è difficile convincersi che sono tante quante le coppie $ ~ (x,y) $ tali che $ ~ xy=-c $, vedendo poi che $ ~ n = \frac{x+y}2,\ a = \frac{x-y}2 $, biunivoca. Quindi, se c non è 0, abbiamo p-1 coppie. (se c = 0 tutti quelli nella somma son residui eh).
Nella sommatoria, abbiamo tanti residui quanti sono i primi membri dell'insieme delle coppie (n,a). Supponiamo che per un certo n, ci sia la coppia (n,a). Allora è facile vedere che l'unica altra soluzione che inizia per n è (n, -a). a,-a sono distinti se e solo se a è diverso da 0. Inoltre c'è una soluzione con a=0 se e soltanto se -c è un residuo quadratico. Quindi abbiamo i casi:
- -c non è un residuo, quindi ogni n compare come primo mebro di esattamente due coppie (n,a), quindi gli n che ci danno un residuo sono esattamente $ ~ \frac{p-1}2 $, quindi la sommatoria fa 0.
-c è un residuo, quindi ogni n compare come primo membro di esattamente due coppie (n,a), tranne le due radice quadrate di -c, a cui corrisponde una coppia. Gli n che ci danno un residuo sono $ ~ \frac{p-3}2 + 2 = \frac{p+1}2 $, quindi la sommatoria fa 2
-c è 0, e la sommatoria fa p-1.
Onestamente a me viene diverso il risultato, comunque boh, scrivo la mia:
(come disse edriv, 2 non e' un primo, e' un caso particolare)
$ \displaystyle \sum_{n=1}^{p}{\left(\frac{n^2+b n+c}{p} \right)}\equiv\sum_{n=1}^{p} (n^2+bn+c)^{\frac{p-1}{2}}\pmod p $
Mentre $ \displaystyle\sum_{n=1}^{p} (n^2+bn+c)^{\frac{p-1}{2}}=\sum_{n=1}^{p} n^{p-1}+q(n) $
Dove q(n) e' un polinomio di grado minore di p-1 e quindi $ \displaystyle\sum_{n=1}^{p} q(n)\equiv 0\pmod p $
Inoltre $ \displaystyle\sum_{n=1}^{p} n^{p-1}\equiv -1 \pmod p $, quindi
$ \displaystyle \sum_{n=1}^{p}{\left(\frac{n^2+b n+c}{p} \right)}\equiv -1\pmod p $
Per cui, per ovvi motivi, i casi sono 2:
1) $ \displaystyle \sum_{n=1}^{p}{\left(\frac{n^2+b n+c}{p} \right)}=-1 $, assurdo mod 2 se $ n^2+b n+c $ ha un numero dispari di radici distinte mod p;
2) $ \displaystyle \sum_{n=1}^{p}{\left(\frac{n^2+b n+c}{p} \right)}=p-1 $, assurdo mod 2 se $ n^2+b n+c $ ha un numero pari di radici distinte mod p.
ciaociao
(come disse edriv, 2 non e' un primo, e' un caso particolare)
$ \displaystyle \sum_{n=1}^{p}{\left(\frac{n^2+b n+c}{p} \right)}\equiv\sum_{n=1}^{p} (n^2+bn+c)^{\frac{p-1}{2}}\pmod p $
Mentre $ \displaystyle\sum_{n=1}^{p} (n^2+bn+c)^{\frac{p-1}{2}}=\sum_{n=1}^{p} n^{p-1}+q(n) $
Dove q(n) e' un polinomio di grado minore di p-1 e quindi $ \displaystyle\sum_{n=1}^{p} q(n)\equiv 0\pmod p $
Inoltre $ \displaystyle\sum_{n=1}^{p} n^{p-1}\equiv -1 \pmod p $, quindi
$ \displaystyle \sum_{n=1}^{p}{\left(\frac{n^2+b n+c}{p} \right)}\equiv -1\pmod p $
Per cui, per ovvi motivi, i casi sono 2:
1) $ \displaystyle \sum_{n=1}^{p}{\left(\frac{n^2+b n+c}{p} \right)}=-1 $, assurdo mod 2 se $ n^2+b n+c $ ha un numero dispari di radici distinte mod p;
2) $ \displaystyle \sum_{n=1}^{p}{\left(\frac{n^2+b n+c}{p} \right)}=p-1 $, assurdo mod 2 se $ n^2+b n+c $ ha un numero pari di radici distinte mod p.
ciaociao
"Sei la Barbara della situazione!" (Tap)
piever ha scritto:Dove q(n) e' un polinomio di grado minore di p-1 e quindi $ \displaystyle\sum_{n=1}^{p} q(n)\equiv 0\pmod p $
Sapresti spiegarmi in modo non trascendentale questa uguaglianza?Sai, nella mia dimostrazione non ho fatto uso di robe così complicate...
Non tanto generatore, quanto un'altra cosa piuttosto...salva90 ha scritto:Feddy... prima che posto cazzate alquanto lunghe... per caso il primo dipende dal fatto che 2 sia o meno un generatore modulo q?
[quote="julio14"]Ci sono casi in cui "si deduce" si può sostituire con "è un'induzione che saprebbe fare anche un macaco", ma per come hai impostato i conti non mi sembra la tua situazione...[/quote][quote="Tibor Gallai"]Ah, un ultimo consiglio che risolve qualsiasi dubbio: ragiona. Le cose non funzionano perché lo dico io o Cauchy o Dio, ma perché hanno senso.[/quote]To understand recursion, you fist need to understand recursion.
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
[tex]i \in \| al \| \, \pi \, \zeta(1)[/tex]
ok, la scrivo.FeddyStra ha scritto:Non tanto generatore, quanto un'altra cosa piuttosto...salva90 ha scritto:Feddy... prima che posto cazzate alquanto lunghe... per caso il primo dipende dal fatto che 2 sia o meno un generatore modulo q?
(1) $ \displaystyle\left(\frac{p}{q}\right)\equivp^{\frac{q-1}{2}}\equiv(-2)^{\frac{q-1}{2}} $
caso 1: $ q=4k+1 $
allora la (1) vale 1 sse 2 è residuo quadratico modulo q
caso 2: $ q=4k+3 $
in questo caso la (1) vale 1 sse 2 NON è residuo quadratico mod q, in quanto ci resta un bel meno che non va via con l'elevamento a potenza.
era questa la soluzione?
temo che ci sia qualcosa di più, che rende la condizione ancora più bella 
[url=http://www.myspace.com/italiadimetallo][img]http://img388.imageshack.us/img388/4813/italiadimetallogn7.jpg[/img][/url]
Ok, perdonami ma per incasinarmi di meno con le notazioni ragiono in $ \mathbb{F}_p $FeddyStra ha scritto:piever ha scritto:Dove q(n) e' un polinomio di grado minore di p-1 e quindi $ \displaystyle\sum_{n=1}^{p} q(n)\equiv 0\pmod p $
Scriviamo il polinomio $ r(x_1,\dots ,x_p)=\displaystyle\sum_{n=1}^{p} q(x_n) $
Questo e' chiaramente un polinomio simmetrico di grado <p-1 in p variabili, per cui si puo' scrivere come polinomio nelle funzioni simmetriche degli x_i, dove le funzioni simmetriche vanno da quella di primo grado (non di grado 0 perche' r non ha termine noto) a quella di p-2 esimo grado. Ora se gli x_i sono una permutazione dei residui, le funzioni simmetriche quanto fanno?
Prendiamo $ s(x)=\displaystyle\prod_{i=1}^p (x-i) $
Per il piccolo teorema di Fermat $ s(x)=x^p-x $ per cui le funzioni simmetriche che ci interessano si annullano, quindi $ r(1,\dots ,p)=0 $
Tu invece come dimostri il tuo simpatico esercizio?
"Sei la Barbara della situazione!" (Tap)