Diofantiske likninger

Likninger hvor koeffisientene er heltallige og løsningen skal være heltallig kalles diofantiske likninger.

Likningene deles inn i lineære likninger og diofantiske likninger av høyere grad.

Lineære likninger

Det kan vises at dersom løsningen til en diofantisk likning på formen

(1)   \begin{align*} ax+by=c \end{align*}

er

(2)   \begin{align*} x&=m & m&=s\frac{c}{sff(a,b)}\\ y&=n & n&=t\frac{c}{sff(a,b)} \end{align*}

er alle løsningene gitt ved

(3)   \begin{align*} x=m-\frac{b}{sff(a,b)}k\\ y=n+\frac{a}{sff(a,b)}k \end{align*}

Eksempel

Vi tar for oss et eksempel

(4)   \begin{align*} 5x+2y=49 \end{align*}

Vi trenger først å finne løsninger for x og y som hører sammen.

Vi sjekker om det største felles faktorer i de to koeffisientene 5 og 2 går opp i 49. Dersom største felles faktor ikke går opp i 49 har ikke likningen løsninger.

(5)   \begin{align*} gcd(5,2)=1\\ \end{align*}

viser at største felles faktor er 1. 1 går opp i 49, og likningen har løsning.

Vi bruker euklids utvidede algoritme og finner løsningene

Euklidalgo

Vi ser at vi får

(6)   \begin{align*} m&=1\\ n&=-2 \end{align*}

Dette betyr at

(7)   \begin{align*} 5\cdot m+2\cdot n=1 \end{align*}

Siden sff(5,2)|49 og gir at sff(5,2)\cdot 49=49

må vi

(8)   \begin{align*} x&=m\cdot 49=49\\ y&=n\cdot 49=-98\\ \end{align*}

og vi har funnet en løsning for x og y.

Da kan vi skrive opp.

(9)   \begin{align*} x&=49-\frac{2}{sff(5,2)}k=49-2k\\ y&=-98+\frac{5}{sff(5,2}k=98+5k \end{align*}

Nå kan vi finne flere løsninger for x og y.

k 26 25 24 23 22
x -3 -1 1 3 5
y 32 27 22 17 12

Vi kan oppgi løsningen slik (-3,32),(-1,27),(1,22),(3,17),(5,12)