Akkurat nå er 250 pålogget.

Matematikk

Lineær diofantisk ligning!

08. september kl. 18:41 av karolined1 - Nivå: Universitet

Hei! Er det noen som kan hjelpe meg å løse denne diofantiske ligninga ved bruk av euklids algoritme. 
Skjønner ikke helt hvordan man går bakover igjen etter at man har funnet SFF(a,b) 

33x+14y=115 

Takk for svar! 


Brukbart svar (0)

Svar #1
08. september kl. 19:38 av Sigurd

Vi vet at den diofantiske likningen har en løsning hvis (og bare hvis) gcd(33,14) er en divisor av 115.
Fremgangsmåten blir da
(1) Bruk Euklids algoritme til å sjekke om likningen er løsbar
(2) Bruk algoritmen til å finne en løsning

Okei, vi prøver altså å finne gcd(33,14)

Vi bruker heltallsdivisjon og deler 33 på 14. 14 går to hele ganger opp i 33, og så har vi 5 i rest.

33 = 2 \cdot \underline{14} + \underline{5}

De to understrekede tallene går med til neste steg. Vi heltallsdividerer 14 på 5. 5 går 2 hele ganger opp i 14, og vi har 4 i rest.

14 = 2 \cdot \underline{5} + \underline{4}

Gjenta igjen. 4 går 1 hel gang opp i 5, og vi har 1 i rest.

5 = 1 \cdot \underline{4} + \underline{1}

Og til sist går 1 fire hele ganger opp i 4, med null i rest.

4 = 4 \cdot \underline{1} + \underline{0}

Nå fikk vi en nullrest. Vi ser da på den siste resten som ikke var null. Dette er største felles divisor. Altså

gcd(33,14) = 1

Siden 1 er en divisor av 115, har likningen en løsning.

Målet vårt videre er å skrive gcd(33,14) som en lineærkombinasjon av 33 og 14 (dvs på formen 33u + 14v). Det kan vi gjøre ved å benytte leddene i euklids algoritme på en smart måte. Vi skriver ut leddene, på formen
d = nk + r, uttrykt ved resten, r = d - nk, og setter inn i største felles divisor, og jobber oss videre oppover helt til vi har uttrykt største felles divisor med 33 og 14.

Nest siste linje i euklids algoritme ga 5 = 4*1 + 1
Vi kan løse denne for resten, 1 = 5 - 4*1. Men siden gcd(33,14) = 1, kan vi altså skrive

\gcd(33,14) = 1 = 5-4\cdot1

Men la oss bruke resten i linjen over på samme måte. 14 = 2*5 + 4 gir oss 4 = 14 - 2*4

\newline \gcd(33,14) = 1 = 5-4\cdot1 \newline .\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 5 -(14-2\cdot5)\cdot 1 \newline .\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 5 -14+2\cdot5 \newline .\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = (1+2)\cdot5 -14 \newline .\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 3\cdot5 -14
 

Videre kan vi bruke den første linjen til å finne et uttrykk for 5-tallet: 33 = 2*14 + 5.
5 = 33 - 2*14. Innsatt i likningen får vi da

\newline \gcd(33,14) = 1 = 5-4\cdot1 \newline .\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 5 -(14-2\cdot5)\cdot 1 \newline .\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 5 -14+2\cdot5 \newline .\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = (1+2)\cdot5 -14 \newline .\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 3\cdot5 -14 \newline .\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 3\cdot(33-2\cdot 14) -14 \newline .\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 3\cdot33-6\cdot 14 -14 \newline .\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ = 3\cdot 33-7\cdot 14

Det som er viktig, er at du aldri "regner bort" resten i linjen over i euklids algoritme, men bruker dette tallet til å sette inn linjen over, og dermed til slutt stå igjen med en lineær kombinasjon av de to opprinnelige tallene (33 og 14)

Nå har vi altså funnet ut at
1 = 3 \cdot 33 - 7 \cdot 14

Men vi kan multiplisere denne likningen med 115:
115 = (3\cdot 115) \cdot 33 - (7\cdot115) \cdot 14
Eller
115 = (345) \cdot 33 - (805) \cdot 14

Nå kan vi lese ut x og y:
\newline x = 345 \newline y = 805

Dette er én løsning av likningen. Et teorem gir oss at alle løsninger kan skrives på formen:

\newline x = 345 + \frac{33}{\gcd(33,14)}\cdot t = 345 + 33t \newline y = 805 + \frac{14}{\gcd(33,14)}\cdot t = 805+14t

der t er et heltall.


Brukbart svar (0)

Svar #2
09. september kl. 08:53 av Jørrian

Mye jobb slike oppgaver, bruk lenkene til å sjekke dine svar:

http://www.alcula.com/calculators/math/gcd/

https://www.math.uwaterloo.ca/~snburris/htdocs/linear.html

Og sjekk om løsningen din fungerer, feks for t=0 og t = 1

Se ser du men en gang at du har glemt - tegnet i løsningen din :-)


Brukbart svar (0)

Svar #3
09. september kl. 09:36 av Sigurd

Ugg. Bra du korrigerer meg – og kjempesmart side for å sjekke seg!
Jeg var litt rask på avtrekkeren til slutt der, ser jeg. Løsningen skal selvsagt være

\newline x_0 =345 \newline y_0 = -805

Den andre brøleren jeg gjorde, var at den generelle løsningen skal være på formen

\newline x = x_0 + \frac{b}{\gcd(a,b)}\cdot t \newline y = y_0 - \frac{a}{\gcd(a,b)}\cdot t,

dvs. jeg byttet om a og b, og glemte enda et minustegn.

Dermed får vi altså, denne gangen sjekket med datamaskinen:

\newline x = 345 + 14 t \newline y = -805 - 33 t


Skriv et svar til: Lineær diofantisk ligning!

Du må være pålogget for å skrive et svar til dette spørsmålet. Klikk her for å logge inn.
Har du ikke en bruker på Skolediskusjon.no? Klikk her for å registrere deg.