NEWAll India NCERT Mock Test Series is now live!Take Free Test
| Exercise 11.3

Q1: Find gcd⁡(99,75)\displaystyle \gcd(99,75) using the Euclidean algorithm.

UNDERSTAND THE QUESTION

  • We need to find the Greatest Common Divisor (gcd⁡\gcd) of two positive integers, 9999 and 7575, using the Euclidean algorithm.
  • Although the Euclidean algorithm is traditionally emphasized more in higher classes or specific number theory modules, the concept of repeated division to find the Highest Common Factor (HCF) is directly aligned with the NCERT curriculum's approach to finding the HCF of numbers.

Step 1 — APPLY DIVISION LEMMA ON THE LARGER NUMBER

Compare the two numbers, 9999 and 7575. Since 99>7599 > 75, apply the Division Lemma to 9999 and 7575 to find whole numbers qq and rr such that 99=75×q+r99 = 75 \times q + r, where 0≤r<750 \le r < 75.

99=75×1+24\begin{aligned} 99 &= 75 \times 1 + 24 \end{aligned}

Here, the remainder is r=24≠0r = 24 \neq 0. Since the remainder is not zero, we proceed to the next step.

Step 2 — APPLY DIVISION LEMMA ON THE DIVISOR AND REMAINDER

Now, take the divisor 7575 and the remainder 2424. Apply the Division Lemma to 7575 and 2424:

75=24×3+3\begin{aligned} 75 &= 24 \times 3 + 3 \end{aligned}

Here, 24×3=7224 \times 3 = 72, and 75−72=375 - 72 = 3. Thus, the remainder is r=3≠0r = 3 \neq 0. We continue the process.

Step 3 — CONTINUE THE PROCESS UNTIL THE REMAINDER IS ZERO

Next, take the new divisor 2424 and the new remainder 33. Apply the Division Lemma:

24=3×8+0\begin{aligned} 24 &= 3 \times 8 + 0 \end{aligned}

Here, the remainder has now become 00 (r=0r = 0).

The divisor at this stage, when the remainder is zero, is 33. Therefore, the gcd⁡\gcd of 9999 and 7575 is 33.

ANSWER

gcd⁡(99,75)=3\gcd(99, 75) = 3

COMMON MISTAKES

  • Stopping Prematurely: Stopping the division process before the remainder reaches 00.
  • Arithmetic Errors: Incorrectly calculating the quotient or remainder during the division steps (e.g., miscalculating 75÷2475 \div 24).

Was this solution helpful?

Quick Concept Check: Test Your Understanding

Interactive self-testing widget

?
What is the remainder when 99 is divided by 75 in the first step of the Euclidean algorithm?