Question

Compute $\mathbf{GCD}\mathbf{(}\mathbf{210}\mathbf{,}\mathbf{588}\mathbf{)}$two different ways: by finding the factorization of each number, and by using Euclid’s algorithm.

Short answer

GCD of the numbers$210$ and $588$is calculated using Factorization method and Euclid’s Algorithm and the GCD is $42$.

Step-by-step solution

Explain GCD

Euclid algorithm is defined as a method to find GCD of two integers. General formula used is:

GCD (A, B) = GCD (B, A MOD N)

This step runs recursively till the remainder becomes zero.

Compute GCD by factorization method

$\begin{array}{l}\begin{array}{l}\mathrm{GCD}(210,588)\\ \begin{array}{l}\mathrm{Factor}\mathrm{of}210=2\times 3\times 5\times 7\\ \mathrm{Factor}\mathrm{of}588=2\times 2\times 3\times 7\times 7\end{array}\end{array}\\ \mathrm{Common}\mathrm{divisor}\mathrm{of}210\mathrm{and}588=2\times 3\times 7\\ \mathrm{GCD}(210,588)=42\end{array}$

Compute GCD by Euclid’s algorithm

$\begin{array}{l}\mathrm{GCD}(210,588)\\ \mathrm{Let}\mathrm{the}\mathrm{quotient}\mathrm{be}\mathrm{q}\mathrm{and}\mathrm{remainder}\mathrm{be}\mathrm{r}.\\ 588=210\times \mathrm{q}+\mathrm{r}\\ 588=210\times 2+168\\ 210=168\times 1+42\\ 168=42\times 4+0\\ \mathrm{GCD}\mathrm{equal}\mathrm{to}\mathrm{the}\mathrm{remainder}\mathrm{before}0\mathrm{i}.\mathrm{e}.42.\\ \mathrm{GCD}(210,588)\mathrm{by}\mathrm{Euclid}’\mathrm{s}\mathrm{method}=42\end{array}$

Hence, GCD of the given numbers is $42$.