Try this beautiful problem from Singapore Mathematics Olympiad, SMO, 2013 based on HCF.
Problem on HCF | SMO, 2013 | Problem 35
What is the smallest positive integer n,where \( n \neq 11\) such that the highest common factor of n-11 and 3n +20 is greater than 1?
Check the Answer
But try the problem first…
Singapore Mathematics Olympiad
Challenges and Thrills – Pre – College Mathematics
Try with Hints
If you got stuck in this sum we can start from here:
Let d is the highest common factor of n-11 and 3n +20 which is greater than 1.
So d|(n-11) and d|(3n + 20) .
If we compile this two then d|(3n +20 -3(n-11) when d|53 .
Now one thing is clear that 53 is a prime number and also d >1
so we can consider d = 53.
Now try the rest………………
Now from the previous hint
n-11 = 53 k (let kis the +ve integer)
n = 53 k +11
So for any k 3n +20 is a multiple of 53.
so 3n + 20 = 3(53k +11) +20 = 53(3k+1)
Finish the rest………..
Here is the final solution :
After the last hint :
n = 64 (if k = 1) which is the smallest integer. as hcf of (n – 11,3n +20)>1(answer)