Sistema: soluzioni intere
Siano $a,b,c,d$ numeri interi qualsiasi. Dimostrare che il seguente sistema, nelle incognite $x,y,z,w$, ha soluzioni intere.
${(ax-by+z=c),(ay+bx+w=d),(z^2+w^2<=a^2+b^2):}$
${(ax-by+z=c),(ay+bx+w=d),(z^2+w^2<=a^2+b^2):}$
Risposte
"fields":
Siano $a,b,c,d$ numeri interi qualsiasi. Dimostrare che il seguente sistema, nelle incognite $x,y,z,w$, ha soluzioni intere.
${(ax-by+z=c),(ay+bx+w=d),(z^2+w^2<=a^2+b^2):}$
Falso: se $a = b = 0$, ma $c^2 + d^2 \ne 0$, allora il sistema non possiede alcuna soluzione, né sugli interi né altrove.
Pardon, mi sono dimenticato di escludere il caso banale. Bisogna supporre che $a$ e $b$ non siano entrambi nulli.
ps: è $z^2+w^2<=a^2+b^2$, avevo corretto nei primi 50 secondi, non credevo che qualcuno potesse aver gia' letto.. 
Vale la soluzione banale $x=y=z=w=0$, per $c=d=0$?
Certo che vale.
ps: a prima vista il sistema può sembrare difficile, ma la soluzione è concettualmente molto semplice.
ps: a prima vista il sistema può sembrare difficile, ma la soluzione è concettualmente molto semplice.
Provo a postare quanto credo di aver trovato nel caso $(a,b)=1$. E poi vado a studiare per l'università magari... 
, attendendo opinioni:
Innanzitutto un pò di algebra. Si ha:
$z=c+by-ax$
$w=d-ay-bx$
e quindi basta trovare una coppia $(x,y)$ t.c. sia rispettata la relazione:
$(c+by-ax)^2+(d-ay-bx)^2<=a^2+b^2$ [1]
Pongo ora:
$F=ax-by$ [2]
$G=ay+bx$ [3]
e la [1] diventa:
$(c-F)^2+(d-G)^2<=a^2+b^2$ [4]
la [4] può essere interpretata come una condizione sulla distanza euclidea all'interno piano cartesiano tra i punti $(c,d)$ ed $(F,G)$.
Le relazioni [2] e [3] possono essere invertite:
$x=(aF+bG)/(a^2+b^2)$ [5]
$y=(aG-bF)/(a^2+b^2)$ [6]
e quindi il problema è spostato a trovare una coppia $(F,G)$ t.c. siano rispettate p1) e p2):
p1) la relazione [4] sia rispettata;
p2) le relazioni [5] e [6] producano dei numeri interi;
la condizione p2 richiede che
p2a) $(a^2+b^2)|aF+bG$
p2b) $(a^2+b^2)|aG-bF$
ora mi semplifico la vita sperano di sistemare il ragionamento in un altro momento, usando che:
Claim: se p2a) è vera e $(a,b)=1$, allora p2b) è vera.
dim claim: vale la relazione
$a(aG-bF)+b(aF+bG)=G(a^2+b^2)$
e quindi se p2a) è vera, $a^2+b^2|a(aG-bF)$. Ma sa $(a,b)=1$, anche $(a^2+b^2,a)=1$, da cui la tesi. c.v.d.
usando il claim, basta verificare $p2a)$.
Ora l'obiettivo è costruire un reticolo sul piano cartesiano di punti interi candidati $(F,G)$ che verifichino $p2a)$ e t.c. il reticolo sia abbastanza fitto in modo che per qualsiasi scelta di $(c,d)$ esista un punto sul reticolo abbastanza vicino a $(c,d)$ in modo da verificare la [4].
Questo reticolo può essere dato dai punti $(ka-zb,kb+za)$, con $k$ e $z$ relativi. Infatti è un reticolo che forma dei quadrati di lato $sqrt(a^2+b^2)$ ed è quindi abbastanza fitto.
Torna quanto ho scritto????
, attendendo opinioni: Innanzitutto un pò di algebra. Si ha:
$z=c+by-ax$
$w=d-ay-bx$
e quindi basta trovare una coppia $(x,y)$ t.c. sia rispettata la relazione:
$(c+by-ax)^2+(d-ay-bx)^2<=a^2+b^2$ [1]
Pongo ora:
$F=ax-by$ [2]
$G=ay+bx$ [3]
e la [1] diventa:
$(c-F)^2+(d-G)^2<=a^2+b^2$ [4]
la [4] può essere interpretata come una condizione sulla distanza euclidea all'interno piano cartesiano tra i punti $(c,d)$ ed $(F,G)$.
Le relazioni [2] e [3] possono essere invertite:
$x=(aF+bG)/(a^2+b^2)$ [5]
$y=(aG-bF)/(a^2+b^2)$ [6]
e quindi il problema è spostato a trovare una coppia $(F,G)$ t.c. siano rispettate p1) e p2):
p1) la relazione [4] sia rispettata;
p2) le relazioni [5] e [6] producano dei numeri interi;
la condizione p2 richiede che
p2a) $(a^2+b^2)|aF+bG$
p2b) $(a^2+b^2)|aG-bF$
ora mi semplifico la vita sperano di sistemare il ragionamento in un altro momento, usando che:
Claim: se p2a) è vera e $(a,b)=1$, allora p2b) è vera.
dim claim: vale la relazione
$a(aG-bF)+b(aF+bG)=G(a^2+b^2)$
e quindi se p2a) è vera, $a^2+b^2|a(aG-bF)$. Ma sa $(a,b)=1$, anche $(a^2+b^2,a)=1$, da cui la tesi. c.v.d.
usando il claim, basta verificare $p2a)$.
Ora l'obiettivo è costruire un reticolo sul piano cartesiano di punti interi candidati $(F,G)$ che verifichino $p2a)$ e t.c. il reticolo sia abbastanza fitto in modo che per qualsiasi scelta di $(c,d)$ esista un punto sul reticolo abbastanza vicino a $(c,d)$ in modo da verificare la [4].
Questo reticolo può essere dato dai punti $(ka-zb,kb+za)$, con $k$ e $z$ relativi. Infatti è un reticolo che forma dei quadrati di lato $sqrt(a^2+b^2)$ ed è quindi abbastanza fitto.
Torna quanto ho scritto????
mi accorgo solo ora che il reticolo che ho costruito rispetta (per puro caso) sia p2a) che p2b).... quindi quanto sopra probabilmente può essere "sfoltito" togliendo l'ipotesi che $(a,b)=1$.... ma sentiamo cosa pensate voi 
L'interpretazione geometrica è buona, Thomas, sembra funzionare... Però non hai scritto la parte più importante della dimostrazione, quindi non mi pronuncio (non ho tempo di completare i dettagli, avendo io risolto in modo diverso).
mmm.... ma quale è la parte "più importante" da completare? forse una descrizione più precisa del "reticolo" e delle sue proprietà? Se me lo dici provo ad espandere quel passaggio...
a meno che tu non abbia voluto accennare a qualcosa che "avrei dovuto notare"
...
a meno che tu non abbia voluto accennare a qualcosa che "avrei dovuto notare"
...
ma quale è la parte "più importante" da completare? forse una descrizione più precisa del "reticolo" e delle sue proprietà?
Certo, senza la dimostrazione delle proprietà del reticolo e del fatto che p2a) viene verificata, la dimostrazione è come non ci fosse...
puff.... .... la dimostrazione è scomparsa!
Scherzi a parte, la verifica di p2a) e p2b) è solo una sostituzione:
$aF+bG=a(ka-zb)+b(kb+za)=(a^2+b^2)k$
$aG-bF=a(kb+za)-b(ka-zb)=(a^2+b^2)z$
in quanto al resto, si tratta di disegnare il reticolo... e vedere che effettivamente piastrella il piano con quadrati di lato $sqrt(a^2+b^2)$... la formalizzazione di questo passaggio sinceramente la eviterei....
perchè magari non posti la tua dimostrazione?
.... la dimostrazione è scomparsa! Scherzi a parte, la verifica di p2a) e p2b) è solo una sostituzione:
$aF+bG=a(ka-zb)+b(kb+za)=(a^2+b^2)k$
$aG-bF=a(kb+za)-b(ka-zb)=(a^2+b^2)z$
in quanto al resto, si tratta di disegnare il reticolo... e vedere che effettivamente piastrella il piano con quadrati di lato $sqrt(a^2+b^2)$... la formalizzazione di questo passaggio sinceramente la eviterei....
perchè magari non posti la tua dimostrazione?
Il punto è, Thomas, che quello che hai scritto è pieno di passaggi inutili e che fanno confusione... Infatti era inutile scrivere le relazioni [5] e [6] così come le condizioni p2a e p2b. Se infatti scegli F e G in modo che stiano nel reticolo, ti basta verificare la disuguaglianza... E' per questo che senza l'analisi del reticolo la dimostrazione è inesistente... Comunque in effetti è noioso formalizzare la parte geometrica, quindi tanto vale andare per via algebrica. Ecco come:
Dobbiamo risolvere il sistema
${(ax-by+z=c),(ay+bx+w=d),(z^2+w^2<=a^2+b^2):}$
Consideriamo invece il sistema
${(ax-by=c),(ay+bx=d):}$
Svolgendo i calcoli otteniamo le soluzioni $x=(ac+bd)/(a^2+b^2)$ e $y=(ad-bc)/(a^2+b^2)$. Poniamo allora $x=q_1+p_1$ e $y=q_2+p_2$, dove $q_1,q_2$ sono interi e $|p_1|<=1/2$ e $|p_2|<=1/2$.
Abbiamo allora
${(a(q_1+p_1)-b(q_2+p_2)=c),(a(q_2+p_2)+b(q_1+p_1)=d):}$
dunque
${(aq_1-bq_2+(ap_1-bp_2)=c),(aq_2+bq_1+(ap_2+bp_1)=d):}$
Ci basta dunque verificare che
$(ap_1-bp_2)^2+(ap_2+bp_1)^2<=a^2+b^2$
Banale:
$(ap_1-bp_2)^2+(ap_2+bp_1)^2=(ap_1)^2+(bp_2)^2+(ap_2)^2+(bp_1)^2=(p_1^2+p_2^2)(a^2+b^2)<=(1/4+1/4)(a^2+b^2)=1/2(a^2+b^2)<(a^2+b^2)$
Abbiamo dunque dimostrato che nel dominio degli interi di Gauss la divisione con resto di $c+di$ per $a+bi$ e' possibile:
$(c+di)=(a+bi)(x+yi)+(z+wi)$
con $z^2+w^2
Dobbiamo risolvere il sistema
${(ax-by+z=c),(ay+bx+w=d),(z^2+w^2<=a^2+b^2):}$
Consideriamo invece il sistema
${(ax-by=c),(ay+bx=d):}$
Svolgendo i calcoli otteniamo le soluzioni $x=(ac+bd)/(a^2+b^2)$ e $y=(ad-bc)/(a^2+b^2)$. Poniamo allora $x=q_1+p_1$ e $y=q_2+p_2$, dove $q_1,q_2$ sono interi e $|p_1|<=1/2$ e $|p_2|<=1/2$.
Abbiamo allora
${(a(q_1+p_1)-b(q_2+p_2)=c),(a(q_2+p_2)+b(q_1+p_1)=d):}$
dunque
${(aq_1-bq_2+(ap_1-bp_2)=c),(aq_2+bq_1+(ap_2+bp_1)=d):}$
Ci basta dunque verificare che
$(ap_1-bp_2)^2+(ap_2+bp_1)^2<=a^2+b^2$
Banale:
$(ap_1-bp_2)^2+(ap_2+bp_1)^2=(ap_1)^2+(bp_2)^2+(ap_2)^2+(bp_1)^2=(p_1^2+p_2^2)(a^2+b^2)<=(1/4+1/4)(a^2+b^2)=1/2(a^2+b^2)<(a^2+b^2)$
Abbiamo dunque dimostrato che nel dominio degli interi di Gauss la divisione con resto di $c+di$ per $a+bi$ e' possibile:
$(c+di)=(a+bi)(x+yi)+(z+wi)$
con $z^2+w^2
"fields":
Siano $a,b,c,d$ numeri interi qualsiasi. Dimostrare che il seguente sistema, nelle incognite $x,y,z,w$, ha soluzioni intere.
${(ax-by+z=c),(ay+bx+w=d),(z^2+w^2<=a^2+b^2):}$
A questo p.to, vi dico la mia: $(Z, +, \cdot)$ è un anello euclideo in cui la norma di un elemento è rappresentata dal consueto modulo di un numero complesso. Se pertanto $a, b \in Z$ e $a^2 + b^2 > 0$, comunque scelti $c, d \in Z$, esistono $\xi, \rho \in Z$ tali che $c + id = (a+ib)\xi + \rho$ e $0 \le \rho < |a+ib|$. Da qui la tesi, posto $x = Re(\xi)$, $y = Im(\xi)$, $z = -\Re(\rho)$ e $w = -\Im(\rho)$.
EDIT: un errore nei segni.
A questo p.to, vi dico la mia: $(Z, +, \cdot)$ è un anello euclideo in cui la norma di un elemento è rappresentata dal consueto modulo di un numero complesso. Se pertanto $a, b \in Z$ e $a^2 + b^2 > 0$, comunque scelti $c, d \in Z$, esistono $\xi, \rho \in Z$ tali che $c + id = (a+ib)\xi + \rho$ e $0 \le \rho < |a+ib|$. Da qui la tesi, posto $x = Re(\xi)$, $y = Im(\xi)$, $z = \Re(\rho)$ e $w = \Im(\rho)$.
Sì, ovvio, ma il senso di questo esercizio, come ho mostrato alla fine, era proprio quello di dimostrare che $Z$ è un anello euclideo...
"fields":
Sì, ovvio, ma il senso di questo esercizio, come ho mostrato alla fine, era proprio quello di dimostrare che $Z$ è un anello euclideo...
Scusami se insisto, ma io posso provare che $Z$ è euclideo a prescindere da questo problema, e di quest'ultimo dedurre perciò la soluzione come banale conseguenza della proprietà indicata. Basta infatti osservare che ogni p.to di $CC$, fuori dal cerchio unitario, dista dall'insieme $\{2^{n/2} \cdot (\cos(\pi/2^{n+1} + k\pi/2^n) + i\sin(\pi/2^{n+1} + k\pi/2^n)): n \in NN, k = 0, 1, ..., 2^{n+1}-1\}$ di una quantità $\le {\sqrt{2}}/{2}$. Perciò, se $a, b \in ZZ$ ed $a^2+b^2 \ne 0$, risulta che ogni p.to di $CC$, fuori dal cerchio di centro l'origine e raggio $a^2+b^2$, dista da un qualche multiplo di $a+ib$ in $ZZ$ di una quantità $\le \frac{\sqrt{2}}{2} (a^2+b^2)$. E $\sqrt{2}/2$ è molto meglio che 1, no?
P.S.: comunque la tua soluzione non l'avevo letta per esteso, e quindi mi ero perduto le tue conclusioni a proposito di $ZZ$. Dopo la geometria di Thomas, tutta quell'algebra mi ha dato subito alla testa.
tutta quell'algebra mi ha dato subito alla testa.
Già, però l'algebra che ho postato ti dà immediatamente una formula semplice per calcolare quoziente e resto della divisione fra interi di Gauss, il che non è male
"fields":
Il punto è, Thomas, che quello che hai scritto è pieno di passaggi inutili e che fanno confusione... Infatti era inutile scrivere le relazioni [5] e [6] così come le condizioni p2a e p2b. Se infatti scegli F e G in modo che stiano nel reticolo, ti basta verificare la disuguaglianza... E' per questo che senza l'analisi del reticolo la dimostrazione è inesistente... Comunque in effetti è noioso formalizzare la parte geometrica, quindi tanto vale andare per via algebrica. Ecco come:
boh... perchè era inutile? le relazioni [5] e [6] sono delle condizioni necessarie e sufficienti che ho trovato per poter avere che la x e la y associate ad una certa coppia (F,G) siano numeri interi. Sono queste relazioni che il reticolo deve rispettare... e infatti le rispetta per verifica diretta! non mi basta verificare la disuguaglianza....
le "proprietà" del reticolo che non ho voglia di vedere perchè le trovo evidenti, sono che consiste in una griglia quadrata e che presa una circonferenza di raggio uguale al raggio del quadrato, questa (bordo compreso), tocca almeno un vertice... ma non è difficile...
cmq persoalmente a me piace la mia dimostrazione
.... ora magari guardo le vostre...
fields non capisco la tua posizione sulla $x$. Se x deve essere soluzione intera, perchè poni
$x=q_1+p_1$ con $q_1$ intero e $|p_1|<=1/2$
così x non esce intero se non con $p_1=0$....
chiarito questo, alla fine arrivi a questo sistema, che pare simile a quello iniziale:
${(aq_1-bq_2+(ap_1-bp_2)=c),(aq_2+bq_1+(ap_2+bp_1)=d):}$
e poi tratti $ap_1-bp_2$ come $z$ e l'altro come $w$... ancora non capisco perchè visto che non hai garanzie sul fatto che quei numeri siano interi...
qualche chiarimento?
$x=q_1+p_1$ con $q_1$ intero e $|p_1|<=1/2$
così x non esce intero se non con $p_1=0$....
chiarito questo, alla fine arrivi a questo sistema, che pare simile a quello iniziale:
${(aq_1-bq_2+(ap_1-bp_2)=c),(aq_2+bq_1+(ap_2+bp_1)=d):}$
e poi tratti $ap_1-bp_2$ come $z$ e l'altro come $w$... ancora non capisco perchè visto che non hai garanzie sul fatto che quei numeri siano interi...
qualche chiarimento?
boh... perchè era inutile? le relazioni [5] e [6] sono delle condizioni necessarie e sufficienti che ho trovato per poter avere che la x e la y associate ad una certa coppia (F,G) siano numeri interi.
Le relazioni 5 e 6 che hai scritto e cio' che ne consegue sono inutili. Infatti alla fine poni $x=k$ e $y=z$, scegliendo i punti nel reticolo. Dunque il passaggio per le relazioni e' un giro inutile. O no? Comunque e' chiaro che descrivere un'interpretazione geometrica via forum e' noioso e a volte impossibile, e una volta che la visualizzi e' ovvia.
Ma le dimostrazioni si scrivono per intero, altrimenti non conseguono il loro scopo. Se dovessi anch'io non scrivere in una dimostrazione cio' che mi sembra ovvio, ne risulterebbe che farei perdere tempo al lettore, e a me stesso che dovrei rispondere alle domande. Il bello di una dimostrazione e' che risparmia il tempo al lettore di risolvere a sua volta gli ostacoli incontrati, o no? E' cosi' che funziona il progresso matematico. Io risolvo un problema e evito a te di perderci tempo...
fields non capisco la tua posizione sulla $x$. Se x deve essere soluzione intera, perchè poni
$x=q_1+p_1$ con $q_1$ intero e $|p_1|<=1/2$
così x non esce intero se non con $p_1=0$....
Le soluzioni finali sono $x=q_1$, $y=q_2$, $z=ap_1-bp_2$, $w=ap_2+bp_1$, e le trovi nel sistema finale che ho scritto. Il fatto e' che ho usato la $x$ e la $y$ in due sistemi diversi... in effetti crea confusione.
${(aq_1-bq_2+(ap_1-bp_2)=c),(aq_2+bq_1+(ap_2+bp_1)=d):}$
e poi tratti $ap_1-bp_2$ come $z$ e l'altro come $w$... ancora non capisco perchè visto che non hai garanzie sul fatto che quei numeri siano interi...
qualche chiarimento?
Sono interi perché nell'equazione in cui sono "immersi" tutti gli altri termini sono interi.
ps: vedi, sono cascato anch'io in quello che ti ho detto. Ti ho fatto perdere tempo perche' ho tralasciato di spiegare una cosa che mi sembrava ovvia
"Thomas":
fields non capisco la tua posizione sulla $x$. [...] alla fine arrivi a questo sistema [...]:
${(aq_1-bq_2+(ap_1-bp_2)=c),(aq_2+bq_1+(ap_2+bp_1)=d):}$
e poi tratti $ap_1-bp_2$ come $z$ e l'altro come $w$... [...] non capisco perchè visto che non hai garanzie sul fatto che quei numeri siano interi...
"fields":
Sono interi perché nell'equazione in cui sono "immersi" tutti gli altri termini sono interi.
Non regge, fields: in linea di principio, anche una c.l. a coefficienti in $ZZ$ di numeri razionali può restituire un intero.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo