Question

Use the Euclidean Algorithm to compute the greatest common divisors indicated. (a) gcd(20, 12) (b) gcd(100, 36) (c) gcd(207, 496)

Answer 1

Answer:

(a) $gcd(20, 12)=4$

(b) $gcd(100, 36)=4$

(c) $gcd(496,207 )=1$

Step-by-step explanation:

The Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, without explicitly factoring the two integers.

The Euclidean algorithm solves the problem:

                                  Given integers $a, b$, find $d=gcd(a,b)$

Here is an outline of the steps:

1. Let $a=x$, $b=y$.
2. Given $x, y$, use the division algorithm to write $x=yq+r$.
3. If $r=0$, stop and output $y$; this is the gcd of $a, b$.
4. If $r\neq 0$, replace $(x,y)$ by $(y,r)$. Go to step 2.

The division algorithm is an algorithm in which given 2 integers N and D, it computes their quotient Q and remainder R.

Let's say we have to divide N (dividend) by D (divisor). We will take the following steps:

Step 1: Subtract D from N repeatedly.

Step 2: The resulting number is known as the remainder R, and the number of times that D is subtracted is called the quotient Q.

(a) To find $gcd(20, 12)$ we apply the Euclidean algorithm:

$20 = 12\cdot 1 + 8\\ 12 = 8\cdot 1 + 4\\ 8 = 4\cdot 2 + 0$

The process stops since we reached 0, and we obtain $gcd(20, 12)=4$.

(b) To find $gcd(100, 36)$ we apply the Euclidean algorithm:

$100 = 36\cdot 2 + 28\\ 36 = 28\cdot1 + 8\\ 28 = 8\cdot 3 + 4\\ 8 = 4\cdot 2 + 0$

The process stops since we reached 0, and we obtain $gcd(100, 36)=4$.

(c) To find $gcd(496,207 )$ we apply the Euclidean algorithm:

$496 = 207\cdot 2 + 82\\ 207 = 82\cdot 2 + 43\\ 82 = 43\cdot 1 + 39\\ 43 = 39\cdot 1 + 4\\ 39 = 4\cdot 9 + 3\\ 4 = 3\cdot 1 + 1\\ 3 = 1\cdot 3 + 0$

The process stops since we reached 0, and we obtain $gcd(496,207 )=1$.