Dimostrare che per ogni $ n\in \mathbb{N} $ esistono $ a,b,c,d \in\mathbb{N}^4 $ tali che
$ a^2+b^2+c^2+d^2=n $
Quattro Quadrati
Quattro Quadrati
Un giorno di questi mi metteranno in prigione per aver stuprato troppi problemi.
Re: Quattro Quadrati
Questo esercizio sembra molto figo, ci sto pensando da stamattina ma fino a poco fa non avevo trovato quasi nulla, ora invece credo di essere sulla buona strada (ma la soluzione è ancora parziale ):
Fino ad ora sono sulla strada giusta, oppure non serve a nulla tutto ciò?
Testo nascosto:
-
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
Re: Quattro Quadrati
Sei su un'ottima strada! Sono solo leggermente inquietato dall'affermazione che $-b^2-1$ è "negativo": siccome sei modulo $p$, questo vuol dire poco o nulla! In particolare la frase "Inoltre, il LHS è sempre positivo mentre il RHS sempre negativo, quindi gli insiemi a cui appartengono tutti gli elementi di questi due tipi sono disgiunti" andrebbe chiarita (o eliminata... in ogni caso, io non la capisco^^). Stai anche attento a come dimostri che i residui quadratici sono $(p+1)/2$: l'idea è giusta, ma l'hai scritta veramente di fretta: chi è $m$? Chi è $a$? E poi dovresti sfruttare esplicitamente il fatto che un polinomio di grado 2 ha al più 2 radici modulo $p$, cosa che non dici da nessuna parte - osserva che questo è veramente il punto cruciale, e per esempio è il motivo per cui quello stesso conteggio fallisce modulo 8 (dove il polinomio $x^2-1$ ha 4 radici). E infine, già che mi sono messo a farti le pulci allo stile (ma insisto, le idee sono ottime): quando dici "la loro unione ne ha $p+1$" in realtà dovresti dire "la somma delle loro cardinalità è $p+1$", visto che di sicuro la loro unione non ha più di $p$ elementi (è un sottoinsieme delle classi di resto modulo $p$, che sono $p$ - è proprio il punto della tua dimostrazione!)
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO
Re: Quattro Quadrati
Oops, queste sono tutte le scemenze che scrivo alle $3$ di notte Cerco di spiegare/ aggiustare/ riempire i buchi che ho lasciato. Innanzitutto $p=2n+1$.
Consideriamo i due insiemi:
$$R:= \{a^2 \mid a=0,1, \dots , \frac {p-1}{2} \} \ \ , \ \ S:= \{ -b^2-1 \mid b=0,1, \dots , \frac {p-1}{2} \}$$
Supponiamo per assurdo che vi siano due elementi in $R$ che sono congrui modulo $p$, allora si avrebbe:
$$a^2 \equiv c^2 \pmod p \iff (a+c)(a-c) \equiv 0 \pmod p \iff p \mid (a+c) \ \ \text{o} \ \ p \mid (a-c)$$
Ma dato che $a-c,a+c \leq 2n <p$ e $a,c \geq 0$ si ottiene che $a=c$.
In modo del tutto identico si dimostra che non vi sono due elementi congrui modulo $p$ in $S$.
Osserviamo inoltre che gli elementi in $R$ sono tutti $\geq 0$ , mentre gli elementi in $S$ sono tutti $<0$ , quindi $R \cap S= \emptyset$.
Ma se consideriamo ora $T=R \cup S$ otteniamo che $T$ ha $2n+2=p+1$ elementi. Quindi vi saranno due elementi in $T$ che sono congrui modulo $p$, ma per quanto detto all'inizio, un elemento proviene da $R$ mentre l'altro proviene da $S$. Quest'ultima affermazione è equivalente a dire che :
$$a^2+b^2+1=kp$$ ha sempre soluzione.
Ho cambiato la dimostrazione in parte poiché era questa quella che avevo in mente. Hai ragione, avevo completamente omesso il fatto che il mio polinomio $P(x)$ ha al più due radici! In particolare, $m$ era una generica classe di resto a cui $a^2$ era congruo modulo $p$. Il mio polinomio in questo caso ne ha esattamente $2$ modulo $p$ , ovvero sia $a$ che $-a$ , ma dato che $-a \equiv p-a \pmod p$ e per il discorso iniziale $a^2$ è congruo ad esattamente $1+ \dfrac {p-1}{2}$ classi di resto distinte, si ottiene che i residui quadratici sono esattamente $1+ \dfrac {p-1}{2}$.
Consideriamo i due insiemi:
$$R:= \{a^2 \mid a=0,1, \dots , \frac {p-1}{2} \} \ \ , \ \ S:= \{ -b^2-1 \mid b=0,1, \dots , \frac {p-1}{2} \}$$
Supponiamo per assurdo che vi siano due elementi in $R$ che sono congrui modulo $p$, allora si avrebbe:
$$a^2 \equiv c^2 \pmod p \iff (a+c)(a-c) \equiv 0 \pmod p \iff p \mid (a+c) \ \ \text{o} \ \ p \mid (a-c)$$
Ma dato che $a-c,a+c \leq 2n <p$ e $a,c \geq 0$ si ottiene che $a=c$.
In modo del tutto identico si dimostra che non vi sono due elementi congrui modulo $p$ in $S$.
Osserviamo inoltre che gli elementi in $R$ sono tutti $\geq 0$ , mentre gli elementi in $S$ sono tutti $<0$ , quindi $R \cap S= \emptyset$.
Ma se consideriamo ora $T=R \cup S$ otteniamo che $T$ ha $2n+2=p+1$ elementi. Quindi vi saranno due elementi in $T$ che sono congrui modulo $p$, ma per quanto detto all'inizio, un elemento proviene da $R$ mentre l'altro proviene da $S$. Quest'ultima affermazione è equivalente a dire che :
$$a^2+b^2+1=kp$$ ha sempre soluzione.
Ho cambiato la dimostrazione in parte poiché era questa quella che avevo in mente. Hai ragione, avevo completamente omesso il fatto che il mio polinomio $P(x)$ ha al più due radici! In particolare, $m$ era una generica classe di resto a cui $a^2$ era congruo modulo $p$. Il mio polinomio in questo caso ne ha esattamente $2$ modulo $p$ , ovvero sia $a$ che $-a$ , ma dato che $-a \equiv p-a \pmod p$ e per il discorso iniziale $a^2$ è congruo ad esattamente $1+ \dfrac {p-1}{2}$ classi di resto distinte, si ottiene che i residui quadratici sono esattamente $1+ \dfrac {p-1}{2}$.