OliForum Matematico

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.

beh, potevi uppare i due messaggi precedenti....

Feddy... prima che posto cazzate alquanto lunghe... per caso il primo dipende dal fatto che 2 sia o meno un generatore modulo q?

E come si fa a sapere se 2 e' generatore mod q?

A proposito, provate a fare il secondo, e' carino e la tesi ha conseguenze interessanti...

ciao!

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:

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

Ho indovinato?

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

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

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?

Non tanto generatore, quanto un'altra cosa piuttosto...

FeddyStra ha scritto:

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?

Non tanto generatore, quanto un'altra cosa piuttosto...

ok, la scrivo.

(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

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 $

Sapresti spiegarmi in modo non trascendentale questa uguaglianza?

Ok, perdonami ma per incasinarmi di meno con le notazioni ragiono in $ \mathbb{F}_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?