Pagina 1 di 1
Sti Quadrati
Inviato: 12 lug 2016, 19:36
da Saro00
Sia $ p $ un primo dispari.
Determinare in funzione di $ p $ quanto vale
$ \prod_{i=1}^{p-1}(i^2+1) $ modulo $ p $.
Re: Sti Quadrati
Inviato: 13 lug 2016, 10:27
da Giovanni_98
Mi scuso per eventuali typo, scrivere sto schifo senza sbagliare è al limite dell'impossibile.
Lemma noto : $\sum_{j=1}^{\frac{p-1}{2}} j^{2n} \equiv 0 \pmod p$ per ogni $n$ tale che $2n \neq p-1$.
Se $p \equiv 1 \pmod 4$ allora la produttoria è congrua a $0$. Infatti, se $p \equiv 1 \pmod 4$ si ha che $-1$ è residuo quadratico, di conseguenza esiste un intero $j$ tale che $j \leq p-1$ e tale che $j^2 \equiv -1$, quindi $j^2+1 \equiv 0 \pmod 4$.
Se $p>3 \equiv 3 \pmod 4$ allora la produttoria è congrua a $4$, se invece $p=3$ allora la produttoria è congrua a $1$.
Dimostrazione (solo del caso $p>3$ ovviamente) :
Dal momento che $a^2 \equiv (p-a)^2 \pmod p$ per ogni $a$ si ha che $\prod_{i=1}^{p-1} (i^2+1) \equiv \left[\prod_{i=1}^{\frac{p-1}{2}} (i^2+1)\right]^2$.
Vale $$\left[\prod_{i=1}^{\frac{p-1}{2}} (i^2+1)\right]^2 = \left\{ \left[\sum_{i=1}^{\frac{p-1}{2}} \sum_{1 \leq a_1 < \cdots < a_i \leq \frac{p-1}{2}} \prod_{j=1}^{i} a_j^2 \right] + 1 \right\}^2$$
e vogliamo dimostrare che $$\left[\sum_{i=1}^{\frac{p-1}{2}} \sum_{1 \leq a_1 < \cdots < a_i \leq \frac{p-1}{2}} \prod_{j=1}^{i} a_j^2 \right] + 1 \equiv_p 2$$
Per prima cosa dimostriamo che se $i \neq \frac{p-1}{2}$ si ha $ \sum_{1 \leq a_1 < \cdots < a_i \leq \frac{p-1}{2}} \prod_{j=1}^{i} a_j^2 \equiv -\frac{1}{2} \sum_{j=1}^{\frac{p-1}{2}} j^{2i} \equiv 0 \pmod p$, per induzione su $i$.
Passo base $i=2$ :
Si ha $$\sum_{1 \leq a_1 < a_2 \leq \frac{p-1}{2}} a_1^2a_2^2 = \sum_{1 \leq a_1 < a_2 \leq \frac{p-1}{2}} \frac{a_1^2a_2^2}{2} + \frac{a_1^2a_2^2}{2} = \sum_{i=1}^{\frac{p-1}{2}} i^2\frac{(\sum_{j=1}^{\frac{p-1}{2}} j^2 - i^2)}{2} \equiv \frac{-i^4}{2}$$
grazie al fatto che $\sum_{j=1}^{\frac{p-1}{2}} j^2 \equiv 0 \pmod p$ con $p > 3$. Quindi ora dobbiamo dimostrare che $-\frac{1}{2} \sum_{j=1}^{\frac{p-1}{2}} j^4 \equiv 0 \pmod p$ che è ovviamente vero per il Lemma (notiamo inoltre che quel numero è intero) dal momento che $p \ge 7$ e quindi $p-1 > 4$.
Passo induttivo : supponiamo di averlo dimostrato per $i$ e dimostriamolo per $i+1$ , supponendo sempre $i+1 < \frac{p-1}{2}$. Abbiamo $\sum_{1 \leq a_1 < \cdots < a_{i+1} \leq \frac{p-1}{2}} \prod_{j=1}^{i+1} a_j^2$ che vogliamo dimostrare essere congruo a $0 \pmod p$. Analogamente a prima ragioniamo scrivendo $$\sum_{1 \leq a_1 < \cdots < a_{i+1} \leq \frac{p-1}{2}} \prod_{j=1}^{i+1} a_j^2 = \sum_{1 \leq a_1 < \cdots < a_{i+1} \leq \frac{p-1}{2}} \frac{\prod_{j=1}^{i+1} a_j^2}{2}+\frac{\prod_{j=1}^{i+1} a_j^2}{2}$$
Tuttavia, è ovvio che $$\sum_{1 \leq a_1 < \cdots < a_{i+1} \leq \frac{p-1}{2}} \frac{\prod_{j=1}^{i+1} a_j^2}{2}+\frac{\prod_{j=1}^{i+1} a_j^2}{2} = \sum_{k=1}^{\frac{p-1}{2}} k^2 \frac{\sum_{1 \leq b_1 < \cdots < b_i \leq \frac{p-1}{2}} \prod_{j=1}^i b_j^2 - k^2\sum_{1 \leq c_1 < \cdots < c_{i-1} \leq \frac{p-1}{2} \, \, c_t \ne k} \prod_{j=1}^{i-1} c_j^2}{2} \equiv_p \sum_{k=1}^{\frac{p-1}{2}}-\frac{k^{2(i+1)}}{2} \equiv_p 0$$ come volevamo.
Di conseguenza $$\left[\sum_{i=1}^{\frac{p-1}{2}} \sum_{1 \leq a_1 < \cdots < a_i \leq \frac{p-1}{2}} \prod_{j=1}^{i} a_j^2 \right] + 1 \equiv \prod_{i=1}^{\frac{p-1}{2}} i^2 + 1$$
Per il teorema di Wilson si ha $$\prod_{i=1}^{p-1} i \equiv_p -1$$ quindi $$\left[\prod_{i=1}^{p-1} i\right]^2 \equiv_p 1 \equiv_p \left[\prod_{i=1}^{\frac{p-1}{2}} i\right]^4$$ e quindi $\prod_{i=1}^{\frac{p-1}{2}} i^2 \equiv_p 1$ oppure $\prod_{i=1}^{\frac{p-1}{2}} i^2 \equiv_p -1$. Ma $-1$ non è residuo quadratico modulo $p$ poichè $p \equiv 3 \pmod 4$ e quindi $\prod_{i=1}^{\frac{p-1}{2}} i^2 \equiv_p 1$ da cui si ricava finalmente $$\left[\sum_{i=1}^{\frac{p-1}{2}} \sum_{1 \leq a_1 < \cdots < a_i \leq \frac{p-1}{2}} \prod_{j=1}^{i} a_j^2 \right] + 1 \equiv_p 2$$
e quindi $$\left\{ \left[\sum_{i=1}^{\frac{p-1}{2}} \sum_{1 \leq a_1 < \cdots < a_i \leq \frac{p-1}{2}} \prod_{j=1}^{i} a_j^2 \right] + 1 \right\}^2 \equiv_p 4$$
Edit : Wilsonnnnnnn
Re: Sti Quadrati
Inviato: 13 lug 2016, 11:28
da Saro00
Sembra giusta.
Quando enunci il teorema di Wilson c'é il segno sbagliato.
Per non far pensare esista solo la soluzione brutale metto in spoiler 2 idee carine.
Re: Sti Quadrati
Inviato: 13 lug 2016, 12:17
da Giovanni_98
Eh ti ho detto che qualche typo del cazzo ci sarebbe stato ahaha.
Re: Sti Quadrati
Inviato: 24 lug 2016, 03:21
da Rho33
Dato che il caro Olimato è quasi morto in sto periodo(
), inizio a postare qualcosa anche in questo, magari trovo più compagnia
Premesso che non ho avuto il coraggio di leggere la soluzione lunghissima e densissima sopra di me (e ciò mi fa dubitare parecchio della mia soluzione), ecco come l'ho risolto:
EDIT: Ovviamente mi accorgo solo ora che Saro aveva già postato (questa dovrebbe corrispondere al suo secondo spoiler, almeno dubito di meno sulla sua correttezza)