Sti Quadrati

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Saro00
Messaggi: 114
Iscritto il: 27 mag 2015, 10:52
Località: Provincia di Milano

Sti Quadrati

Messaggio da Saro00 » 12 lug 2016, 19:36

Sia $ p $ un primo dispari.
Determinare in funzione di $ p $ quanto vale
$ \prod_{i=1}^{p-1}(i^2+1) $ modulo $ p $.
Un giorno di questi mi metteranno in prigione per aver stuprato troppi problemi. 8)

Giovanni_98
Messaggi: 69
Iscritto il: 10 apr 2015, 18:19

Re: Sti Quadrati

Messaggio da Giovanni_98 » 13 lug 2016, 10:27

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
Ultima modifica di Giovanni_98 il 13 lug 2016, 12:18, modificato 1 volta in totale.

Saro00
Messaggi: 114
Iscritto il: 27 mag 2015, 10:52
Località: Provincia di Milano

Re: Sti Quadrati

Messaggio da Saro00 » 13 lug 2016, 11:28

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.
Testo nascosto:
Cosa c'entra il polinomio $ (x-1)^{\frac{p-1}{2}} $ con il problema?
Quindi il prodotto delle radici é facile trovarlo...
Testo nascosto:
Non so giustificare il fatto che si possa fare, ma pare funzionare.
$ x^2+1=(x+i)(x-i) $ quindi ci basta sapere $ \prod_{j=1}^{p-1}(j+i) $, ma ora vediamolo come un polinomio di grado $ p-1 $ in $ i $, coincide con $ i^{p-1}-1 $ e quindi si conclude con poco sforzo.
Un giorno di questi mi metteranno in prigione per aver stuprato troppi problemi. 8)

Giovanni_98
Messaggi: 69
Iscritto il: 10 apr 2015, 18:19

Re: Sti Quadrati

Messaggio da Giovanni_98 » 13 lug 2016, 12:17

Eh ti ho detto che qualche typo del cazzo ci sarebbe stato ahaha.

Rho33
Messaggi: 89
Iscritto il: 16 set 2014, 13:15

Re: Sti Quadrati

Messaggio da Rho33 » 24 lug 2016, 03:21

Dato che il caro Olimato è quasi morto in sto periodo( :cry: ), inizio a postare qualcosa anche in questo, magari trovo più compagnia :mrgreen:
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:
Non so se fosse un hint voluto di Saro, ma quella $i$ del testo mi ha fatto pensare a lavorare in $\mathbb{Z}$. Consideriamo innanzitutto il seguente polinomio:

$$P(x)=(x+1)\cdot (x+2) \cdot \dots \cdot (x+p-1)=x^{p-1}+ (p-1)!+p\cdot Q(x) \qquad Q(x) \in \mathbb{Z}[x]$$

Per evitare confusione, rimpiazzo il testo come:

$$\prod_{k=1}^{p-1}(k^2+1)$$

Ora osserviamo che: $$(k^2+1)=(k+i)(k-i) \qquad \forall k$$

Ma allora è ovvio che posso riscrivere il testo come:

$$\prod_{k=1}^{p-1}(k^2+1)=P(i)\cdot P(-i)=(i^{p-1}+(p-1)!+p \cdot Q(i))( (-i)^{p-1}+(p-1)!+ p \cdot Q(-i))$$

Ora guardiamo modulo $p$ (usando anche Wilson e le proprietà di $i$) ed otteniamo:

$$(i^{p-1}-1)((-i)^{p-1}-1) \equiv \begin{cases}4 \ \ \text{se} \ \ p \equiv 3 \pmod 4 \\ 0 \ \ \text{se} \ \ p \equiv 1 \pmod 4 \end{cases}$$

P.S. Il caso $p=3$ si fa a parte ed otteniamo $1$ (sul perché si faccia a parte, data l'ora molto tarda non mi viene in mente :oops: )



EDIT: Ovviamente mi accorgo solo ora che Saro aveva già postato :oops: (questa dovrebbe corrispondere al suo secondo spoiler, almeno dubito di meno sulla sua correttezza)

Rispondi