Teorema di Bezeout e equazioni diofantee
Teorema di Bezeout e equazioni diofantee
Ho provato a cercare un pò sulla rete ma con risultati poco sodisfacenti...
Chinque conosca il teorema di di Bezeout e le applicazioni non esiti a postare...
Inoltre come si risolvono le equazioni della seguente forma?
$ \dispaystyle ax+by=c $
Non mi rifilate l'algoritmo di wikipedia...XD
Grazie in anticipo...
Chinque conosca il teorema di di Bezeout e le applicazioni non esiti a postare...
Inoltre come si risolvono le equazioni della seguente forma?
$ \dispaystyle ax+by=c $
Non mi rifilate l'algoritmo di wikipedia...XD
Grazie in anticipo...
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
Questo sito lo spiega parecchio bene:
http://www.answers.com/topic/extended-e ... technology
in particolare è abbastanza pratica la sezione "the table method".
http://www.answers.com/topic/extended-e ... technology
in particolare è abbastanza pratica la sezione "the table method".
-
- Messaggi: 849
- Iscritto il: 22 ott 2006, 14:36
- Località: Carrara/Pisa
Teorema di Bezout
se a e b sono interi e d è il loro MCD esistono m e n tali che $ am + bn = d $
Per calcolare m e n si può ricorrere al seguente algoritmo:
Esempio:
$ a=45 $ e $ b=19 $, per prima cosa si divide a con b e si ottiene un resto, poi si divide b col resto e si ottiene un'altro resto e così via finche non si arriva al MCD tra a e b.
$ \boxed{45} = \boxed{19} \cdot 2 + \boxed{7} $
$ \boxed{19} = \boxed{7} \cdot 2 + \boxed{5} $
$ \boxed{7} = \boxed{5} \cdot 1 + \boxed{2} $
$ \boxed{5} = \boxed{2} \cdot 2 +\boxed{\boxed{1}} $
andando a ritroso si ricava 1 dall'ultima riga, 2 dalla penultima, 5 dalla terzultima e così via , allora si ottiene:
$ \boxed{1} = \boxed{5} - \boxed{\boxed{2}} \cdot 2 $
$ = 5 - (7 - 5) \cdot 2 = \boxed{\boxed{5}} \cdot 3 + \boxed{7} \cdot (-2) $
$ (19 - 7 \cdot 2) \cdot 3 + 7 \cdot (-2) = \boxed{19} \cdot 3 + \boxed{\boxed{7}} \cdot{-8} $
$ 19 \cdot 3 + (45 - 19 \cdot 2) \cdot (-8) = \boxed{45} \cdot (-8) + \boxed{19} \cdot (19) $
quindi $ m= -8 $ e $ n=19 $
Per risolvere la diofantea $ ax+by = c $ il metodo è questo:
ammette almeno una soluzione sse $ (a,b) \mid c $ e in tal caso sono infinite.
Se $ (a,b) \mid c $ si divide l'equazione per $ (a,b) $.
Per trovare tutte le soluzioni, si trovano le soluzioni della omogenea (dopo aver diviso per (a,b)) e si sommano a una soluzione della diofantea.
$ ax_0 + by_0 = 0 $ ha soluzioni $ x_0 = bk $ e $ y_0 = -ak $ con $ k \in \mathbb{Z} $
per trovare una soluzione della non oogenea, che chiamiamo x' e y', si trovano le soluzioni di $ ax + by = d $ (con $ d=(a,b) $) con il Teorema di Bezout e si moltiplicano per $ \frac{c}{d} $.
Quindi tutte le soluzioni sono date da
$ \displaystyle \left\{\begin{matrix} x = x' + x_0 \\ y = y' + y_0 \end{matrix}\right $
se a e b sono interi e d è il loro MCD esistono m e n tali che $ am + bn = d $
Per calcolare m e n si può ricorrere al seguente algoritmo:
Esempio:
$ a=45 $ e $ b=19 $, per prima cosa si divide a con b e si ottiene un resto, poi si divide b col resto e si ottiene un'altro resto e così via finche non si arriva al MCD tra a e b.
$ \boxed{45} = \boxed{19} \cdot 2 + \boxed{7} $
$ \boxed{19} = \boxed{7} \cdot 2 + \boxed{5} $
$ \boxed{7} = \boxed{5} \cdot 1 + \boxed{2} $
$ \boxed{5} = \boxed{2} \cdot 2 +\boxed{\boxed{1}} $
andando a ritroso si ricava 1 dall'ultima riga, 2 dalla penultima, 5 dalla terzultima e così via , allora si ottiene:
$ \boxed{1} = \boxed{5} - \boxed{\boxed{2}} \cdot 2 $
$ = 5 - (7 - 5) \cdot 2 = \boxed{\boxed{5}} \cdot 3 + \boxed{7} \cdot (-2) $
$ (19 - 7 \cdot 2) \cdot 3 + 7 \cdot (-2) = \boxed{19} \cdot 3 + \boxed{\boxed{7}} \cdot{-8} $
$ 19 \cdot 3 + (45 - 19 \cdot 2) \cdot (-8) = \boxed{45} \cdot (-8) + \boxed{19} \cdot (19) $
quindi $ m= -8 $ e $ n=19 $
Per risolvere la diofantea $ ax+by = c $ il metodo è questo:
ammette almeno una soluzione sse $ (a,b) \mid c $ e in tal caso sono infinite.
Se $ (a,b) \mid c $ si divide l'equazione per $ (a,b) $.
Per trovare tutte le soluzioni, si trovano le soluzioni della omogenea (dopo aver diviso per (a,b)) e si sommano a una soluzione della diofantea.
$ ax_0 + by_0 = 0 $ ha soluzioni $ x_0 = bk $ e $ y_0 = -ak $ con $ k \in \mathbb{Z} $
per trovare una soluzione della non oogenea, che chiamiamo x' e y', si trovano le soluzioni di $ ax + by = d $ (con $ d=(a,b) $) con il Teorema di Bezout e si moltiplicano per $ \frac{c}{d} $.
Quindi tutte le soluzioni sono date da
$ \displaystyle \left\{\begin{matrix} x = x' + x_0 \\ y = y' + y_0 \end{matrix}\right $
Ultima modifica di ¬[ƒ(Gabriel)³²¹º]¼+½=¾ il 25 feb 2008, 14:41, modificato 1 volta in totale.
Non sò se è la mia impressione ma la chiarezza...bho...edriv ha scritto:Questo sito lo spiega parecchio bene:
http://www.answers.com/topic/extended-e ... technology
in particolare è abbastanza pratica la sezione "the table method".
non capisco perchè la gente non si spreca a scrivere qualche riga in più per rendere chiaro un concetto...(naturalmente mi firerisco al link...)
saranno le difficoltà legate alla lingua...mah
Io sta cosa proprio non l'ho capita...link di ediv ha scritto: [...]The main idea is to think of the equation chain as a sequence of divisors [...]
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
grazie ¬[ƒ(Gabriel)³²¹º]¼+½=¾...ora è chiaro...
Alla fine è l'algoritmo di wikipedia però spiegato come si deve...
Alla fine è l'algoritmo di wikipedia però spiegato come si deve...
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
Allora...premetto di aver capito come si utilizza l'algoritmo per risolvere le equazioni nella forma $ \dispaystyle a \cdot x + b \cdot y = c $
Ma non sò per quale motivo mi viene faticolo applicarlo...
Allora ho sviluppato un mio metodo(del quale sono insicuro) che espongo brevemente
metodo
$ \displaystyle \\a \cdot x + b \cdot y = c $
con $ \dispaystyle a $ e $ \displaystyle b $ termini noti.
Allora la condizione affinchè sia risolvibile questa equazione è che
$ \dispaystyle c=r \cdot MCD(a,b) $
per comodità poniamo
$ \displaystyle \\ h=MCD(a,b) \\ a \cdot x + b \cdot y = h $
E per ora risolviamo questa nel seguente modo:
Scriviamo $ \dispaystyle a $ in funzione di $ \dispaystyle b $(o viceversa), ovvero come
$ \displaystyle a=k \cdot b + h $
Faccio notare che deve essere necessariamente $ \dispaystyle h $ (che risulta essere il resto della divisione tra $ \dispaystyle a $ e $ \dispaystyle b $) per l'algoritmo di Euclide.
Detto questo riscriviamo come
$ \dispaystyle a-k \cdot b=h $
Che è proprio la soluzione d'equazione data, in questo caso banale
$ \dispaystyle\\ x=1 \\ y=- k $
Ma dato che l'equazione iniziale prevedeva che dovessimo risolvere quest'altro tipo di equazione
$ \displaystyle \\a \cdot x + b \cdot y = c $
dove $ \dispaystyle c=r \cdot MCD(a,b) $
o per come abbiamo messo le cose $ \dispaystyle c=r \cdot h $
Basterà moltiplicare tutto per $ \dispaystyle r $ e ottenere
$ \dispaystyle r \cdot (a)-k\cdot r \cdot (b)=c $
E a questo punto le nuove soluzioni sono
$ \dispaystyle \\ x=r \\ y= - k \cdot r $
E per trovare le altre soluzioni
$ \dispaystyle \\ x_{n}=x+k \cdot b \\ y_{n}=y-k \cdot a $
Dove $ \displaystyle k $ è un numero intero...
Spero di esser stato abbastanza chiaro anche se credo di aver riscritto la stessa cosa in un altro modo, se è così scusate l'ignoranza, ma la mia paura è che questo metodo "mangi" qualche soluzione(sto enfatizzando un pò)...
Se necessario posto qualche esempio di applicazione...
Ma non sò per quale motivo mi viene faticolo applicarlo...
Allora ho sviluppato un mio metodo(del quale sono insicuro) che espongo brevemente
metodo
$ \displaystyle \\a \cdot x + b \cdot y = c $
con $ \dispaystyle a $ e $ \displaystyle b $ termini noti.
Allora la condizione affinchè sia risolvibile questa equazione è che
$ \dispaystyle c=r \cdot MCD(a,b) $
per comodità poniamo
$ \displaystyle \\ h=MCD(a,b) \\ a \cdot x + b \cdot y = h $
E per ora risolviamo questa nel seguente modo:
Scriviamo $ \dispaystyle a $ in funzione di $ \dispaystyle b $(o viceversa), ovvero come
$ \displaystyle a=k \cdot b + h $
Faccio notare che deve essere necessariamente $ \dispaystyle h $ (che risulta essere il resto della divisione tra $ \dispaystyle a $ e $ \dispaystyle b $) per l'algoritmo di Euclide.
Detto questo riscriviamo come
$ \dispaystyle a-k \cdot b=h $
Che è proprio la soluzione d'equazione data, in questo caso banale
$ \dispaystyle\\ x=1 \\ y=- k $
Ma dato che l'equazione iniziale prevedeva che dovessimo risolvere quest'altro tipo di equazione
$ \displaystyle \\a \cdot x + b \cdot y = c $
dove $ \dispaystyle c=r \cdot MCD(a,b) $
o per come abbiamo messo le cose $ \dispaystyle c=r \cdot h $
Basterà moltiplicare tutto per $ \dispaystyle r $ e ottenere
$ \dispaystyle r \cdot (a)-k\cdot r \cdot (b)=c $
E a questo punto le nuove soluzioni sono
$ \dispaystyle \\ x=r \\ y= - k \cdot r $
E per trovare le altre soluzioni
$ \dispaystyle \\ x_{n}=x+k \cdot b \\ y_{n}=y-k \cdot a $
Dove $ \displaystyle k $ è un numero intero...
Spero di esser stato abbastanza chiaro anche se credo di aver riscritto la stessa cosa in un altro modo, se è così scusate l'ignoranza, ma la mia paura è che questo metodo "mangi" qualche soluzione(sto enfatizzando un pò)...
Se necessario posto qualche esempio di applicazione...
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
Effettivamente il mio metodo risolve solo qualche caso...EvaristeG ha scritto:No.
Prova a risolvere col tuo metodo
$ 1343x+1024y=1 $.
stavo facendo alcuni esercizi tutti simili e il mio metodo sembrava andare alla grande (che deficiente che sono)...
Comunque sia, da questa cosa nasce una cosa seria...
Alla fine risolvere questo tipo di equazione
$ \dispaystyle a \cdot x + b \cdot y = c $
(negli interi)
equivale a risolvere
$ \dispaystyle a \cdot x - b \cdot y = c $
Però questa seconda a differenza della prima si può risolvere abbastanza facilmente con la proprietà del massimo comune divisore e l'algoritmo di Euclide...
Il mio dubbio è se risolverla in quel modo mi fà saltare qualche soluzione...
Tipo la tua
$ 1343x+1024y=1 $
risolta con quello che ho appena detto viene
$ \dispaystyle \\ x=-2081 \\ y=27281 $
(non mi son ricercato la soluzione più piccola ma la prima che è venuta)
E poi per trovare le altre soluzioni solito metodo
$ \dispaystyle \\ $x_{n}=x+k \cdot b \\ $y_{n}=y-k \cdot a $
Però sempre il solito dubbio...manca qualche soluzione?
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
-
- Messaggi: 849
- Iscritto il: 22 ott 2006, 14:36
- Località: Carrara/Pisa
il problema è che quella che hai trovato non è una soluzione, basta sostituire per accorgersene...le soluzioni dovrebbero essere:angus89 ha scritto: $ 1343x+1024y=1 $
risolta con quello che ho appena detto viene
$ \dispaystyle \\ x=-2081 \\ y=27281 $
(non mi son ricercato la soluzione più piccola ma la prima che è venuta)
$ \left\{\begin{matrix} x = -321 + 1024k \\ y = 421 - 1343k \end{matrix}\right $
avrò sbagliato a scrivere perchè ieri sera l'avevo trovata...
comunque...a partire da una soluzione si possono trovarte tutte le altre con quel metodo?
Ovvero con
$ \dispaystyle \\ x_{n}=x+k \cdot b \\ y_{n}=y+k \cdot b $
Il mio timore è di non trovarle tutte
comunque...a partire da una soluzione si possono trovarte tutte le altre con quel metodo?
Ovvero con
$ \dispaystyle \\ x_{n}=x+k \cdot b \\ y_{n}=y+k \cdot b $
Il mio timore è di non trovarle tutte
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
Non voglio togliere nulla a Wikipedia, ma a dirla tutta, l'algoritmo e' di Euclide...angus89 ha scritto:è l'algoritmo di wikipedia però spiegato come si deve...
Ok. Ora passiamo al commento serio.
Timore ben fondato, infatti, c'e' un errore nel post di Gabriel:angus89 ha scritto:Il mio timore è di non trovarle tutte
Senz'altro quelle che dice Gabriel sono soluzioni, ma non sono tutte.Gabriel ha scritto:$ ax_0 + by_0 = 0 $ ha soluzioni $ x_0 = bk $ e $ y_0 = -ak $ con $ k \in \mathbb{Z} $
Controesempio:
$ a=b=2 $
$ (1,-1) $ e' soluzione di $ 2 x + 2 y = 0 $, ma non e' della forma $ (2k, -2k) $.
Come si aggiusta il ragionamento?
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
-
- Messaggi: 849
- Iscritto il: 22 ott 2006, 14:36
- Località: Carrara/Pisa
Per Marco...sò che è l'algoritmo di euclide...o per lo meno una sua applicazione...Ma è spiegato male lostesso su wiki...
ok in definitiva con queste correzioni...trovo tutte le soluzioni?
E poi visto che ci siamo
$ \display a \cdot x + b \cdot y + c \cdot z = d $
Trovata la prima soluzione...come si trovano le altre?
ok in definitiva con queste correzioni...trovo tutte le soluzioni?
E poi visto che ci siamo
$ \display a \cdot x + b \cdot y + c \cdot z = d $
Trovata la prima soluzione...come si trovano le altre?
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
Sì. Ricapitoliamo: dati $ a,b $ interi non nulli, le soluzioni intere diangus89 ha scritto:trovo tutte le soluzioni?
$ ax + by = 0 $ sono TUTTE e SOLE della forma
$ x = k \frac{b}{(a,b)}; y = -k \frac{a}{(a,b)} $.
Dim.: Quelle scritte sono ovviamente soluzioni. Dimostriamo che non ce ne sono altre. Sia $ (x,y) $ una soluzione. Se dimostro che $ x $ è multiplo di $ \frac{b}{(a,b)} $, ho vinto.
So che $ ax + by = 0 $. Allora $ b | ax $ il che succede sse $ \frac{b}{(a,b)} | \frac{ax}{(a,b)} $.
Ora, $ \frac{a}{(a,b)} $ e $ \frac{b}{(a,b)} $ sono coprimi [perché? Esercizio: trovare almeno due dimostrazioni], quindi $ \frac{b}{(a,b)} | x $. []
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."
- - - - -
"Well, master, we're in a fix and no mistake."
ho paura di esser banale o di aver capito male quello che mi si chiede di dimostrare...ma mi pare legico cheMarco ha scritto: Ora, $ \frac{a}{(a,b)} $ e $ \frac{b}{(a,b)} $ sono coprimi [perché? Esercizio: trovare almeno due dimostrazioni]
$ \dispaystyle (a,b) $ raccoglie tutti i fattori comuni ad $ \dispaystyle a $ e $ \dispaystyle b $, quindi nel momento in cui dividiamo $ \dispaystyle a $ per$ \dispaystyle (a,b) $ e $ \dispaystyle b $ per $ \dispaystyle (a,b) $ li priviamo dei loro fattori comuni e di conseguenza li rendiamo comprimi...
Ma era veramente questo?
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui