
Find g.c.d of (i) 135 and 225 (ii) 38220 and 196 by Euclid’s algorithm.
Answer
511.2k+ views
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.
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.
Recently Updated Pages
Master Class 11 Physics: Engaging Questions & Answers for Success

Master Class 11 Chemistry: Engaging Questions & Answers for Success

Master Class 11 Biology: Engaging Questions & Answers for Success

Class 11 Question and Answer - Your Ultimate Solutions Guide

Master Class 11 Business Studies: Engaging Questions & Answers for Success

Master Class 11 Computer Science: Engaging Questions & Answers for Success

Trending doubts
What is the Full Form of ISI and RAW

Which of the following districts of Rajasthan borders class 9 social science CBSE

Difference Between Plant Cell and Animal Cell

Fill the blanks with the suitable prepositions 1 The class 9 english CBSE

Name the states which share their boundary with Indias class 9 social science CBSE

What is 85 of 500 class 9 maths CBSE
