Q. 74.2( 70 Votes )

Find the HCF of 1260 and 7344 using Euclid’s algorithm.
OR
Show that every positive odd integer is of the form (4q + 1) or (4q + 3), where q is some integer.

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
Genius Quiz | All About Magnetic Field33 mins
All about Coulomb's Law64 mins
All About Mass-Energy Equivalence56 mins
Quiz | Recalling the National Movement50 mins
Champ Quiz | Nationalism in India38 mins
NCERT | Nationalism in India-II53 mins
NCERT | Nationalism in India-I52 mins
Champ Quiz | Crops of India31 mins
All About Electricity38 mins
Rivers of India30 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