Question

Trace Algorithm 3 when it finds gcd (12,17) . That is, show all the steps used by Algorithm 3 to find gcd (12,17).

Short answer

The value of gcd(12,17) is 1.

Step-by-step solution

 Step 1: A Recursive Algorithm for Computing  

The gcd (a,b) can be reduced as gcd (a,b) = gcd (b mod ,a) and the condition gcd (0,b) when b > 0 .

Determine the value of  gcd (12,17)

Here, a = 12 and b = 17 .

The algorithm uses the else clause for finding that gcd (12,17) as follows.

$\begin{array}{r}\gcd (12,17)=\gcd (17mod12,12)\\ =\gcd (5,12)\end{array}$

This clause is used again for finding that gcd (5,12).

$\begin{array}{r}\gcd (5,12)=\gcd (12mod5,5)\\ =\gcd (2,5)\end{array}$

Then,

$\begin{array}{r}\gcd (2,5)=\gcd (5mod2,2)\\ =\gcd (1,2)\end{array}$

Then,

$\begin{array}{r}\mathrm{gca}(1,2)=\mathrm{gca}(2mod1,1)\\ =\gcd (0,1)\end{array}$

Lastly, for finding gcd (0,1) the algorithm uses the first step with a = 0 to find that gcd (0,1) = 1 . As a result, the algorithm finds that gcd (12,17) = 1 , which is the answer.

Therefore, the value of gcd (12,17) is 1.