Forumet - Diofantiska ekvationer

Diofantiska ekvationer

2152 0 17
Hur löser man denna diofantiska ekvation?

2x - 11y = 9

Försökte kopiera lösningssättet för de med HL=1 där de använder Euklides' Algoritm, men av någon anledning så får jag inte till det på denna ekvationer eftersom:

2 = 11*0 + 2
11 = 2*5 + 1

1 = (11 - 5*2) = (2-0)?
1=2?? [n]
alter ego:

En fråga bara: det ges väl vissa definitioner av hur lösningen ska se ut? Med bara ekvationen kan svaren se ut hur som helst..


Den diofantiska ekvationen ax + by = c där SGD(a,b) = 1 (SGD = största gemensamma divisor)

har den allmänna lösningen:
x = cx0 - nb
y = cy0 - na

där (x0,y0) satisfierar ax0 + by0 = 1 och kan bestämmas med hjälp av Euklides algoritm.
sylar:

Hur löser man denna diofantiska ekvation?


sylar:

2x - 11y = 9


Uppgift:
2x-11y = 9

Söks:
Alla heltal x, y som satisfierar uppgiftens ekvation

[

sylar:

x = cx0 - nb
y = cy0 - na


Rättelse:
x = cx0+nb
y = cy0-na

]

Förutsättningar:
a = 2
b = -11
c = 9 = 3*3 = 3²
|a|, |b| primtal

Euklides algoritm:
[ |a|, |b| primtal → a, b relativt prima ↔ SGD(a, b) = 1 ]
|b|/|a| = 11/2 = 5, resten 1
2/1 = 2, resten 0
SGD(a, b) = SGD(2, -11) = 1
2*(-5)-11*(-1) = -10+11 = 1

Lösning:
ax0+by0 = 1
x0 = -5
y0 = -1
x = cx0+nb = 9*(-5)+n*(-11) = -45-11n
y = cy0-na = 9*(-1)-n*2 = -9-2n

Kontroll:
2x-11y = 2(-45-11n)-11(-9-2n) = -90-22n+99+22n = 9

Resultat:
x = -45-11n = -45+11m
y = -9-2n = -9+2m
m, n heltal
(m = -n)

Länkar:
http://sv.wikipedia.org/wiki/Matematik
http://sv.wikipedia.org/wiki/Diskret_matematik
http://sv.wikipedia.org/wiki/Talteori
http://sv.wikipedia.org/wiki/Talteori#Element.C3.A4r_talteori
http://sv.wikipedia.org/wiki/Heltal
http://sv.wikipedia.org/wiki/Delbarhet
http://sv.wikipedia.org/wiki/Primtal
http://sv.wikipedia.org/wiki/Primtalsfaktorisering
http://sv.wikipedia.org/wiki/Relativt_prima
http://sv.wikipedia.org/wiki/St%C3%B6rsta_gemensamma_delare
http://sv.wikipedia.org/wiki/Minsta_gemensamma_n%C3%A4mnare
http://sv.wikipedia.org/wiki/Minsta_gemensamma_multipel
http://sv.wikipedia.org/wiki/Euklides_algoritm
http://sv.wikipedia.org/wiki/Diofantisk_ekvation
http://sv.wikipedia.org/wiki/Linj%C3%A4r_diofantisk_ekvation

Spana också in:

HobGoblin:

Har en diofantisk ekvation som jag inte vet hur jag löser:


HobGoblin:

992x + 96y + 8z + 8 = 0


En viss förenkling är tänkbar:

992x+96y+8z+8 = 0

(992x+96y+8z+8)/8 = 0/8
992x/8+96y/8+8z/8+8/8 = 0
(992/8)x+(96/8)y+(8/8)z+1 = 0
124x+12y+z+1 = 0
124x+12y = -z-1
(4/4)(124x+12y) = -(z+1)
4(124x+12y)/4 = -(z+1)
4(124x/4+12y/4) = -(z+1)
4((124/4)x+(12/4)y) = -(z+1)
4(31x+3y) = -(z+1)
z+1 = 4w, w heltal
z = 4w-1
4w = z+1
w = (z+1)/4
-(z+1) = -4w
4(31x+3y) = -4w
4(31x+3y)/4 = -4w/4
(4/4)(31x+3y) = -(4/4)w
31x+3y = -w

31x+3y+w = 0, z = 4w-1

Men efter denna förenkling så är detta tyvärr fortfarande en linjär diofantisk ekvation i tre variabler.
AndersLkpg:

Men efter denna förenkling så är detta tyvärr fortfarande en linjär diofantisk ekvation i tre variabler.


AndersLkpg:

31x+3y+w = 0,


Har ingen aning egentligen, har inte sett tidigare, men ok.

Låt oss kalla 3y+w = q eller whatever...

Då måste 31y + q = 0, så om q är delbart med 31 kan vi garanterat hitta ett y som löser ekvationen (nämligen välja y = -q/31).

Således reduceras problemet till att bestämma alla y, w så att
3y + w är en multipel av 31.

Ok, låt säga att vi väljer y till ett fixt tal, t.
Det enda sättet för att få ett tal delbart med 31 är då att välja w = 31*s - 3t för något s. (som är valfritt heltal).

Detta ger då att
(x,y,w) = (-s,t,31*s-3t)

Stoppar vi in detta i ekvationen du hade
ges då 31(-s)+3t+(31s-3t), som är noll för alla heltalsvärden på s och t.

Detta känns ok dimensionsmässigt; en diofantisk ekvation med 2 variabler har ett endimensionellt rum av lösningar, så att addera en variabel till bör då ge 2 dimensioner... i vårt fall s och t...
Eller om man nu vill lösa ursprungliga evationen:

AndersLkpg:

992x+96y+8z+8 = 0


som förkortas till

128x + 12y + z + 1 = 0

Här sätt z = z' - 1.

128x + 12y + z' = 0

Analogt enl. ovan, så måste 12y + z'=q vara delbart med 128 om det är möjlig att lösa ekvationen, och då bestäms x entydigt av att vara (12y + z')/128

Problemet blir alltså att finna alla y,z så att 128|12y + z'
Nu, om vi väljer y = t, så måste då 12t + z' = 128*s för något s.
Alltså, z' = 128s - 12t.

Således gäller det att (x,y,z') = (-s,t 128s-12t).
Substitutierar vi tillbaka fås då

(x,y,z) = ( -s, t 128s-12t + 1).

som löser ekvationen för alla heltal (s,t).
HobGoblin:

fråga


Jo, och jag beklagar ifall jag råkade uttrycka mig missvisande.

Gifted:

fullständiga lösningar


Tack så mycket för dina fullständiga lösningar av ekvationerna. Jag delar givetvis dina resonemang angående metoderna och lösningsmängdernas dimensioner och fullständighet.

Mina privata tidsekvationer visade sig dock sakna reella lösningar och tillät tyvärr inte vidare analys av ekvationernas lösbarhet i frånvaro av mer ingående talteori.