Answer :
Answer:
(a) [tex]gcd(20, 12)=4[/tex]
(b) [tex]gcd(100, 36)=4[/tex]
(c) [tex]gcd(496,207 )=1[/tex]
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 [tex]a, b[/tex], find [tex]d=gcd(a,b)[/tex]
Here is an outline of the steps:
- Let [tex]a=x[/tex], [tex]b=y[/tex].
- Given [tex]x, y[/tex], use the division algorithm to write [tex]x=yq+r[/tex].
- If [tex]r=0[/tex], stop and output [tex]y[/tex]; this is the gcd of [tex]a, b[/tex].
- If [tex]r\neq 0[/tex], replace [tex](x,y)[/tex] by [tex](y,r)[/tex]. 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 [tex]gcd(20, 12)[/tex] we apply the Euclidean algorithm:
[tex]20 = 12\cdot 1 + 8\\ 12 = 8\cdot 1 + 4\\ 8 = 4\cdot 2 + 0[/tex]
The process stops since we reached 0, and we obtain [tex]gcd(20, 12)=4[/tex].
(b) To find [tex]gcd(100, 36)[/tex] we apply the Euclidean algorithm:
[tex]100 = 36\cdot 2 + 28\\ 36 = 28\cdot1 + 8\\ 28 = 8\cdot 3 + 4\\ 8 = 4\cdot 2 + 0[/tex]
The process stops since we reached 0, and we obtain [tex]gcd(100, 36)=4[/tex].
(c) To find [tex]gcd(496,207 )[/tex] we apply the Euclidean algorithm:
[tex]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[/tex]
The process stops since we reached 0, and we obtain [tex]gcd(496,207 )=1[/tex].