Diofantisk likning
Moderatorer: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga
http://no.wikipedia.org/wiki/Diofantisk_ligningTerminator skrev:Hva er en diofantisk likning?
eksempel 1:
http://www.matematikk.net/ressurser/mat ... sk+likning
eksempel 2:
http://www.matematikk.net/ressurser/mat ... sk+likning
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.
[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
Marie Curie, kjemiker og fysiker.
[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
En lineær likning der løsningene (x,y) er i heltall.
[tex]ax + by = c[/tex]
der a,x,b,y,c alle er heltall.
Eksempel:
[tex]3x + 4y = 1[/tex]
Vi ser at x=-1, y = 4 er løsning.
Når man først har funnet en løsning vil det finnes uendelig mange løsninger. Du vil også kun ha løsninger hvis og bare hvis gcd(a,b)|c .. Dette forstår du kanskje ikke helt da du ikke er kjent med gcd, men det har jeg ikke tid til å forklare nærmere nå. Daofeishi er vel kanskje i slaget;)
[tex]ax + by = c[/tex]
der a,x,b,y,c alle er heltall.
Eksempel:
[tex]3x + 4y = 1[/tex]
Vi ser at x=-1, y = 4 er løsning.
Når man først har funnet en løsning vil det finnes uendelig mange løsninger. Du vil også kun ha løsninger hvis og bare hvis gcd(a,b)|c .. Dette forstår du kanskje ikke helt da du ikke er kjent med gcd, men det har jeg ikke tid til å forklare nærmere nå. Daofeishi er vel kanskje i slaget;)
En diofantisk likning er en hvilken som helst likning der variablene er heltallige. En av de viktigere diofantiske likningene er en lineære diofantiske likningen av første orden, som Magnus allerede har presentert:
[tex]ax + by = c[/tex]
Her er a, b og c konstanter, og x og y varibler. Det som er spennede her er at vi løser én likning i to variabler. Vi vet at dersom denne likningen skulle løses i alle heltall, hadde den på grunn av dette hatt uendelig mange løsninger. Vi kan vise at dersom vi kan finne én heltallig løsning til likningen, har den også uendelig mange heltallige løsninger.
Det første vi må vite, før vi kan løse en slik likning, er følgende teorem:
Enhver lineær kombinasjon av heltall er lik et multippel av største felles faktor til disse tallene.
Vi skal forklare dette, og introduserer derfor gcd-funksjonen. Den har fått navnet sitt fra engelsk "greatest common factor," og det hender du finner den på norsk som sff-funksjonen. gcd(a, b) forteller oss det største tallet som deler både a og b.
Siden gcd(a, b) er faktor av både a og b, kan vi skrive:
a = gcd(a,b)*m
b = gcd(a,b)*n
Nå kan du kanskje se at en hver lineær kombinasjon av a og b må inneholde gcd(a,b). En lineær kombinasjon av tallene er gitt ved ka + lb.
ka + lb = k*gcd(a,b)*m + l*gcd(a,b)*n = gcd(a,b)*(km+ln)
Vi kan nå se på et eksempel:
[tex]14x + 7y = 2[/tex]
gcd(14, 7) = 7. Vi har vist at dersom vi har en lineær kombinasjon av 14 og 7, må dette gi oss et multippel av gcd(14, 7) = 7. Siden 2 ikke er et multippel av 7, har heller ikke denne likningen en løsning.
Så la oss heller ta et annet eksempel:
[tex]14x + 7y = 21[/tex]
21 = 7*3, og er dermed et multippel av gcd(14, 7). Likningen har en løsning. Kan vi klare å finne den?`Veldig kjapp prøv-og-feil gir oss:
[tex]14(1) + 7(1) = 21[/tex]
Så x = 1 og y = 1. Men kan vi finne flere løsninger?
Se på dette:
x = (1 + t)
y = (1 - 2t)
Hva skjer hvis vi setter dette inn i likningen?
[tex]14(1+t) + 7(1-2t) = 21 - 0t = 21[/tex]
Og dermed har vi funnet uendelig mange løsninger!
x kan være 1, 2, 3, 4, 5 ..., og y vil da være 1, -1, -3, -5, -7...
Den kan vises at dersom en diofantisk likning
[tex]ax + by = c[/tex]
har løsningene x = m og y = n, er alle løsninger gitt ved:
[tex]x = m + \frac{b}{\gcd(a, b)} \qquad \qquad y = n - \frac{a}{\gcd(a, b)}[/tex]
(Prøv å vise dette selv!)
Når man så skal løse en lineær diofantisk likning av første grad, gjør man følgende:
- [tex]ax + by = c[/tex]
Forsikre deg om a c er et multippel av gcd(a,b). Vi antar at den er det, og skriver c som k*gcd(a,b)
- [tex]ax + by = k\gcd(a,b)[/tex]
Finn to tall m og n slik at løsningen slik at am + bn = \gcd(a,b). For å gjøre dette, bruker man en svært enkel algoritme, som bærer navnet "den euklidiske algorimen." La oss si du har funnet m og n slik at a(m) + b(n) = gcd(a, b). Da har vi at:
[tex]a(km) + b(kn) = k\gcd(a,b) = c[/tex]
- Da har du knekt nøtten! Alle løsninger er gitt ved
[tex]x = km + \frac{b}{\gcd(a, b)} \qquad \qquad y = kn - \frac{a}{\gcd(a, b)}[/tex]
Nå overlater jeg til Magnus å forklare den Euklidiske algoritmen
[tex]ax + by = c[/tex]
Her er a, b og c konstanter, og x og y varibler. Det som er spennede her er at vi løser én likning i to variabler. Vi vet at dersom denne likningen skulle løses i alle heltall, hadde den på grunn av dette hatt uendelig mange løsninger. Vi kan vise at dersom vi kan finne én heltallig løsning til likningen, har den også uendelig mange heltallige løsninger.
Det første vi må vite, før vi kan løse en slik likning, er følgende teorem:
Enhver lineær kombinasjon av heltall er lik et multippel av største felles faktor til disse tallene.
Vi skal forklare dette, og introduserer derfor gcd-funksjonen. Den har fått navnet sitt fra engelsk "greatest common factor," og det hender du finner den på norsk som sff-funksjonen. gcd(a, b) forteller oss det største tallet som deler både a og b.
Siden gcd(a, b) er faktor av både a og b, kan vi skrive:
a = gcd(a,b)*m
b = gcd(a,b)*n
Nå kan du kanskje se at en hver lineær kombinasjon av a og b må inneholde gcd(a,b). En lineær kombinasjon av tallene er gitt ved ka + lb.
ka + lb = k*gcd(a,b)*m + l*gcd(a,b)*n = gcd(a,b)*(km+ln)
Vi kan nå se på et eksempel:
[tex]14x + 7y = 2[/tex]
gcd(14, 7) = 7. Vi har vist at dersom vi har en lineær kombinasjon av 14 og 7, må dette gi oss et multippel av gcd(14, 7) = 7. Siden 2 ikke er et multippel av 7, har heller ikke denne likningen en løsning.
Så la oss heller ta et annet eksempel:
[tex]14x + 7y = 21[/tex]
21 = 7*3, og er dermed et multippel av gcd(14, 7). Likningen har en løsning. Kan vi klare å finne den?`Veldig kjapp prøv-og-feil gir oss:
[tex]14(1) + 7(1) = 21[/tex]
Så x = 1 og y = 1. Men kan vi finne flere løsninger?
Se på dette:
x = (1 + t)
y = (1 - 2t)
Hva skjer hvis vi setter dette inn i likningen?
[tex]14(1+t) + 7(1-2t) = 21 - 0t = 21[/tex]
Og dermed har vi funnet uendelig mange løsninger!
x kan være 1, 2, 3, 4, 5 ..., og y vil da være 1, -1, -3, -5, -7...
Den kan vises at dersom en diofantisk likning
[tex]ax + by = c[/tex]
har løsningene x = m og y = n, er alle løsninger gitt ved:
[tex]x = m + \frac{b}{\gcd(a, b)} \qquad \qquad y = n - \frac{a}{\gcd(a, b)}[/tex]
(Prøv å vise dette selv!)
Når man så skal løse en lineær diofantisk likning av første grad, gjør man følgende:
- [tex]ax + by = c[/tex]
Forsikre deg om a c er et multippel av gcd(a,b). Vi antar at den er det, og skriver c som k*gcd(a,b)
- [tex]ax + by = k\gcd(a,b)[/tex]
Finn to tall m og n slik at løsningen slik at am + bn = \gcd(a,b). For å gjøre dette, bruker man en svært enkel algoritme, som bærer navnet "den euklidiske algorimen." La oss si du har funnet m og n slik at a(m) + b(n) = gcd(a, b). Da har vi at:
[tex]a(km) + b(kn) = k\gcd(a,b) = c[/tex]
- Da har du knekt nøtten! Alle løsninger er gitt ved
[tex]x = km + \frac{b}{\gcd(a, b)} \qquad \qquad y = kn - \frac{a}{\gcd(a, b)}[/tex]
Nå overlater jeg til Magnus å forklare den Euklidiske algoritmen
Godt forklart Daofeishi. Når det kommer til den euklidiske algoritme anbefaler jeg strengt tatt bare å ta et søk på google; "Euclidean algorithm", evt "extended euclidean algorithm".
Vi ser at disse oppgavene kan løses "slavisk" med bruk av enkle algoritmer. Når det kommer til ikke-lineære blir det fort mer problematisk. Én type det dog finnes løsningsmetode for er typiske "Pell equations". Dette er likninger på formen [tex]u^2 - dv^2 = 1[/tex] der d ikke er et perfekt kvadrat(altså, kvadrat av heltall), og u,v er heltall. Oppgaven går da ut på å bestemme u og v når d er gitt. For å få til dette må man gå via såkalte kjedebrøker, en måte å representere f.eks irrasjonelle talls repeterende siffer. Igjen sikter jeg til google ta dette er veldig slavisk å fram til.
Vi ser at disse oppgavene kan løses "slavisk" med bruk av enkle algoritmer. Når det kommer til ikke-lineære blir det fort mer problematisk. Én type det dog finnes løsningsmetode for er typiske "Pell equations". Dette er likninger på formen [tex]u^2 - dv^2 = 1[/tex] der d ikke er et perfekt kvadrat(altså, kvadrat av heltall), og u,v er heltall. Oppgaven går da ut på å bestemme u og v når d er gitt. For å få til dette må man gå via såkalte kjedebrøker, en måte å representere f.eks irrasjonelle talls repeterende siffer. Igjen sikter jeg til google ta dette er veldig slavisk å fram til.