OliForum Matematico

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

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

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

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 $

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 as a sequence of divisors [...]

Io sta cosa proprio non l'ho capita...

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

Alla fine è l'algoritmo di wikipedia però spiegato come si deve...

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

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

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?

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 $

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

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?

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

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?

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 $. []

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?