Answer to Question #317984 in Algorithms for asdasd

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