fant en ting til jeg ikke får til. diofantiske ligninger blir bare tull-selvom det ser rett frem ut i boka.
et eks: 3x+5y=19
så skal man dividere 5 på 3 ved å bruke euklid algoritmen. det gir 1 som svar og 2 i rest
blir 5-3x1=2
neste ledd blir-trodde jeg3delt på 2-som er rest. det gir 1 som svar og 1 i rest
blir 3-1x2=1
prøver så å sette inn det øverste utrrykket inn i 2 tallet i det nederste-og ikke gange det ut men samle det som det står i 3ms boka.
blir 3-1(5-3)= 2x3-1x5=1 og det blir helt på jordet. den videre utregningen med å gange det opp med 19 igjen, blir bare tull. er ikke euklid algoritmen at man deler først to tall, og så deler man på rest av det minste tallet av de to første etc???
kan gi noen gi tips om hva som er så feil?
diofantiske ligninger...
Moderators: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga
-
Fibonacci92
- Abel
- Posts: 665
- Joined: 27/01-2007 22:55
Jeg vet jeg ikke svarer på det du spør om, men kanskje har du godt av å se dette?
En måte å løse slike diofantiske likninger på er som følger:
Vi ser på likningen:
$ax+by = 1$,
Dersom du kan finne heltall $x_1$ og $y_1$ som oppfyller den likningen vil heltallene $cx_1$ og $cy_1$ oppfylle den generelle likningen:
$ax + by = c$
Rett og slett fordi hvis vi ganger alle ledd i en likning med det samme tallet vil likningen fortsatt gjelde.
I ditt tilfelle skal vi løse
$3x +5y = 19$
Da prøver vi først å løse
$3x + 5y = 1$
Da kan du bruke den euklidske algoritmen, eller du kan tenke slik: Hvilket tall i 5-gangen er bare 1 i fra et tall i 3-gangen? F.eks. $10 = 5*2$ og $9 = 3*3$.
Så da kan vi se at $x_1 = -3$ og $y_1 = 2$ er en heltallsløsning til likningen $3x +5y = 1$.
Da vet vi at $x_1 = -3*19 = -57$ og $y_1 = 2*19 = 38$ er løsninger av likningen $3x +5y = 19$.
Eller snarere:
$3*(-3) + 5*2 = 1 $
$\Rightarrow 3*(-3)*19 + 5*2*19 = 1*19 $
$\Rightarrow 3*(-57) + 5*38 = 19$
Da har vi funnet en mulig heltallsløsning.
For å svare på ditt siste spørsmål. I den euklidske algoritmen stopper vi når vi får rest 1.
Så det eneste steget er $7 = 1*6 +1$.
Dersom du tenker over hva du faktisk driver med, og hva målet ditt er, så bruker du den euklidske algoritmen til å løse likningen
$6x+7y = 1$
Her burde man, hvis man faktisk prøver å tenke og ikke bare følger en metode slavisk, se at $x_1 = -1$ og $y_1 = 1$ er en løsning.
Da er $x_1 = -38$ og $y_1 = 38$ en løsning av den opprinnelige likningen
$6x+7y = 38$
En måte å løse slike diofantiske likninger på er som følger:
Vi ser på likningen:
$ax+by = 1$,
Dersom du kan finne heltall $x_1$ og $y_1$ som oppfyller den likningen vil heltallene $cx_1$ og $cy_1$ oppfylle den generelle likningen:
$ax + by = c$
Rett og slett fordi hvis vi ganger alle ledd i en likning med det samme tallet vil likningen fortsatt gjelde.
I ditt tilfelle skal vi løse
$3x +5y = 19$
Da prøver vi først å løse
$3x + 5y = 1$
Da kan du bruke den euklidske algoritmen, eller du kan tenke slik: Hvilket tall i 5-gangen er bare 1 i fra et tall i 3-gangen? F.eks. $10 = 5*2$ og $9 = 3*3$.
Så da kan vi se at $x_1 = -3$ og $y_1 = 2$ er en heltallsløsning til likningen $3x +5y = 1$.
Da vet vi at $x_1 = -3*19 = -57$ og $y_1 = 2*19 = 38$ er løsninger av likningen $3x +5y = 19$.
Eller snarere:
$3*(-3) + 5*2 = 1 $
$\Rightarrow 3*(-3)*19 + 5*2*19 = 1*19 $
$\Rightarrow 3*(-57) + 5*38 = 19$
Da har vi funnet en mulig heltallsløsning.
For å svare på ditt siste spørsmål. I den euklidske algoritmen stopper vi når vi får rest 1.
Så det eneste steget er $7 = 1*6 +1$.
Dersom du tenker over hva du faktisk driver med, og hva målet ditt er, så bruker du den euklidske algoritmen til å løse likningen
$6x+7y = 1$
Her burde man, hvis man faktisk prøver å tenke og ikke bare følger en metode slavisk, se at $x_1 = -1$ og $y_1 = 1$ er en løsning.
Da er $x_1 = -38$ og $y_1 = 38$ en løsning av den opprinnelige likningen
$6x+7y = 38$
-
Guest
Jækla pikk.staalel wrote:hvorfor heller ikke svare på det jeg spør om? ok, fant ut av det-man må stanse den euklidske algoritmen når den er 1.
men-mye enklere å se en løsning ved et svar som handler akkurat om problemet man spør om.
staalel wrote:hvorfor heller ikke svare på det jeg spør om? ok, fant ut av det-man må stanse den euklidske algoritmen når den er 1.
men-mye enklere å se en løsning ved et svar som handler akkurat om problemet man spør om.
Dette begynner å bli på kanten, staalel. Fibonacci92 oppga full utregning med endelig svar. Han utdypte også om hvordan man løser diofantiske likninger generelt som prikken over i'en. Er det ikke bra nok?Fibonacci92 wrote: Da vet vi at $x_1 = -3*19 = -57$ og $y_1 = 2*19 = 38$ er løsninger av likningen $3x +5y = 19$.
prøver en siste.
2850x+3750y=61200
dividerer med 30
95x+125y=2040
gir med euklid alg. x=4 og y=-3 og rest på 5. 61200 delt på 5 blir 12240. ganger det med 4 og trekker fra 3750/5xn for å finne positive tall for x og y.
x=4x12240-750n, n=avrundet til 65
setter inn: 48960-750x65= 210
som er galt. noen som kan vise hvor det er galt?
2850x+3750y=61200
dividerer med 30
95x+125y=2040
gir med euklid alg. x=4 og y=-3 og rest på 5. 61200 delt på 5 blir 12240. ganger det med 4 og trekker fra 3750/5xn for å finne positive tall for x og y.
x=4x12240-750n, n=avrundet til 65
setter inn: 48960-750x65= 210
som er galt. noen som kan vise hvor det er galt?
-
Fibonacci92
- Abel
- Posts: 665
- Joined: 27/01-2007 22:55
Noen spørsmål:
Hvorfor deler du på 30 og ikke 150? Det skal være ganske greit å se at den likningen du ender opp med kan videre forkortes med i alle fall en faktor 5.
Hva mener du med: trekker fra 3750/5xn og hvorfor ganger du med 4?
Edit: endret fra 90 til 150
Hvorfor deler du på 30 og ikke 150? Det skal være ganske greit å se at den likningen du ender opp med kan videre forkortes med i alle fall en faktor 5.
Hva mener du med: trekker fra 3750/5xn og hvorfor ganger du med 4?
Edit: endret fra 90 til 150
Last edited by Fibonacci92 on 04/07-2015 01:29, edited 1 time in total.
fordi: 95x+125y=2040 og 125:95=1, rest 30, og 95:30=3 og rest er 5
125-95x1=30
95-30x3=5 satt inn øverste i nederste:
95-(125-95)3=5 blir 4x95-3x125=5, x=4 og y=-3.
ganger med 12240 for å få 5 til å bli 61200-opprinnelige verdi og ganger x og y med det og.
48960x125-36720x125=61200
for å finne positiv verdi for y, bruker de en metode. lar n være et helt tall og:
x=48960-3750/5xn blir 48960=750n, n=65,28 som avrundes til 65 fordi det skal være et helt tall.
satt inn x=48960-750x65=210, x=210
y=-36720+ 2850/5x65=-36720+37050=330, y=330
det stemmer ikke. men hvis deler på 30, blir x=7 og y=11, og det stemmer. hvorfor? den metoden skal liksom gi rett svar, uten å måtte dele på noe.
125-95x1=30
95-30x3=5 satt inn øverste i nederste:
95-(125-95)3=5 blir 4x95-3x125=5, x=4 og y=-3.
ganger med 12240 for å få 5 til å bli 61200-opprinnelige verdi og ganger x og y med det og.
48960x125-36720x125=61200
for å finne positiv verdi for y, bruker de en metode. lar n være et helt tall og:
x=48960-3750/5xn blir 48960=750n, n=65,28 som avrundes til 65 fordi det skal være et helt tall.
satt inn x=48960-750x65=210, x=210
y=-36720+ 2850/5x65=-36720+37050=330, y=330
det stemmer ikke. men hvis deler på 30, blir x=7 og y=11, og det stemmer. hvorfor? den metoden skal liksom gi rett svar, uten å måtte dele på noe.
-
Fibonacci92
- Abel
- Posts: 665
- Joined: 27/01-2007 22:55
Her slår det meg at du blander en del.
$x=48960, y = -36720$ er en løsning av likningen
$95x + 125y =61200$
Men var det denne du forsøkte å løse?
Og når vi ser på dette:
$48960-3750/5 \cdot n = 0$ så bruker du $48960$ fra din løsning av likningen $95x + 125y =61200$
og
$3750$ fra likningen $2850x+3750y=61200$.
Hva er sammenhengen?
$x=48960, y = -36720$ er en løsning av likningen
$95x + 125y =61200$
Men var det denne du forsøkte å løse?
Og når vi ser på dette:
$48960-3750/5 \cdot n = 0$ så bruker du $48960$ fra din løsning av likningen $95x + 125y =61200$
og
$3750$ fra likningen $2850x+3750y=61200$.
Hva er sammenhengen?
-
Fibonacci92
- Abel
- Posts: 665
- Joined: 27/01-2007 22:55
La oss se, dette blir unødvendig komplisert, men jeg svarer ut i fra det du har klart selv så langt.
Du løser likningen
$2850x+3750y=61200$
Du har funnet at $x_1 = 4 , y_1 = -3$ er en løsning av likningen $95x + 125y = 5$ ved å bruke den euklidske algoritmen.
Da er de samme verdiene en løsning av likningen hvor vi ganger alle ledd med $30$:
$2850x_1 + 3750y_1 = 150.$
For å omforme dette til tallene du begynte med ønsker vi å skalere høyresiden opp til $61200$
Vi må da gange med: $61200/150 = 408.$
Så da får vi at
$2850x_1 \cdot 408+3750y_1 \cdot 408 =150*408$
altså
$2850 \cdot x_2 + 3750 \cdot y_2 = 61200$,
hvor
$x_2 = 408 \cdot x_1 = 408 \cdot 4 = 1632$
$y_2 = 408 \cdot y_1 = 408 \cdot (-3) = -1224$
så nå som vi har riktige tall:
Vi har også at vi kan få nye løsninger ved å legge til og trekke fra
$2850 \cdot 3750 / 150 \cdot n$ slik som dette:
$2850 \cdot x_2 - 2850 \cdot 3750 / 150 \cdot n + 3750 \cdot y_2 +2850 \cdot 3750 / 150 \cdot n = 61200$,
som er det samme som
$2850 \cdot (x_2 - 3750 / 150 \cdot n) + 3750 \cdot (y_2 + 2850 /150 \cdot n) = 61200$,
Vi ser at ved å velge vilkårlige verdier av n, så får vi nye løsninger av likningen.
Da kan vi kanskje velge n slik at vi tvinger både $x_2 - 3750 / 150 \cdot n$ og $y_2 +2850 /150 \cdot n$ til å være positive.
Da prøver vi å gjøre $x_2 - 3750 / 150 \cdot n$ så liten som mulig, men fortsatt positiv. Ser du hvorfor det vil fungere?
Da trenger vi løse ulikheten $x_2 - 3750 / 150 \cdot n > 0$,
which is $ 1632 - 3750 / 150 \cdot n > 0$ som gir $n = 65.28$, så vi velger $ n = 65$,
da får vi verdiene $x_3 = 1632 - 3750 / 150 \cdot 65 = 7$ og $y_3 = -1224+2850 /150 \cdot 65 = 11 $
Du løser likningen
$2850x+3750y=61200$
Du har funnet at $x_1 = 4 , y_1 = -3$ er en løsning av likningen $95x + 125y = 5$ ved å bruke den euklidske algoritmen.
Da er de samme verdiene en løsning av likningen hvor vi ganger alle ledd med $30$:
$2850x_1 + 3750y_1 = 150.$
For å omforme dette til tallene du begynte med ønsker vi å skalere høyresiden opp til $61200$
Vi må da gange med: $61200/150 = 408.$
Så da får vi at
$2850x_1 \cdot 408+3750y_1 \cdot 408 =150*408$
altså
$2850 \cdot x_2 + 3750 \cdot y_2 = 61200$,
hvor
$x_2 = 408 \cdot x_1 = 408 \cdot 4 = 1632$
$y_2 = 408 \cdot y_1 = 408 \cdot (-3) = -1224$
så nå som vi har riktige tall:
Vi har også at vi kan få nye løsninger ved å legge til og trekke fra
$2850 \cdot 3750 / 150 \cdot n$ slik som dette:
$2850 \cdot x_2 - 2850 \cdot 3750 / 150 \cdot n + 3750 \cdot y_2 +2850 \cdot 3750 / 150 \cdot n = 61200$,
som er det samme som
$2850 \cdot (x_2 - 3750 / 150 \cdot n) + 3750 \cdot (y_2 + 2850 /150 \cdot n) = 61200$,
Vi ser at ved å velge vilkårlige verdier av n, så får vi nye løsninger av likningen.
Da kan vi kanskje velge n slik at vi tvinger både $x_2 - 3750 / 150 \cdot n$ og $y_2 +2850 /150 \cdot n$ til å være positive.
Da prøver vi å gjøre $x_2 - 3750 / 150 \cdot n$ så liten som mulig, men fortsatt positiv. Ser du hvorfor det vil fungere?
Da trenger vi løse ulikheten $x_2 - 3750 / 150 \cdot n > 0$,
which is $ 1632 - 3750 / 150 \cdot n > 0$ som gir $n = 65.28$, så vi velger $ n = 65$,
da får vi verdiene $x_3 = 1632 - 3750 / 150 \cdot 65 = 7$ og $y_3 = -1224+2850 /150 \cdot 65 = 11 $