Diofantisk ekvation (Matematik/Universitet)

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.

Hej!

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

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

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

$1 = (15+71n)\cdot 19 + (-4-19n)\cdot 71$ .

Multiplicera detta med $4000$ för att få

$4000 = (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 + 284000n$ och $y = -16000-76000n$ , där $n$ betecknar ett godtyckligt heltal.

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.

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

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, $r_{1} = 14, r_{2} = 5, r_{3} = 4, r_{4} = 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 $(x_{0}, y_{0})$ , vilken är en partikulärlösning till ekvationen.

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

$\{\begin{cases} x = x_{0} - b n \\ y = y_{0} + a n \end{cases}$

där $n$ är ett godtyckligt heltal och $(x_{0}, y_{0})$ ä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 $\{\begin{cases} x = 60 000 - 71 n \\ y = - 16 000 + 19 n . \end{cases}$

Albiki skrev:
Notera att det finns oändligt många heltal som har denna egenskap; addera och subtrahera $n\cdot 19\cdot 71$ till denna identitet för att få
$1 = (15+71n)\cdot 19 + (-4-19n)\cdot 71$ .
Multiplicera detta med $4000$ för att få
$4000 = (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 + 284000n$ och $y = -16000-76000n$ , där $n$ 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?

Lisa Mårtensson skrev:
Albiki skrev:
Notera att det finns oändligt många heltal som har denna egenskap; addera och subtrahera $n\cdot 19\cdot 71$ till denna identitet för att få
$1 = (15+71n)\cdot 19 + (-4-19n)\cdot 71$ .
Multiplicera detta med $4000$ för att få
$4000 = (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 + 284000n$ och $y = -16000-76000n$ , där $n$ 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.

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

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?

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.

Så bra då!