Linjär diofantisk ekvation

En linjär diofantisk ekvation är en diofantisk ekvation på formen a₁x₁ + a₂x₂ + .... + a_nx_n = c där a₁, a₂, …, a_n är nollskilda heltalskonstanter, c är en heltalskonstant, och x₁, x₂, …, x_n ä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 x₁ och x₂, och på liknande sätt förenkla symbolerna för konstanterna. Ekvationen får då utseendet

${\displaystyle ax+by=c}$, 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 a₁, a₂, …, a_n 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

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

${\displaystyle ax+by=c}$

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

${\displaystyle (ii)\qquad ax+by=0}$

Inledande exempel

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

${\displaystyle (1)\qquad 25x+4y=3}$

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

${\displaystyle 25=6\cdot 4+1}$

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

${\displaystyle (2)\qquad 25x+4y=1}$

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 x₀ = 3·1 = 3 och y₀ = 3·(-6) = -18, så får man att mycket riktigt

${\displaystyle 25x_{0}+4y_{0}=3\cdot (25\cdot 1+4\cdot (-6))=3\cdot 1=3}$

det vill säga att (x,y) = (x₀,y₀) ä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

${\displaystyle 25x+4y=3=25x_{0}+4y_{0}}$

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

${\displaystyle (3)\qquad 25(x-x_{0})=4(y_{0}-y)}$

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

${\displaystyle (4)\qquad 25(x-x_{0})=25\cdot 4\cdot n=4\cdot 25\cdot n=4(y_{0}-y)}$

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

${\displaystyle (5)\qquad \left\{{\begin{matrix}x&=&3&+&4n\\y&=&-18&-&25n\end{matrix}}\right.\quad n\in \mathbf {Z} }$

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

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

${\displaystyle (i)\qquad ax+by=c}$

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

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

${\displaystyle (ii)\qquad au+bv=d}$

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 uppfyller (ii).)

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

Steg två: Hitta den allmänna lösningen medelst aritmetikens fundamentalsats

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

${\displaystyle ax+by=c=ax_{0}+by_{0}}$

och alltså efter omflyttningar och utbrytningar också att

${\displaystyle (iii)\qquad a(x-x_{0})=b(y_{0}-y)}$

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

${\displaystyle (iv)\qquad e(x-x_{0})=f(y_{0}-y)}$

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

${\displaystyle (v)\qquad \left\{{\begin{matrix}x&=&x_{0}&+&fn\\y&=&y_{0}&-&en\end{matrix}}\right.\quad n\in \mathbf {Z} \,.}$

Hitta en lösning, (x₀, y₀), 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 x₀ = 1 och y₀ = -6.

Trestegsmetoden

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

${\displaystyle (vi)\qquad ex+fy=s}$

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

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)

${\displaystyle 679=2\cdot 245+189}$

${\displaystyle 245=1\cdot 189+56}$

${\displaystyle 189=3\cdot 56+21}$

${\displaystyle 56=2\cdot 21+14}$

${\displaystyle 21=1\cdot 14+7}$

${\displaystyle 14=2\cdot 7+0}$

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.

${\displaystyle 7=21-14=21-(56-2\cdot 21)=3\cdot 21-56=3(189-3\cdot 56)-56=}$

${\displaystyle =3\cdot 189-10\cdot 56=3\cdot 189-10(245-189)=13\cdot 189-10\cdot 245=}$

${\displaystyle =13(679-2\cdot 245)-10\cdot 245=13\cdot 679-36\cdot 245}$

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

${\displaystyle 679\cdot 13+245\cdot (-36)=7\Leftrightarrow 679\cdot (13\cdot 13)+245\cdot (-36\cdot 13)=7\cdot 13=91}$

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

${\displaystyle \left\{{\begin{matrix}x&=&169&+&35n\\y&=&-468&-&97n\end{matrix}}\right.\quad n\in \mathbf {Z} \,.}$

Tre eller fler variabler

I fallen med tre eller fler variabler har ekvationen utseendet a₁x₁ + a₂x₂ + .... + a_nx_n = 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:

${\displaystyle \mathrm {SGD} (a_{1},...,a_{n})=\mathrm {SGD} (a_{1},...,a_{n-2},g)}$

där g = SGD(a_n-1, a_n). 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.