Euklids metode er en effektiv metode for å beregne største felles faktor (sff) av to heltall. Metoden baserer seg på følgende observasjon. Hvis \(a\) og \(b\) er to heltall med \(a \geq b\), så vil største felles faktor til \(a\) og \(b\) også være største felles faktor til \(a\, \% \, b\) og \(b\). Med andre ord får vi: \[\text{sff}(a,\ b) = \text{sff}(a\,\%\,b,\ b) = c\,.\]

Vi kan legge merke til at dette gir oss en metode vi kan gjenta så mange ganger vi vi ønsker. Algoritmen produserer mindre og mindre tallpar. Til slutt vil den ene verdien i paret bli 0, og den andre verdien må dermed være største felles faktor til det opprinnelige paret \(a\) og \(b\). I Python kan vi lage et program som utfører denne algoritmen på følgende måte:

1
2
3
4
5

def EuklidsMetodeForFellesFaktorAv(a, b):
    while a != 0:
        a, b = max(a, b), min(a, b) # Definerer a til å være den største av a og b.
        a = a % b # Redefinerer a til å være resten etter divisjonen a / b. 
    return b

I tallteori ønsker vi ofte å studere likninger på formen, \[\tag 1 a\cdot x + b\cdot y = c\, ,\]
hvor \(a,\, b\) og \(c\) er heltall. Slike likninger kalles lineære diofantiske likninger, og det er heltallsløsninger vi er ute etter.

Dersom vi kan finne en heltallsløsning \((u, v) \) på den diofantiske likningen \begin{equation}\tag 2 b\cdot x + (a \, \% \, b)\cdot y = c\, ,\end{equation} så kan vi også løse likning (1). Det gjør vi ved å bruke at \[a \,\% \, b = a - (a \, // \, b)·b\,. %\quad \text{og} \quad \text{sff}(a, b) = c, \] Dermed kan vi manipulere likning (2) slik: \begin{align} b\cdot u + (a \, \% \, b)\cdot v = c \\
b\cdot u + (a - (a \, // \, b)·b)\cdot v = c \\
a\cdot v + b\cdot (u - (a \, // \, b) \cdot v) = c \end{align} Vi kan altså se at hvis \(x= u\) og \(y = v\) løser likning (2), så vil \(x = v\) og \(y = (u - (a \, // \, b) \cdot v)\) løse likning (1).

Legg merke til at vi kan gjenta denne prosessen så lenge vi ønsker. Helt spesielt så kan vi gjenta denne prosessen fra koeffisienter \( a,\) og \(b\) ned til koeffisientene \(c\) og \(0\). Den diofantiske likningen \(c·x + 0·y = c \) har triviell løsning \(x = 1\) og \(y = 0\). Å løse diofantiske likninger ved å reversere denne prosessen er det som kalles den utvidede Euklidske metode og kan enkelt implementeres i Python rekursivt, som vist under:

1
2
3
4
5
6
7
8
9

def LosningAvDiofantiskLikningMedKoeffisienter(a, b):
    if a < b:
        return LosningAvDiofantiskLikningMedKoeffisienter(b, a)
    if (b == 0):
        return a, 1, 0
    else:
        sff, x, y = LosningAvDiofantiskLikningMedKoeffisienter(b, a % b)
    x, y = y, (x - (a // b) * y)
    return sff, x, y

Under kan du se algotitmen i aksjon med to valgfrie verdier av \(a \text{ og }b \). Først bruker vi Euklids algoritme til å finne største felles faktor mellom tallene. Deretter reverseres prosessen slik at vi finner løsningen den diofantiske likningen \(ax + by = 1\).