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
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 27 feb 2008, 23:44

Certo. Oppure:

Dim 2: Sia $ d = \left( \frac{a}{(a,b)}, \frac{b}{(a,b)} \right) $. $ d \cdot (a,b) $ divide sia $ a $ che $ b $, quindi deve dividere il loro MCD, quindi $ d = 1 $. []

Dim 3: Per il teorema di Bézout, esistono $ S,T $ t.c. $ aS + bT = (a,b) $. Dividendo questa per $ (a,b) $, ottengo che $ \frac{a}{(a,b)} S + \frac{b}{(a,b)} T = 1 $. Ne segue che $ \frac{a}{(a,b)} $ e $ \frac{b}{(a,b)} $ sono coprimi. []
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Mondo
Messaggi: 65
Iscritto il: 22 dic 2007, 16:00
Contatta:

Messaggio da Mondo » 02 nov 2008, 22:39

Riesumo questo vecchio topic per fare una domanda sulle diofantee lineari in più di due variabili.
La risoluzione generale è sempre la stessa (soluzione particolare + soluzioni della non omogenea) e la soluzione particolare della non omogenea si trova applicando bezout generalizzato. Ora il problema è trovare TUTTE le soluzioni della non omogenea.

Supponendo che l'equazione sia del tipo $ ax+by+ct=0 $ cerco due generatori indipendenti ponendo uguali a zero di volta in volta una delle tre variabili.

In pratica i miei generatori ad esempio potrebbero essere $ (-\frac{b}{(a,b)},\frac{a}{(a,b)} , 0) $ e $ (0, -\frac{c}{(b,c)}, \frac{b}{(b,c)}) $ da cui si ha che una generica soluzione particolare dipendente dai parametri risulta $ (-s\frac{b}{(a,b)}, s\frac{a}{(a,b)}-q\frac{c}{(b,c)}, q\frac{b}{(b,c)}) $
con $ s,q \in Z $

Trovo effettivamente tutte le soluzioni dell'omogenea associata?
Réver e révéler, c'est à peu prés le meme mot (R. Queneau)

sibilla
Messaggi: 1
Iscritto il: 27 mar 2009, 14:31

Messaggio da sibilla » 27 mar 2009, 14:35

¬[ƒ(Gabriel)³²¹º]¼+½=¾ ha scritto: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 $
Ragazzi...scusate...sto impazzendo con questo teorema...ci sono quasi ma non capisco alcune cose...potreste dirmi da dove viene ricato il 3 di 19x 3 e quindi -8 e 19? grazie mille

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 27 mar 2009, 15:22

$ ~5-(7-5)\cdot2=5+5\cdot 2-2\cdot 7=5\codt 3+7\cdot(-2) $
$ ~5=19-7\cdot2 $
$ ~7\cdot(-2)\cdot3+7\cdot(-2)=7\cdot(-8) $
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