Największy Wspólny Dzielnik NWD – dowód poprawności Algorytmu Euklidesa

Największy wspólny dzielnik liczb naturalnych a, b oznaczamy przez NWD(a,b).
Własności (bardzo łatwe do udowodnienia):
Lemat
1. NWD(a,a)=a
2. NWD(a,b)=NWD(a – b,b) jeśli a > b
3. NWD(a,b)=NWD(a,b – a) jeśli a < b

Dowód (tylko wariantu 2).
Niech a > b oraz niech

(

)

,

K

K

K

NWD a b

a

a

K

b

b

K

=

⇒ =

⋅

∧ =

⋅

, gdzie

,

0

K

K

a

b > ,

K

K

a

b

>

, przy czym

0

K > jest

największą liczbą o tej własności oraz niech

(*)

(

)

,

L

L

L

NWD a b b

a b

c

L

b

b

L

=

−

⇒ − =

⋅ ∧ =

⋅

, gdzie

,

0

L

L

c b > , przy czym

0

L > jest

największą liczbą o tej własności.

(**)

Z (*) wynika, że

(

)

K

K

a b

a

b

K

− =

−

⋅

stąd K dzieli a – b (oraz oczywiście K dzieli b).

A zatem na pewno

K

L

≤ na mocy (**).

Z (**) wynika, że

(

)

L

L

a

a b b

c

b

L

= − + =

+

⋅

stąd

L dzieli a (oraz oczywiście L dzieli b).

A zatem na pewno

L

K

≤

na mocy (*).

Stąd

K

L

= .

CND.

Algorytm Euklidesa

start

naturalne

a, b, nwd, A, B ;

czytaj

a ;

czytaj

b ;

A = a ;
B = b ;
dopóty dopóki

a

b

≠ wykonuj

jeśli

a

b

> to a a b

= − ;

w przeciwnym przypadku

b

b a

= − ;

nwd = a ;
wyświetl

A ;

wyświetl

B ;

wyświetl

nwd ;

koniec

Rozpatrzmy funkcję zdaniową

(

)

,

P a b

zdefiniowaną następująco:

(

)

(

)

(

)

,

0

0

,

,

P a b

a

b

NWD a b

NWD A B

=

> ∧ > ∧

=









gdzie a, b, A, B są identyfikatorami zmiennych zdefiniowanych w

Algorytmie Euklidesa

Dowód poprawności algorytmu sprowadza się do stwierdzenia, że funkcja zadaniowa

(

)

,

P a b

jest prawdziwa w każdym kroku algorytmu oraz, że liczba kroków algorytmu

jest liczbą skończoną.

Dowód (por. np. Turski W.M., Propedeutyka Informatyki, PWN).
Bezpośrednio przed rozpoczęciem iteracji funkcja

(

)

,

P a b

jest oczywiście prawdziwa pod

warunkiem, że wczytamy liczby naturalne a i b.
Iteracja jest wykonywana pod warunkiem, że a

b

≠ , czyli mamy albo przypadek a b

> albo

przypadek a

b

< .

Jeśli a

b

> , to działanie wykonywane w obrębie iterowanej instrukcji nie zmieni b, natomiast

a pozostanie dodatnie. Ponadto będzie prawdziwa relacja

(

)

(

)

,

,

NWD a b

NWD A B

=

na mocy

Lematu (wariant 2). A zatem wartość logiczna funkcji

(

)

,

P a b

będzie prawdą.

Podobne rozumowanie przeprowadzamy dla przypadku a

b

< .

Iteracja może zakończyć się tylko w przypadku kiedy a

b

= , przy czym zawsze będzie

spełniony warunek

0

0

a

b

> ∧ > . A zatem funkcja

(

)

,

P a b

także i w tym szczególnym

przypadku będzie miała wartość logiczną prawda (mówimy wtedy, że funkcja

(

)

,

P a b

jest

niezmiennikiem iteracji). Instrukcje, które następują po instrukcji pętli nie mają już wpływu
na wartość logiczną funkcji

(

)

,

P a b

.

Zauważmy

ponadto,

że

jeśli

a

b

= , to na mocy Lematu (wariant 1)

( , )

( , )

NWD a b

NWD a a

a

=

= i skoro funkcja

(

)

,

P a b

jest prawdziwa w każdym kroku

algorytmu (jak to zostało wykazane wyżej), więc

( , )

NWD A B

a

nwd

= =

(po podstawieniu a

do nwd ).
Pozostaje jeszcze do udowodnienia, że iteracja musi się zakończyć, ale zauważmy, że wobec
zmniejszania liczby dodatniej o liczbę dodatnią w taki sposób, że wynik zawsze pozostaje
dodatni, nie jest zatem możliwe (wobec założonej skończoności wczytywanych liczb a i b)
aby instrukcje te mogły być powtarzane nieskończoną liczbę razy.
CND.