Aviseringar
Rensa alla

Diofantiska ekvationer


Ämnesstartare

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]


   
Citera

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


   
SvaraCitera
Ämnesstartare

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.


   
SvaraCitera

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


   
SvaraCitera
Ämnesstartare

AndersLkpg:

lösning

Ah tack!
Det som är förvirrande är alla steg, men jag förstod det där någorlunda.


   
SvaraCitera

Jag tyckte aldrig om diofantiska ekvationer 🙁


   
SvaraCitera
Ämnesstartare

HobGoblin:

Jag tyckte aldrig om diofantiska ekvationer 🙁

Gör inte det jag heller nu. Fast det är ganska tufft att det gick att räkna ut sådana där ekvationer.


   
SvaraCitera

sylar:

Gör inte det jag heller nu. Fast det är ganska tufft att det gick att räkna ut sådana där ekvationer.

Hehe jo, i och för sig, men ändå 😛


   
SvaraCitera

Har en diofantisk ekvation som jag inte vet hur jag löser:
992x + 96y + 8z + 8 = 0


   
SvaraCitera

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.


   
SvaraCitera

AndersLkpg:

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

Den är således inte möjlig att lösa? :/


   
SvaraCitera
Gifted

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


   
SvaraCitera
Gifted

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


   
SvaraCitera

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.


   
SvaraCitera
Gifted

AndersLkpg:

tidsekvationer

?


   
SvaraCitera