Teorema di Bezeout e equazioni diofantee

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Avatar utente
angus89
Messaggi: 281
Iscritto il: 28 ott 2006, 10:12

Teorema di Bezeout e equazioni diofantee

Messaggio da angus89 » 24 feb 2008, 01:46

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...
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

Avatar utente
edriv
Messaggi: 1638
Iscritto il: 16 feb 2006, 19:47
Località: Gradisca d'Isonzo
Contatta:

Messaggio da edriv » 24 feb 2008, 10:40

Questo sito lo spiega parecchio bene:
http://www.answers.com/topic/extended-e ... technology

in particolare è abbastanza pratica la sezione "the table method".

¬[ƒ(Gabriel)³²¹º]¼+½=¾
Messaggi: 849
Iscritto il: 22 ott 2006, 14:36
Località: Carrara/Pisa

Messaggio da ¬[ƒ(Gabriel)³²¹º]¼+½=¾ » 24 feb 2008, 11:39

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 $
Ultima modifica di ¬[ƒ(Gabriel)³²¹º]¼+½=¾ il 25 feb 2008, 14:41, modificato 1 volta in totale.

Avatar utente
angus89
Messaggi: 281
Iscritto il: 28 ott 2006, 10:12

Messaggio da angus89 » 24 feb 2008, 11:48

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 sò se è la mia impressione ma la chiarezza...bho...
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
link di ediv ha scritto: [...]The main idea is to think of the equation chain Immagine as a sequence of divisors Immagine[...]
Io sta cosa proprio non l'ho capita...
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

Avatar utente
angus89
Messaggi: 281
Iscritto il: 28 ott 2006, 10:12

Messaggio da angus89 » 24 feb 2008, 11:57

grazie ¬[ƒ(Gabriel)³²¹º]¼+½=¾...ora è chiaro...

Alla fine è l'algoritmo di wikipedia però spiegato come si deve...
:D
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

Avatar utente
angus89
Messaggi: 281
Iscritto il: 28 ott 2006, 10:12

Messaggio da angus89 » 24 feb 2008, 20:12

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...
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

EvaristeG
Site Admin
Messaggi: 4791
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Messaggio da EvaristeG » 24 feb 2008, 21:10

No.
Prova a risolvere col tuo metodo
$ 1343x+1024y=1 $.

Avatar utente
angus89
Messaggi: 281
Iscritto il: 28 ott 2006, 10:12

Messaggio da angus89 » 25 feb 2008, 00:02

EvaristeG ha scritto:No.
Prova a risolvere col tuo metodo
$ 1343x+1024y=1 $.
Effettivamente il mio metodo risolve solo qualche caso...
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

¬[ƒ(Gabriel)³²¹º]¼+½=¾
Messaggi: 849
Iscritto il: 22 ott 2006, 14:36
Località: Carrara/Pisa

Messaggio da ¬[ƒ(Gabriel)³²¹º]¼+½=¾ » 25 feb 2008, 00:49

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)
il problema è che quella che hai trovato non è una soluzione, basta sostituire per accorgersene...le soluzioni dovrebbero essere:

$ \left\{\begin{matrix} x = -321 + 1024k \\ y = 421 - 1343k \end{matrix}\right $

Avatar utente
angus89
Messaggi: 281
Iscritto il: 28 ott 2006, 10:12

Messaggio da angus89 » 25 feb 2008, 08:26

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
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

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 25 feb 2008, 14:15

angus89 ha scritto:è l'algoritmo di wikipedia però spiegato come si deve...
Non voglio togliere nulla a Wikipedia, ma a dirla tutta, l'algoritmo e' di Euclide...

Ok. Ora passiamo al commento serio.
angus89 ha scritto:Il mio timore è di non trovarle tutte
Timore ben fondato, infatti, c'e' un errore nel post di Gabriel:
Gabriel ha scritto:$ ax_0 + by_0 = 0 $ ha soluzioni $ x_0 = bk $ e $ y_0 = -ak $ con $ k \in \mathbb{Z} $
Senz'altro quelle che dice Gabriel sono soluzioni, ma non sono tutte.
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."

¬[ƒ(Gabriel)³²¹º]¼+½=¾
Messaggi: 849
Iscritto il: 22 ott 2006, 14:36
Località: Carrara/Pisa

Messaggio da ¬[ƒ(Gabriel)³²¹º]¼+½=¾ » 25 feb 2008, 14:35

Marco ha scritto: 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?
Ero sicuro di averlo scritto ma in effetti non ho detto che se $ (a,b) \mid c $ bisogna dividere l'equazione per $ (a,b) $ :?

Avatar utente
angus89
Messaggi: 281
Iscritto il: 28 ott 2006, 10:12

Messaggio da angus89 » 25 feb 2008, 16:19

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?
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

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 25 feb 2008, 23:04

angus89 ha scritto:trovo tutte le soluzioni?
Sì. Ricapitoliamo: dati $ a,b $ interi non nulli, le soluzioni intere di
$ 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."

Avatar utente
angus89
Messaggi: 281
Iscritto il: 28 ott 2006, 10:12

Messaggio da angus89 » 27 feb 2008, 22:47

Marco ha scritto: Ora, $ \frac{a}{(a,b)} $ e $ \frac{b}{(a,b)} $ sono coprimi [perché? Esercizio: trovare almeno due dimostrazioni]
ho paura di esser banale o di aver capito male quello che mi si chiede di dimostrare...ma mi pare legico che
$ \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

Rispondi