Matematikk

Lineær diofantisk ligning!

08. september 2017 av karolined1 (Slettet) - 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 2017 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

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