Linjär diofantisk ekvation

Från Wikipedia
Hoppa till navigering Hoppa till sök

En linjär diofantisk ekvation är en diofantisk ekvation på formen a1x1 + a2x2 + .... + anxn = c där a1, a2, …, an är nollskilda heltalskonstanter, c är en heltalskonstant, och x1, x2, …, xn är variabler, "de obekanta". Som för alla diofantiska ekvationer söks endast heltalslösningar.

Den typ av diofantiska ekvationer som oftast tas upp i undervisningssammanhang är den linjära diofantiska ekvationen i två variabler, och det är därför främst denna typ som oftast avses när läroböcker använder termen diofantisk ekvation. Man kan då skriva variablerna som x och y lika gärna som x1 och x2, och på liknande sätt förenkla symbolerna för konstanterna. Ekvationen får då utseendet

, under det extra antagandet att x,y ∈ ℤ.

Det finns algoritmer för att lösa allmänna linjära diofantiska ekvationer, alltså för att avgöra om de alls har lösningar, och i förekommande fall hitta samtliga lösningar. Ekvationen har lösningar om och endast om den största gemensamma delaren (SGD) av alla koefficienterna a1, a2, …, an också är en delare till c.

En linjär diofantisk ekvation i en variabel, ax = c, saknar alltså lösningar om a inte delar c, men har en unik lösning om a delar c, nämligen x = c / a. Om en linjär diofantisk ekvation i flera variabler har någon lösning, så har den oändligt många lösningar. Dessa kan då framställas med hjälp av parametrar, som bara får anta heltalsvärden.

I vissa fall har man i det ursprungliga problemet ytterligare bivillkor på de obekanta, exempelvis att de inte får anta negativa värden. Man kan behandla sådana varianter genom att först lösa dem allmänt (utan bivillkor), och sedan undersöka vilka av lösningarna som uppfyller bivillkoren.

Att lösa en linjär diofantisk ekvation i två variabler[redigera | redigera wikitext]

Det viktigaste fallet är den allmänna linjära diofantiska ekvationen med två variabler,

eftersom metoden för att lösa denna kan användas rekursivt för att behandla fallen med fler variabler. Det viktigaste verktyget för lösningen av tvåvariabelfallet är Euklides algoritm för att bestämma SGD(a,b), den största gemensamma delaren av koefficienterna a och b, samt för att uttrycka SGD(a,b) som en linjärkombination av a och b. Detta kommer antingen att visa att ekvationen inte är lösbar, eller ge oss en lösning, en partikulärlösning. För att hitta alla lösningar kan man betrakta skillnaden mellan en godtycklig lösning och partikulärlösningen, och visa att den löser den motsvarande homogena ekvationen

Inledande exempel[redigera | redigera wikitext]

Följande exempel leder till mycket enkla räkningar, men illustrerar bland annat gången från partikulärlösningen till att hitta den allmänna lösningen. Betrakta ekvationen

Redan första steget i Euklides algoritm, alltså divisionen

ger här att SGD(25,4) = 1, och alltså att 1 = 25·1 + 4·(-6). Det betyder att (x,y) = (1,-6) är en lösning på en likartad ekvation, nämligen

En lösning på ekvation (2) ger dock ett för litet värde; högerledet i ekvation (1) är ju 3 gånger större. Om man tredubblar båda komposanterna i lösningen till (2) får man dock en lösning till (1). Med andra ord, om man sätter x0 = 3·1 = 3 och y0 = 3·(-6) = -18, så får man att mycket riktigt

det vill säga att (x,y) = (x0,y0) är en lösning på den ursprungliga ekvationen (1). Detta kallas en partikulärlösning.

Betraktar man nu en allmän lösning till ekvationen (1), så finner man att den också uppfyller att

Genom att "flytta om och byta tecken", samt bryta ut faktorer, kan man samla "x-delarna" i vänsterledet och "y-delarna" i högerledet, och får då likheten

Eftersom 25 och 4 är relativt prima, och på grund av aritmetikens fundamentalsats, måste primfaktorerna i 25 dela y0-y och primfaktorerna i 4 dela x-x0. Det betyder att vi kan skriva om (3) som

för något heltal n. Detta ger i sin tur att x-x0 = 4n och y0-y = 25n, det vill säga att den allmänna lösningen till ekvation (1) ges av

Här ger varje heltalsvärde på n en lösning. Med andra ord är n en heltalsparameter. Exempelvis ger n = 2 lösningen (x,y) = (11, -68), och n = -1 ger lösningen (x,y) = (-1, 7). Parametervärdet n = 0 ger tillbaka den ursprungliga partikulärlösningen.

Allmän lösningsgång[redigera | redigera wikitext]

Den allmänna linjära diofantiska ekvationen med två variabler

kan lösas i två steg, även om många läroböcker förordar en trestegslösning. Tvåstegslösningen ser ut så här:

Steg ett: Hitta en partikulärlösning medelst Euklides algoritm[redigera | redigera wikitext]

Genomför Euklides algoritm "framlänges och baklänges" för talen a och b, för att dels hitta SGD(a,b), som vi kan kalla d, och dels hitta två heltal u och v, sådana att

Undersök också om d delar c eller inte.

Om d inte delar c så saknar ekvation (i) lösningar. Annorlunda uttryckt är då lösningsmängden tom, vilket i sig är lösningen på problemet. Processen kan därför avbrytas, och man behöver aldrig gå vidare till steg 2. (Man behöver då inte heller genomföra Euklides algoritm baklänges för att hitta u och v som uppfyler (ii).)

Om däremot d delar c, så finns det ett heltal s sådant att ds = c. Sätter man nu x0 = su och y0 = sv, så ger (x,y) = (x0,y0) den sökta partikulärlösningen till den ursprungliga ekvationen (i).

Steg två: Hitta den allmänna lösningen medelst aritmetikens fundamentalsats[redigera | redigera wikitext]

Den allmänna lösningen till ekvationen (i) måste, precis som i det inledande exemplet, också uppfyller att

och alltså efter omflyttningar och utbrytningar också att

Aritmetikens fundamentalsats säger nu att vänsterledet och högerledet i (iii) har samma unika primfaktorisering. Det går dock inte att använda detta direkt på samma sätt som i det inledande exemplet, därför att a och b inte behöver vara relativt prima.

Emellertid är ju d en gemensam delare till a och b, så att det måste finnas heltal e och f, sådana att a = ed och b = fd. Man kan nu dividera båda leden i (iii) med d, och får en ny likhet

där e och f är relativt prima. Ur (iv) kan man på samma sätt som i exemplet härleda att den allmänna lösningen kan ges på parameterformen

Hitta en lösning, (x0, y0), till hjälpekvationen ax + by = 1, vilket man enklast gör genom att använda Euklides algoritm. Om, för att använda ett enkelt exempel, a = 25 och b = 4, ger Euklides algoritm att 25 = 6 × 4 + 1 vilket efter omskrivning blir 25 × (1) + 4 × (-6) = 1, alltså är en lösning till hjälpekvationen i detta fallet x0 = 1 och y0 = -6.

Trestegsmetoden[redigera | redigera wikitext]

Många läroböcker förordar en metod i tre steg, där med man börjar med en förberedande beräkning av SGD(a,b). Enligt den metoden genomför man därför först Euklides algoritm en gång, men då bara framlänges, till dess man har beräknat d = SGD(a,b). Därefter undersöker man om d delar c. I så fall delar man omedelbart ut d ur hela ekvation (i), och får på så sätt en ny ekvation

Denna löses sedan med hjälp av steg ett och steg två ovan, med den förenklingen att man i förväg vet att SGD(e,f) = 1, så att man inte kommer att behöva utföra de divisioner av a, b och c med d som man redan har utfört. Denna variant har vissa konceptuella fördelar, men också den stora nackdelen att man i allmänhet behöver utföra Euklides algoritm två gånger.

Ett räknemässigt mer komplicerat exempel[redigera | redigera wikitext]

Användningen av "den utvidgade Euklides algoritm" i steg ett ovan belyses bäst med hjälp av ett exempel. Anta att vi vill lösa den diofantiska ekvationen 679x + 245y = 91. Vi använder då Euklides algoritm för att finna SGD(679, 245)

Alltså är SGD(679, 245) = 7. Vi skall nu använda ovanstående resultat för att skriva SGD(679, 245) som en linjärkombination av 679 och 245.

Vidare är ju 91/7 = 13, så att vi får följande uttryck.

En partikulärlösning till vår diofantiska ekvation är således x0 = 169, y0 = -468, och vi kan som i det inledande exemplet gå vidare till att hitta den allmänna lösningen

Tre eller fler variabler[redigera | redigera wikitext]

I fallen med tre eller fler variabler har ekvationen utseendet a1x1 + a2x2 + .... + anxn = c med n ≥ 3. Den diofantiska ekvationen har endast lösningar om största gemensamma delaren för alla koefficienterna framför variablerna delar högerledet. För beräkningen av denna största gemensamma delare kan man tillämpa rekursion med avseende på antalet variabler. Detta ger:

där g = SGD(an-1an). Man kan nu även utnyttja detta för att återföra lösandet av den ursprungliga ekvationen på lösandet av linjära diofantiska ekvationer i n-1 eller 2 variabler.