11 svar
114 visningar
Lisa Mårtensson är nöjd med hjälpen!
Lisa Mårtensson 307
Postad: 9 feb 2019

Diofantisk ekvation

Jag har den diofantiska ekvationen 19x + 71y = 4000 och jag ska finna samtliga positiva lösningar.

En diofantisk ekvation har enbart heltalslösningar, så mycket vet jag. Hur ska jag börja?

tomast80 2074
Postad: 9 feb 2019

Se exempel här: http://staff.www.ltu.se/~larserik/applmath/chap10/part4.html

Tillämpa samma metod på din ekvation. Återkom ifall du fastnar på något steg.

Albiki 3270
Postad: 10 feb 2019 Redigerad: 10 feb 2019

Hej!

Det gäller att 71=4·19-571 = 4\cdot 19-5 och därför även 4·71=16·19-20=15·19-14\cdot 71 = 16\cdot 19 - 20 = 15\cdot 19 - 1 varför

    1=15·19+(-4)·711 = 15 \cdot 19 +(-4)\cdot 71.

Notera att det finns oändligt många heltal som har denna egenskap; addera och subtrahera n·19·71n\cdot 19\cdot 71 till denna identitet för att få

    1=(15+71n)·19+(-4-19n)·711 = (15+71n)\cdot 19 + (-4-19n)\cdot 71

Multiplicera detta med 40004000 för att få

    4000=(4000·15+n·4000·71)·19+(-4·4000-n·4000·19)·714000 = (4000\cdot 15+n\cdot 4000\cdot 71)\cdot 19 + (-4\cdot 4000-n\cdot 4000 \cdot 19) \cdot 71.

Detta ger dig alla heltalslösningar:

x=60000+284000nx = 60000 + 284000n och y=-16000-76000ny = -16000-76000n, där nn betecknar ett godtyckligt heltal.

Laguna 3301
Postad: 11 feb 2019

4000 = (4000*15 + n*71)*19 + (-4*4000 - n*19)*71 är bättre.

Den homogena delen, eller vad vi ska kalla den, behöver inte multipliceras med 4000.

Lisa Mårtensson 307
Postad: 11 feb 2019

Tack så mycket för förklaringar. Det här tyckte jag var svårt.

Lisa Mårtensson 307
Postad: 12 feb 2019 Redigerad: 12 feb 2019

Hej!

Här är nu min redovisning av hur jag löste uppgiften med er hjälp och kurslitteraturen:

 

Uppgiften är att finna samtliga positiva lösningar till den diofantiska ekvationen

19x + 71y = 4000,

som kan skrivas på formen

ax + by = c, 

där a och b är givna heltal och vi bara är intresserade av heltalslösningar x och y.

 

Ett nödvändigt villkor för att det ska finnas lösningar till den diofantiska ekvationen

ax + by = c är att SGD(a, b) delar c.

Att SGD(a, b) = 1 i vår ekvation kan vi visa genom att använda Euklides algoritm på (19, 71):

71 = 3 * 19 + 14

19 = 1 * 14 + 5

14 = 2 * 5 + 4

5 = 1 * 4 + 1

4 = 4 * 1 + 0

vilket ger SGD = 1, r1=14, r2=5, r3=4, r4=0.

SGD (a, b) delar c ty 1 delar 4000. Vi vet således att det finns lösningar till vår ekvation.

I de fall där SGD(a, b) = 1 har ekvationen oändligt många lösningar, givet en enda lösning (x0, y0), vilken är en partikulärlösning till ekvationen.

 

Ekvationen ax + by = c där SGD(a, b) = 1 hat den allmänna lösningen

x = x0-bny = y0+an

där n är ett godtyckligt heltal och (x0, y0) är partikulärlösning till ekvationen.

 

För att finna en partikulärlösning till ekvationen söker jag en lösning till hjälpekvationen 

ax + by = 1.

 

Genom att betrakta resultatet av att använda Euklides algoritm ovan, ser jag att det gäller att 71 = 4 * 19 - 5 och därför även att 4 * 71 = 16 * 19 - 20 = 15 * 19 - 1 varför

1 = 15 * 19 +(-4) * 71, och vi har partikulärlösning (15, -4) till hjälpekvationen ax + by = 1.

 

Ett alternativt sätt att hitta partikulärlösningen är att lösa ut resterna i schemat:

14 = 71 - 3 * 19

5 = 19 - 1 * 14

4 = 14 - 2 * 5

1 = 5 - 1 * 4

och därefter köra Euklides algoritm baklänges och uttrycka SGD(19, 71) som en linjärkombination av 19 och 71. Vi utgår här från den sista likheten 1 = 5 - 1 * 4 och ersätter 4 i denna med uttrycket för 4 i den föregående ekvationen:

1 = 5 - 1(14 - 2 * 5) = 3 * 5 - 1 * 14

= 3(19 - 1 * 14) - 1 * 14 = 3 * 19 - 4 * 14

= 3 * 19 - 4(71 - 3 * 19) = 15 * 19 - 4 * 71,

dvs. att 19 * 15 + 71 * (-4) = 1.

 

Den ursprungliga ekvationen 19x + 71y = 4000 har då en partikulärlösning

(4000 * 15, 4000 * (-4)) = (60 000, -16 000).

 

Sammanfattningsvis är då den allmänna lösningen x = 60 000 - 71ny = -16 000 + 19n.

Lisa Mårtensson 307
Postad: 12 feb 2019 Redigerad: 12 feb 2019
Albiki skrev:

Notera att det finns oändligt många heltal som har denna egenskap; addera och subtrahera n·19·71n\cdot 19\cdot 71 till denna identitet för att få

    1=(15+71n)·19+(-4-19n)·711 = (15+71n)\cdot 19 + (-4-19n)\cdot 71

Multiplicera detta med 40004000 för att få

    4000=(4000·15+n·4000·71)·19+(-4·4000-n·4000·19)·714000 = (4000\cdot 15+n\cdot 4000\cdot 71)\cdot 19 + (-4\cdot 4000-n\cdot 4000 \cdot 19) \cdot 71.

Detta ger dig alla heltalslösningar:

x=60000+284000nx = 60000 + 284000n och y=-16000-76000ny = -16000-76000n, där nn betecknar ett godtyckligt heltal.

Detta förstod jag inte riktigt och jag undrar om ni tycker att min lösning kan stämma trots att den är så annorlunda än Albikis? Jag ska ju tydligen addera och subtrahera 19 * 71 också för att bli klar, vilket jag inte gjort i min lösning. I kurslitteraturen har jag tolkat det som att man kan svara så som jag gjorde. Men har jag då täckt in ALLA positiva lösningar?

Laguna 3301
Postad: 13 feb 2019
Lisa Mårtensson skrev:
Albiki skrev:

Notera att det finns oändligt många heltal som har denna egenskap; addera och subtrahera n·19·71n\cdot 19\cdot 71 till denna identitet för att få

    1=(15+71n)·19+(-4-19n)·711 = (15+71n)\cdot 19 + (-4-19n)\cdot 71

Multiplicera detta med 40004000 för att få

    4000=(4000·15+n·4000·71)·19+(-4·4000-n·4000·19)·714000 = (4000\cdot 15+n\cdot 4000\cdot 71)\cdot 19 + (-4\cdot 4000-n\cdot 4000 \cdot 19) \cdot 71.

Detta ger dig alla heltalslösningar:

x=60000+284000nx = 60000 + 284000n och y=-16000-76000ny = -16000-76000n, där nn betecknar ett godtyckligt heltal.

Detta förstod jag inte riktigt och jag undrar om ni tycker att min lösning kan stämma trots att den är så annorlunda än Albikis? Jag ska ju tydligen addera och subtrahera 19 * 71 också för att bli klar, vilket jag inte gjort i min lösning. I kurslitteraturen har jag tolkat det som att man kan svara så som jag gjorde. Men har jag då täckt in ALLA positiva lösningar?

Du har täckt in alla positiva lösningar, men du kan göra mer för att ringa in bara dem. Om du väljer n så att y blir positivt och ser vad x blir då så har du en positiv lösning där. Sedan kan du ta reda på vilket det största n är så att x fortfarande är positivt. Det är inte många alls, så du kan räkna upp de positiva lösnngarna.

Lisa Mårtensson 307
Postad: 13 feb 2019

Jag ska försöka göra detta såsnart jag har tid. Tack!

Lisa Mårtensson 307
Postad: 13 feb 2019

Om n=843 så blir y positivt, y blir då 17.

Om n= 843 så blir x= 147

Lösning  1 blir då x=147, y=17 eller 

Övriga värden på n som gör att x blir positivt är n=844 och n= 845.

När n=844 så är x=76, y=36, vilket är lösning 2.

När n=845 så är x=5, y=36, vilket är lösning 3.

Har jag förstått rätt?

Laguna 3301
Postad: 14 feb 2019
Lisa Mårtensson skrev:

Om n=843 så blir y positivt, y blir då 17.

Om n= 843 så blir x= 147

Lösning  1 blir då x=147, y=17 eller 

Övriga värden på n som gör att x blir positivt är n=844 och n= 845.

När n=844 så är x=76, y=36, vilket är lösning 2.

När n=845 så är x=5, y=36, vilket är lösning 3.

Har jag förstått rätt?

Ja.

Lisa Mårtensson 307
Postad: 14 feb 2019

Så bra då!

Svara Avbryt
Close