Question

Solve for the Greatest Common Divisor (GCD) of the following pair of numbers using the Basic Euclidean Algorithm. (Show your complete solution.) 1. GCD (700, 105)

Answer 1

GCD(700, 105):
initial values: m = 700, n = 105

while n != 0 do  :      105 != 0
    r <- m mod n :      r <- 700 mod 105 = 70
    m <- n       :      m <- 105
    n <- r       :      n <- 70

while n != 0 do  :      70 != 0
    r <- m mod n :      r <- 105 mod 70 = 35
    m <- n       :      m <- 70
    n <- r       :      n <- 35

while n != 0 do  :      35 != 0
    r <- m mod n :      r <- 70 mod 35 = 0
    m <- n       :      m <- 35
    n <- r       :      n <- 0

while n != 0 do  :      0 == 0

return m         :      return 35