Euklids Algoritme

Forenklingstrinnet i sff-beregning

Dersom a\geq b \geq 0 og k er kvot(a,b), har vi
 

    \begin{align*}  sff(a,b)=sff(a-k\cdot b,b)  \end{align*}

Eksempel 1

sff(180, 60)

Kvotienten er kvot(180,60)=3

    \begin{align*} sff(180,60)&=sff(180-3\cdot 60,60)=sff(0,60)=60 \end{align*}

Eksempel 2

sff(183,43)

Kvotienten er kvot(183,43)=4

    \begin{align*} sff(183,43)&=sff(183-4\cdot 43,43)=sff(11,43) \end{align*}

Kvotienten kvot(43,11))=3

    \begin{align*} sff(183,43)&=sff(43-3\cdot 11,11)=sff(3,11)=1 \end{align*}

Euklids utvidede algoritme

En algoritme for å skrive sff(a,b) som en lineær kombinasjon av a og b

Skriv sff(154,82) som en lineær kombinasjon av 154 og 82

  • Vi skriver først opp de to tallene i synkende rekkefølge til venstre i kolonnene.
  • Detter setter vi 1 og 0 i raden med det største tallet , og 0 og 1 i raden med det minste.
  • Vi trekker så det minste fra det største. Antalle ganger skriver vi i kolonnen nest lengst til venstre.
154 \color{red}{1} \color{green}{0}
82 \color{blue}{1} {\color{orange}0} {\color{pink}1}
72 {\color{red}1}-{\color{blue}1}\cdot {\color{orange}0} =1 {\color{green}0}-{\color{blue}1}\cdot {\color{pink}1} =-1

Vi ser så på de tre nederste radene i den nye tabellen

82 1 \color{red}{0} \color{green}{1}
72 \color{blue}{1} {\color{orange}1} {\color{pink}-1}
10 {\color{red}0}-{\color{blue}1}\cdot {\color{orange}1} =-1 {\color{green}1}-{\color{blue}1}\cdot {\color{pink}-1} =2

Vi ser så på de tre nederste radene i den nye tabellen

72 1 \color{red}{1} \color{green}{-1}
10 \color{blue}{7} {\color{orange}-1} {\color{pink}2}
2 5 {\color{red}1}-{\color{blue}7}\cdot {\color{orange}-1} =8 {\color{green}-1}-{\color{blue}7}\cdot {\color{pink}2} =-15
0 ferdig

Vi ser hele tabellen

72
154 \color{red}{1} \color{green}{0}
82 \color{blue}{1} {\color{orange}0} {\color{pink}1}
\color{blue}{1} {\color{red}1}-{\color{blue}1}\cdot {\color{orange}0} =1 {\color{green}0}-{\color{blue}1}\cdot {\color{pink}1} =-1
10 \color{blue}{7} {\color{red}0}-{\color{blue}1}\cdot {\color{orange}1} =-1 {\color{green}1}-{\color{blue}1}\cdot {\color{pink}-1} =2
2 \color{blue}{5} {\color{red}1}-{\color{blue}7}\cdot {\color{orange}-1} =8 {\color{green}-1}-{\color{blue}7}\cdot {\color{pink}2} =-15
0 ferdig

Tall som en lineærkombinasjon

Spesiell løsning

På forrige side fant vi den spesiell løsningen til

    \begin{align*} sff(154,82)=8\cdot 154-15\cdot 82=2 \end{align*}

Den spesiell løsningen omfatter en bestemt løsning

Generell løsning

Generell løsning
Den generell løsningen omfatter mange løsninger. Har vi funnet koeffisienten for en lineærkombinasjon kan vi finne flere ved

    \begin{align*} c=\left(w-k\frac{b}{sff(a,b)}\right)a+\left(z+k\frac{a}{sff(a,b)}\right)b \end{align*}

der w og z er en spesiell løsning og k er et heltall

Når c=sff(a,b)

Den generell løsningen omfatter mange løsninger. Har vi funnet koeffisienten for en lineærkombinasjon kan vi finne flere ved

    \begin{align*} sff(a,b)=\left(w-k\frac{b}{sff(a,b)}\right)a+\left(z+k\frac{a}{sff(a,b)}\right)b \end{align*}

der w og z er en spesiell løsning og k er et heltall

Når sa+tb=1

    \begin{align*} 1=(w-kb)a+(z+ka)b \end{align*}

der w og z er en spesiell løsning og k er et heltall. \textbf{Det finnes ingen andre løsninger}