CameraIcon
CameraIcon
SearchIcon
MyQuestionIcon
MyQuestionIcon
1
You visited us 1 times! Enjoying our articles? Unlock Full Access!
Question

Find the HCF of 32 and 616 by prime factorisation method and Euclid division algorithm

Open in App
Solution

By Euclid division lemma algorithm:


Step 1: Since 616 > 32, we apply the division lemma to 616 and 32, to get

616 = 32 x 19 + 8
Step 2: Since the reminder 32 ≠ 0, we apply division lemma to 8 and 32, to get
32 = 8 x 4 + 0
The remainder has now become zero, so our procedure stops. Since the divisor at this stage is 8, the HCF of 616 and 32 is 8
Notice that 8 = HCF(32,8) = HCF(616,32) .


And, By prime factorization method:

Prime factorization of 616 and 32 is (2 × 2 × 2 × 7 × 11) and (2 × 2 × 2 × 2 × 2) respectively. As visible, 616 and 32 have common prime factors. Hence, the HCF of 616 and 32 is 2 × 2 × 2 = 8.


flag
Suggest Corrections
thumbs-up
18
Join BYJU'S Learning Program
similar_icon
Related Videos
thumbnail
lock
The Fundamental Theorem of Arithmetic
MATHEMATICS
Watch in App
Join BYJU'S Learning Program
CrossIcon