Ajuda: identitat de Bézout factoritzant a i b…
Tenc un problema, ¿algú me pot ajudar?
Donats, a, b nombres naturals, existeixen x, y nombres sencers tals que
mcd(a,b) = ax + by.
A aquesta identitat se l’anomena identitat de Bézout, i si (x,y) compleixen la identitat de Bézout es diuen que nombres de Bézout.
Hi ha un algorisme per trobar una tupla (x,y) que es basa en l’Algorisme d’Euclides (anant cap a enrera)
Voldria un algorisme per trobar una tupla (x, y) basat en la factorització en nombres primers de a i de b. Algú sap si n’hi ha algun? Algú em pot ajudar per trobar-ne un?
Hola Xavi
no crec que existeixi l’algoritme que demanes, precisament perquè l’existència de la identitat de Bézout es una propietat dels dominis euclidians, que són més restrictius que els dominis de factorització única, i per tant has de menester la divisió euclídea per trobar-la (aquesta Algebra IV….. ;-)). Per ventura hi hagi qualque algoritme que empri d’amagat la divisió sense que es vegi, però no ho sé. Però segur que la divisió hi serà.
PS Em sap greu, feia segles que no passava per aquí, miraré de posar-me al dia
3 Abril 2008, 7:49 amMoltes gràcies Xesc per la teva opinió.
Sobre l’algoritme… sí sé que DE ==> DIP (encara m’enrecord!). I que bàsicament les propietats dels enters els heretem als DE. Tenc arguments a favor i en contra de l’existència d’aquest algorisme:
A favor:
(o sigui podem posar el mcd en funció de la factorització d’a i de b) és de suposar que podríem posar x i y en funció també de la factorització d’a i de b
1) Si podem posar el mcd com a
2) Com a mínim crec que podríem obtenir una fita (baixa) sobre el valor absolut de x i y.
3) Podríem derivar condicions que facin que x i y estiguin determinats (o almenys pertanyin a un conjunt prou petit). Per exemple, hom pot provar que:
a) Podem restringir-nos al cas de mcd(a,b) = 1:
Suposem que d = mcd(a,b). Aleshores a = d · s, i b = d · k. Llavors d = (d·s)x + (d·k)·y i simplificant 1 = sx + ky, amb s i k comprimers.
Per tant, podem restringir-nos a resoldre el problema de trobar x, y enters tals que 1 = ax + by amb a i b coprimers
b) De 1 = ax + by es dedueix que x i y han de tenir signes distints i cap dels dos ha de ser 0
c) D’aquesta mateixa equació fent mòduls, tenim que x \cong a^{-1} mod b i que y \cong b^{-1} mod a (de fet crec que és un sii: 1 = ax + by sii x \cong a^{-1} mod b i que y \cong b^{-1} mod a)
d) Una bona fita per x i y
En contra
1) En general si tenguessim un algorisme de donat la factorització a i b, poder trobar x i y tals que d = ax + by, de qualque manera sabríem calcular la factorització d’una suma a partir dels sumants, i això és impossible: donats a, b ningú sap trobar la factorització de a+b sense trobar-la. Crec que es pot reduir a aquest cas l’algorisme hipotètic.
2) Potser està relacionat amb la conjectura ABC?
Esper els teus comentaris de tornada.
Gràcies,
3 Abril 2008, 3:44 pmXavi
PS: Xesc, he trobat fites per la identitat de Bézout per polinomis però no per enters:
3 Abril 2008, 3:59 pm1) [http://atlas.mat.ub.es/personals/sombra/papers/tesis/tesis1.pdf]
2) [http://arxiv.org/abs/alg-geom/9710003v1]
3) [http://www.lix.polytechnique.fr/~giusti/publications/diot6.ps]
4) [http://arxiv.org/abs/math/9911094v1]
Hola
3 Abril 2008, 6:17 pmei, a això m’hi vaig dedicar una temporada fa…. 18 anys!!!
Hi ha treballs dels 90 on es fiten no només el grau sinó la mida dels coeficients dels polinomis coeficients a la identitat de bezout per a polinomis amb coeficients enters. Els dec tenir enterrats en una carpeta a qualque banda, si t’interessen. Pel que fa als enters, si escrius el proces per obtenir la identitat de bezout pots donar (per inducció) la forma explicita dels coeficients en funció dels quocients successius a l’algoritme d’euclides. D’aquesta forma en deduiràs una fita superior O(2^b) (on b
Pots acabar l’entrada?
Sí, podria fer “trampa” i trobar una fita de x i y emprant l’algorisme d’Euclides. Però no ho vull fer: voldria trobar x i y sense emprar-lo, només emprant la factorització d’a i b i mòduls.
No sé si és possible o no (potser fins i tot sigui no decidible!) però està bé preguntar-ho almenys.
Xavi
PS: Gràcies per tota l’ajuda. Per cert, per polinomis es pot fer: podem trobar p i q tals que 1 = a(x)p(x) + b(x)q(x) només emprant la factorització de a(x), b(x) i mòduls? Si és possible a polinomis quasi segur que ho serà a enters….. això sí que és Àlgebra IV/V al pla nou?
Xavi
4 Abril 2008, 4:45 pmUps!
volia dir “on b és el més petit d’a i b).”
La veritat és que no se m’acudeix com no emprar la divisió. Pensa en quina pinta han de tenir x i y per a p i q primers a fi que xp+yq=1. Aquí no hi ha factorització que valgui.
Emprant d’amagat la divisió: sabem que si xa+yb=1, aleshores (x+mb)a+(y-ma)b=1, i per tant pots cercar (x,y) tals que 0
4 Abril 2008, 6:35 pmXesc, crec que se t’ha tornat a tallar ;-D
Però bé, el de p i q primers fa pensar que no, que no hi ha cap algorisme…. és vera que en aquest cas no hi ha factorització que valgui,
Gràcies.
4 Abril 2008, 8:06 pmXavi
Telegraficament:
Si a i b son coprimers existeix x entre 1 i b i un y ves a saber per on tals que xa+yb=1. Aleshores proves (1-xa)/b per a x=1,….,b-1, i quan doni enter dius Bingo!. Pero fas servir divisio, no factorització.
Creuarem els dits i li donarem al submit comment
5 Abril 2008, 5:17 pmCom dedueixes que x està entre 1 i b. Podria ser el negatiu el x. Així i tot pots demostrar-ho formalment?
Xavi
5 Abril 2008, 11:30 pmTelegraficament: a una solucio (x,y) de xa+yb=1 la pots modificar (x+mb,y-ma) amb m de Z i encara dona solucio: aleshores, si fas la divisió euclidea x=qb+r amb 0
6 Abril 2008, 8:44 amUn altre cop Xesc. Per favor, pots tornar a acbar el comentari. No sé què te passa!….
Xavi
6 Abril 2008, 9:48 amNo, t’ho enviare per mail d’aqui a una estona i llestos!
6 Abril 2008, 4:07 pmEn/na Cesc Rossello ha escrit:
6 Abril 2008, 6:58 pm> Xavi
>
> Si (x, y) es tal que ax+by=1, aleshores tota altra (x+mb,y-ma) tambe. Aleshores, donada una parella (x,y) tal que xa+yb=1, dividixes euclidianament x per b i tens
> x=qb+x’ amb 0
> Ara que saps que hi ha un x’ entre 1 i b-1 per al que existeix un y’ tal que x’a+y’b=1, nomes has de calcular (1-xa)/b per a cada x=1,…,b-1 fins que trobis un valor per al que aixo doni enter. Tindras la parella que cercaves
>
> Ara be, has fet servir divisio dos cops.
>
>
> No se que passa amb els meus comentaris, que se’m tallen, ho sento. Penja’l tu, a mem si tens mes sort (tot i que no se si hi ha qualcú llevat de tu interessat en saber com acabava aixo…..)
>
> Memories!
>
> Cesc
Gràcies Xesc per la demostració.
Al final idò he de dividir b-1 vegades si tenc mala sort.
No empr l’algorisme d’Euclides i això té una avantatge: puc provar “fàcilment” per exempla el teorema de Bézout (existeix aquests x i y tq ax + by =1). Amb Euclides has de provar-ho anant cap a enrera i formalment és un rotllo. La desvantatge és que crec que és més complex computacionalment que fer Euclides.
Ei gràcies Xesc per tot el teu interès.
I sí, ho pensaré al blog. Qui sap….
Xavi
6 Abril 2008, 6:59 pmJejeje
a tu tambe se t’ha menat un tros!!!
El primer paràgraf ha d’acabar
> x=qb+x’ amb 0 concret y’=y+qa) tal que x’a+y’b=1.
A mem si surt!
7 Abril 2008, 12:29 pmAixò és un rotllo!
7 Abril 2008, 6:33 pmA mi també me n’ha menjat un tros!!!!!!!!!!!! Au, per avall!
8 Abril 2008, 7:21 am