Euklides algoritm och diofantiska ekvationer
=======================================

Euklides algoritm är ett sätt att finna största gemensamma delaren för två tal. Diofantiska 
ekvationer är ekvationer med heltalslösningar.

Euklides algoritm
-----------------------------

En division kan skrivas på följande sätt:

     dividend = kvot gånger divisor plus rest

Divisionen a/b kan alltså skrivas

      a = c x b + d

där 

    a   dividend    (täljare)
    b   divisor     (nämnare)
    c   kvot
    d   rest

Om a och b innehåller en gemensam faktor finns den även i d (om d inte är noll). Det gör att man kan 
fortsätta leta efter den genom att undersöka b och d. Man skriver då divisionen b/d som

     b = e x d + f

där 

    b  dividend
    d  divisor
    e   kvot
    f     rest

Och så fortsätter man tills resten blir noll. Det man då har som divisor är den största gensamma 
delaren i a och b.

Man får alltså

    a = c x b + d
    b = e x d + f
    d = g x f + h
    f = i x h + j

Och så fortsätter man tills resten blir noll.Divisorn i en rad blir alltså dividend i raden under och 
resten i en rad blir divisor i raden under. 

Diofantiska ekvationer
---------------------------------

En linjär diofantisk ekvation med två variabler är

      a X + b Y = c

där X och Y är heltalsvariabler och a, b och c är givna konstanter.

Om a och b har en gemensam faktor måste den finnas även i c. Annars har ekvationen ingen 
lösning. Om a och b enbart har fakton 1 gemensam finns den ju även i c och man kan då 
lösa ekvationen.

Finns det en gemensam faktor större än 1 i a, b och c börjar man med att dividera bort den.

Om a och b enbart har faktorn 1 gemensam löser man 

      a X + b Y = c

på följande sätt:

Lös först

      a X0 + b Y0 = 1

då blir

     X = c  X0 
     Y = c  Y0 

Om jag sätter  a X0  lika med minus b Y0 blir summan noll. Men 
a X0 skall vara 1 större än b Y0. Det betyder att om jag tar 
a X0 dividerat med b Y0 skall jag få resten 1.

Jag kan nu använda Euklides algoritm för att övertyga mig om att a och b bara har faktorn 1 
gemensam. Så kan jag gå baklänges genom algoritmen för att hitta två heltal som ligger 
intill varandra och som innehåller a respektive b. När jag går baklänges eliminerar jag i varje 
steg resten genom att använda att 

    a = c x b + d     kan skrivas  d = a - c x b
    b = e x d + f      kan skrivas  f = b - e x d       o s v

Exempel:

Lös ekvationen  

       77 X + 171 Y = 5

Euklides algoritm ger 

     171 = 2 x 77 + 17
      77 = 4 x 17 + 9
      17 = 1 x 9 + 8
       9 = 1x 8 +1
       8 = 8 x 1+ 0    Här är resten 0 och divisorn 1 vilket innebär att 1 är största gemensamma 
                       delare

Så går jag baklänges

        9 = 1 x 8 +1  ger  1 = 9 - 1 x8

eliminera 8  med hjälp av raden ovanför

        8 = 17 - 1 x 9     insättning ger   1 = 9 - 1 x (17 - 1 x9 ) = 2 x 9 -17

eliminera 9 med hjälp av raden ovanför

       9 = 77 - 4 x 17    insättning ger  1 = 2 x (77 - 4 x 17) - 17 = 2 x 77 - 9 x 17

eliminera 17 med hjälp av raden ovanför

      17 = 171 -2 x 77   insättning ger  1 = 2 x 77 - 9 ( 171 - 2 x 77) = 20 x 77 - 9 x 171

vilket ger 

     X0 = 20     som ger   X = 5 x 20 = 100
     Y0 = -9     som ger   Y = 5 x (-9) = - 45

Men det är inte den enda lösningen.

Om 

        a X + b Y = c

kan man skriva

       a(X + X1) + b (Y + Y1) = 1

       a X + b Y + a X1 + b Y1 = 1 + 0

Ekvationen gäller alltså även för alla värden på X1 och Y1 som
uppfyller kravet att 

       a  X1 + b Y1 = 0

Det ger

      X1 = n 171
      Y1 = - n 77

och den fullständiga lösningen blir

       X = 100 + n 171
       Y = - 45 - n 77

där n är ett heltal.


Till   http://www.lexsup.se