Math 455.1  •  22 March 2009

Methods of finding the gcd

Copyright © 2009 by Murray Eisenberg.  All rights reserved.

Problem

a = 144375; b = 21175;

Method 1: Use definition of gcd

Divisors[a]
Divisors[b]

Intersection[Divisors[a], Divisors[b]]

Max[%]

Method 2: Use prime power factorization

FactorInteger[a]
FactorInteger[b]

(5^2) (7^1) (11^1)

Method 3: Use the Euclidean Algorithm

The relations behind the Euclidean Algorithm are:

Apply the algorithm by using list of quotients, remainders

{q = Quotient[a, b] ,r0 = Mod[a,b]}

{q1 = Quotient[b, r0] ,r1 = Mod[b,r0]}

{q2 = Quotient[r0, r1] ,r2 = Mod[r0,r1]}

{q3 = Quotient[r1, r2] ,r3 = Mod[r1,r2]}

Apply the algorithm by reassigning a, b

r = Mod[a,b]

a = b; b = r; r = Mod[a, b]

a = b; b = r; r = Mod[a, b]

a = b; b = r; r = Mod[a, b]