Sia $ p $ un primo dispari.
Determinare in funzione di $ p $ quanto vale
$ \prod_{i=1}^{p-1}(i^2+1) $ modulo $ p $.
Sti Quadrati
Sti Quadrati
Un giorno di questi mi metteranno in prigione per aver stuprato troppi problemi.
-
- Messaggi: 69
- Iscritto il: 10 apr 2015, 18:19
Re: Sti Quadrati
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
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
Ultima modifica di Giovanni_98 il 13 lug 2016, 12:18, modificato 1 volta in totale.
Re: Sti Quadrati
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.
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.
Testo nascosto:
Testo nascosto:
Un giorno di questi mi metteranno in prigione per aver stuprato troppi problemi.
-
- Messaggi: 69
- Iscritto il: 10 apr 2015, 18:19
Re: Sti Quadrati
Eh ti ho detto che qualche typo del cazzo ci sarebbe stato ahaha.
Re: Sti Quadrati
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)
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:
Testo nascosto:
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)