Basic HCF/GCD problem
What is the highest common factor of 2442 and 17171?
Note : Try not to use a calculator.
The answer is 11.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
4 solutions
Can you tell me properly from first step
Divide 2442 into 17171. Get the remainder, then divide the remainder into 2442. Get that remainder. Take the 2nd remainder and divide into the 1st remainder. Divide the remainders until the remainder is 0.
Relevant wiki: Euclidean Algorithm
Apply the Euclidean algorithm:
1 7 1 7 1 = 2 4 4 2 = 7 7 = 5 5 = 2 2 = 2 4 4 2 × 7 7 7 × 3 1 5 5 × 1 2 2 × 2 1 1 × 2 + 7 7 + 5 5 + 2 2 + 1 1 + 0 .
The process stops since we reached 0 , and we obtain
1 1 = g cd ( 1 1 , 2 2 ) = g cd ( 2 2 , 5 5 ) = g cd ( 5 5 , 7 7 ) = g cd ( 7 7 , 2 4 4 2 ) = g cd ( 2 4 4 2 , 1 7 1 7 1 ) . □
17171 = 7 * 2442 + 77 <=1st Remainder 2442 = 31 * 77 + 55 <=2nd Remainder 77 = 1 * 55 + 22 1st Remainder/2nd Remainder = 3rd Remainder 55 = 2 * 22 + 11 22 = 2 * 11 + 0
1) 17171/2442 =7R77
2) 2442/77=31R55
3) 77/55=1R22
4) 55/22=2R11
5) 22/11=2R 0
The highest common factor of 2442 and 17171 is 11.
(2442,17171)
17171-2442x7=77
(2442,77)
2442-77x31=55
(55,77)
77-55=22
(55,22) [At this point you should know the GCD/HCF already]
55-22x2=11
(11,22)
GCD/HCF is 11.