Answer to Question #317995 in Algorithms for asdasd

Question

Solve for the Greatest Common Divisor (GCD) of the following pair of numbers using the Pseudocode of Euclidean Algorithm given

below. (Show your complete solution.)

while n ≠ 0 do

r ← m mod n

m ← n

n ← r

return m

1. GCD (248, 16)

Answer 1

GCD(248, 16):
initial values: m = 248, n = 16

while n != 0 do  :      16 != 0
    r <- m mod n :      r <- 248 mod 16 = 8
    m <- n       :      m <- 16
    n <- r       :      n <- 8

while n != 0 do  :      8 != 0
    r <- m mod n :      r <- 16 mod 8 = 0
    m <- n       :      m <- 8
    n <- r       :      n <- 0

while n != 0 do  :      0 == 0

return m         :      return 8