Identità di Bèzout e equazioni in Z

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
Willy67
Messaggi: 56
Iscritto il: 24 nov 2009, 19:08

Identità di Bèzout e equazioni in Z

Messaggio da Willy67 »

Ciao a tutti avrei bisogno di alcuni chiarimenti sull'identità di bezout e la risoluzione di equazioni a due incognite in Z.
Se io ho un equazione $ ax+by= c $ a coefficienti in Z, sia $ d = (a,b) $ potrò scrivere l'equazione come $ d(a_1x+b_1y)=c $ per cui $ d $ divide a, b ma anche c. Siccome $ (a,b) = am+bn $ con m e n interi per l'identità di bezout segue $ (am+bn)q=c $ dove q è intero e $ amq+bnq=c $ - -> $ a(mq)+b(nq) =c $ Per cui due soluzioni intere sono $ x_0 =mq $ e$ y_0=nq $. Siccome m e n sono i coefficienti della combinazione lineare di a e b e sono più di uno ( infiniti forse? ), segue che le soluzioni intere sono + di una. Ma come determinare la soluzione generale? Ho trovato che se $ (x_0,y_0) $ sono soluzioni allora anche $ (x_1,y_1) $ lo sono essendo $ x_1=x_0+k(\frac{b}{d}) $ e $ y_1=y_0-k(\frac{a}{d} $ ma non lo comprendo assolutamente.
Grazie a chi mi possa aiutare
Willy67
Messaggi: 56
Iscritto il: 24 nov 2009, 19:08

Messaggio da Willy67 »

nessuno che risponda?
Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai »

Uso una notazione leggermente diversa che mi permetta di non scrivere in LaTeX.

Abbiamo la diofantea dax+dby=c con (a,b)=1, vogliamo trovare tutte le coppie (x,y) che la risolvono, per a,b,c,d fissati.

Una coppia (x,y) esiste per il teorema di Bezout, e la sappiamo trovare con l'algoritmo di Euclide. Vogliamo le altre coppie.

Se (z,w) è un'altra soluzione, allora sottraendo membro a membro le 2 equazioni si ricava
d(ax+by-az-bw) = c-c
a(x-z) = b(w-y).
Siccome a e b sono coprimi, x-z dev'essere multiplo di b e w-y dev'essere multiplo di a. Ma se x-z=kb e w-y=ja, vale akb=bja, da cui k=j. Quindi la nuova soluzione dev'essere della forma (x+kb,y-ka), per un opportuno k intero.

Verifichiamo che tutte queste coppie sono soluzioni. Per ogni k intero dev'essere verificata
da(x+kb)+db(y-ka) = c
dax+dby+dabk-dabk = c
dax+dby = c,
che è vera perché (x,y) è soluzione della diofantea.
[quote="Pigkappa"]Penso che faresti un favore al mondo se aprissi un bel topic di bestemmie da qualche parte in modo che ti bannino subito.[/quote]
Willy67
Messaggi: 56
Iscritto il: 24 nov 2009, 19:08

Messaggio da Willy67 »

bene, quindi significa che se $ (x_0,y_0) $ sono soluzioni dell'equazione allora $ x_1=x_0+kb $ e $ y_1= y_0-ka $ sono anche soluzioni. Perchè ora questo libro indica invece $ x_1=x_0+k(\frac{b}{d}) $ e $ y_1=y_0-k(\frac{a}{d} $ che è tuttavia comunque una soluzione?
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

perche' Tibor ha usato la notazione
dax+dby=c (a,b)=1
mentre il libro usa
ax+by=c (a,b)=d


Onestamente io userei
ax+by=c (a,b)=1
tanto i casi di sopra si riconducono facilmente a questo
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Willy67
Messaggi: 56
Iscritto il: 24 nov 2009, 19:08

Messaggio da Willy67 »

ma scusate quelle due notazioni se d è il massimo comun divisore di a e b non si equivalgono
Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ »

hai
a=> da
b=> db
si equivalgono e infatti se fai la trasformazione nella formula del libro vedrai che hai la stessa di Tibor
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Rispondi