Határozzuk meg a legnagyobb közös osztót euklideszi algoritmussal? f: 5x^3-3x^2+x-3 g: x^2-x

lnko(f,g) meghatározása:

f = q1 * g + r1

g = q2 * r1 + r2

r1 = q3 * r2 + r3

.

.

.

Egész addig osztogatsz így maradékosan, amíg nem kapsz 0-t maradékul (előbb utóbb kapni fogsz, ez tétel), és akkor az utolsó nem 0 maradék lesz lnko(f,g). Ezt a konkrét példát nézve:

(5x^3 - 3x^2 + x - 3) : (x^2 - x) = 5x + 2 = q1

5x^3 - 5x^2

---------------------

2x^2 + x - 3

2x^2 - 2x

---------------------

3x - 3 = r1

======================================

(x^2 - x) : (3x - 3) = (1/3)x = q2

x^2 - x

---------------------

0 = r2

Mivel itt r2 = 0, ezért r1 az utolsó nem 0 maradék, így lnko(f,g) = 3x - 3.