$7\mid \text{gcd}(x,y)$
$7\mid \text{gcd}(x,y)$
Sapendo che $x,y$ sono interi tali che $3x+4y$ e $4x+3y$ sono quadrati, mostrare che $7$ divide sia $x$ che $y$.
The only goal of science is the honor of the human spirit.
Re: $7\mid \text{gcd}(x,y)$
Scrivo le due equazioni:
$$3x+4y=m^2 \textrm{ e } 4x+3y=n^2$$
Sommo le due equazioni membro a membro, ottenendo:
$$7(x+y)=m^2+n^2$$
Osservo che LHS è congruo a $0$ modulo $7$, e visto che i residui quadratici modulo $7$ sono solo $\left\{0,1,2,4\right\}$, l'unico modo in cui RHS può essere congruo a $0$ modulo $7$ è con $n,m\equiv 0 \pmod7$.
Dunque $m^2+n^2\equiv 0 \pmod {49}$, e quindi $x+y\equiv 0 \pmod 7$.
Sommando ripetutamente questa nuova condizione con $3x+4y\equiv 0 \pmod 7$ e $4x+3y\equiv 0 \pmod 7$, si ottiene:
$$6x\equiv 0 \pmod 7 \textrm{ e } 6y\equiv 0 \pmod 7$$
Visto che $(6,7)=1$, questo implica la tesi!
$$3x+4y=m^2 \textrm{ e } 4x+3y=n^2$$
Sommo le due equazioni membro a membro, ottenendo:
$$7(x+y)=m^2+n^2$$
Osservo che LHS è congruo a $0$ modulo $7$, e visto che i residui quadratici modulo $7$ sono solo $\left\{0,1,2,4\right\}$, l'unico modo in cui RHS può essere congruo a $0$ modulo $7$ è con $n,m\equiv 0 \pmod7$.
Dunque $m^2+n^2\equiv 0 \pmod {49}$, e quindi $x+y\equiv 0 \pmod 7$.
Sommando ripetutamente questa nuova condizione con $3x+4y\equiv 0 \pmod 7$ e $4x+3y\equiv 0 \pmod 7$, si ottiene:
$$6x\equiv 0 \pmod 7 \textrm{ e } 6y\equiv 0 \pmod 7$$
Visto che $(6,7)=1$, questo implica la tesi!
"Una funzione generatrice è una corda da bucato usata per appendervi una successione numerica per metterla in mostra" (Herbert Wilf)
"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)
Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?
PRIMA FILA TUTTI SBIRRI!
"La matematica è la regina delle scienze e la teoria dei numeri è la regina della matematica" (Carl Friedrich Gauss)
Sensibilizzazione all'uso delle potenti Coordinate Cartesiane, possano seppellire per sempre le orride baricentriche corruttrici dei giovani: cur enim scribere tre numeri quando se ne abbisogna di due?
PRIMA FILA TUTTI SBIRRI!
Re: $7\mid \text{gcd}(x,y)$
Giusto ma evita di farti i casi a mano: dato un primo $p\equiv 3\pmod 4$ abbiamo $p\mid x^2+y^2$ per qualche intero $x,y$ se e solo se $p\mid \text{gcd}(x,y)$ 
The only goal of science is the honor of the human spirit.
-
NicolasRossi
- Messaggi: 48
- Iscritto il: 18 mar 2013, 22:33
- Località: Senise (PZ)
Re: $7\mid \text{gcd}(x,y)$
Jordan, puoi spiegare a noi poveri non teoretideinumeri il perché? 
"Per tre cose vale la pena di vivere: la matematica, la musica, l'amore." [cit.]
Re: $7\mid \text{gcd}(x,y)$
Ci provo io a dimostrare questo lemma, sperando di non sbagliare
Riscrivo come $m^2\equiv -n^2 (p)$
Supponiamo che m e n non siano multipli di $p$. dato che $\mathbb Z /p\mathbb Z$ è un campo, posso dividere ambo i membri per $n^2$, ottenendo $(\frac {m} {n} )^2\equiv -1$
Ma ciò è assurdo perchè a sinistra abbiamo un quadrato, mentre a destra un numero che non è un residuo quadratico (-1 è residuo sse $p\equiv 1 (4)$ ). Quindi l'unica soluzione è che sia $m$ che $n$ siano multipli di $p$
Oppure si potrebbe dimostrare in modo simile al primo del contest.
$m\equiv \pm in (p)$ con $i^2=-1$ che esiste solo se $p\equiv 1 (4)$ oppure se $m\equiv n \equiv 0 (p)$ (che è proprio il nostro caso)
Riscrivo come $m^2\equiv -n^2 (p)$
Supponiamo che m e n non siano multipli di $p$. dato che $\mathbb Z /p\mathbb Z$ è un campo, posso dividere ambo i membri per $n^2$, ottenendo $(\frac {m} {n} )^2\equiv -1$
Ma ciò è assurdo perchè a sinistra abbiamo un quadrato, mentre a destra un numero che non è un residuo quadratico (-1 è residuo sse $p\equiv 1 (4)$ ). Quindi l'unica soluzione è che sia $m$ che $n$ siano multipli di $p$
Oppure si potrebbe dimostrare in modo simile al primo del contest.
$m\equiv \pm in (p)$ con $i^2=-1$ che esiste solo se $p\equiv 1 (4)$ oppure se $m\equiv n \equiv 0 (p)$ (che è proprio il nostro caso)
"We' Inge!"
LTE4LYF
LTE4LYF