Question

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

Short answer

The value of gcd (8,13) is 1.

Step-by-step solution

Define Recursive Algorithm for Computing  

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

 Step 2: Determine the value of  gcd (8,13)

Here, a = 8 and b = 13.

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

$\begin{array}{r}\gcd (8,13)=\gcd (13mod8,8)\\ =\gcd (5,8)\end{array}$

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

$\begin{array}{r}\gcd (5,8)=\gcd (8mod5,5)\\ =\gcd (3,5)\end{array}$

Then,

$\begin{array}{r}\gcd (3,5)=\gcd (5mod3,3)\\ =\gcd (2,3)\end{array}$

Then,

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

Now,

$\begin{array}{r}\gcd (1,2)=\gcd (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 (8,13) = 1 , which is the answer.

Therefore, the value of gcd (8,13) is 1.