Q. 74.2( 70 Votes )

# Find the HC

Answer :

By Euclid's algorithm

We know that Dividend = Divisor × Quotient + Remainder

⇒ 7344 = 1260 × 5 + 1044

⇒ 1260 = 1044 × 1 + 216

⇒ 1044 = 216 × 4 + 180

⇒ 216 = 180 × 1 + 36

⇒ 180 = 36 × 5 + 0

So, HCF of 1260 and 7344 is 36 because when the divisor is 36 remainder is 0.

OR

We know by Euclid's algorithm if a and b are two positive integers, there exist unique integers q and r satisfying,

a = bq + r where 0 ≤ r < b

Let, b = 4

a = 4q + r , 0 ≤ r < 4
So, r can be 0,1,2 and 3.
If r =0,
a = 4q
= 2(2q)
= 2n where n = 2q
which is an even integer.
If r =1,
a = 4q + 1
= 2(2q) + 1
= 2n + 1 where n = 2q
which is an odd integer.
If r =2,
a = 4q + 2
= 2(2q +1 )
= 2n where n = 2q + 1
which is an even integer
If r =3,
a = 4q + 3
= 4q + 2 + 1
= 2(2q +1) + 1
= 2n + 1 where n = 2q + 1
which is an odd integer
Thus "a" can be 4q, 4q + 1, 4q + 2, 4q + 3.

4q or 4q + 2 is not possible because they are even integers.

So, 4q + 1 or 4q + 3 are representing odd integers.
Hence, every positive odd integer is of the form (4q + 1) or (4q + 3).

Rate this question :

How useful is this solution?
We strive to provide quality solutions. Please rate us to serve you better.
Related Videos  Glimpses of India39 mins
Try our Mini CourseMaster Important Topics in 7 DaysLearn from IITians, NITians, Doctors & Academic Experts
Dedicated counsellor for each student
24X7 Doubt Resolution
Daily Report Card
Detailed Performance Evaluation view all courses 