Question

Find g.c.d of (i) 135 and 225 (ii) 38220 and 196 by Euclid’s algorithm.

Answer 1

Hint: To calculate gcd of two numbers using Euclid’s algorithm, the larger number is divided by the smaller number and the larger is number is expressed in terms of the small number, that is, \[\text{dividend}=\text{divisor}\times \text{quotient}+\text{remainder}\]. If the remainder is zero, the divisor becomes the gcd. If remainder is not zero, the remainder of the previous step becomes the divisor in the next step and the divisor becomes dividend. This continues until the remainder is zero. The divisor at the very last step becomes gcd of the two numbers.

Complete step-by-step answer:
In mathematics, the greatest common divisor (gcd) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted . For example, the gcd of 8 and 12 is 4.

i..135 and 225

First, divide 225 by 135.

\[\begin{align}
  & \text{dividend}=\text{divisor}\times \text{quotient}+\text{remainder} \\
 & 225=135\times 1+90 \\
\end{align}\]
     Since remainder is not 0, divide 135 by 90.
          \[\begin{align}
  & \text{dividend}=\text{divisor}\times \text{quotient}+\text{remainder} \\
 & 135=90\times 1+45 \\
\end{align}\]
     Since, the remainder is not 0, divide 90 by 45.
          \[\begin{align}
  & \text{dividend}=\text{divisor}\times \text{quotient}+\text{remainder} \\
 & 90=45\times 2+0 \\
\end{align}\]
     Here, the remainder is 0. The divisor becomes gcd.
     Therefore, gcd of 135 and 225 is 45.

ii.38220 and 196

First, divide 38220 by 196.

\[\begin{align}
  & \text{dividend}=\text{divisor}\times \text{quotient}+\text{remainder} \\
 & 38220=196\times 195+0 \\
\end{align}\]
Here, the remainder is 0. The divisor becomes gcd.
     Therefore, gcd of 38220 and 196 is 196.


Note: This is very similar to the division method to find gcd of two numbers. GCD can also be calculated using the prime factorization method where the prime factors of both the numbers are listed and the common factors with the least powers are multiplied. Another way of finding gcd is by listing all the factors of both the numbers and selecting the common factors. The greatest among them becomes the gcd.