Divided by 2, 3, 4, 5, 6 gives remainder 1?

Number Theory Level 2

What is the smallest positive integer which is a multiple of 7, yet it gives a remainder of 1 when divided by any of 2, 3, 4, 5, or 6?

The answer is 301.

5 solutions

Sanyam Bajaj
Jan 6, 2016

Please don't go complicated just take their lcm(23456)which comes out to be 60 and add 1 to it =61now this no will remainder 1 in each of above numbers now keep adding 60 to it until thee comes a no divisible by 7and ans will be 301

If only your typing were as good as your maths!

Dorothy Taylor - 4 years, 6 months ago

Moaz Mahmud
Dec 30, 2016

$lcm(2,3,4,5,6) = 60.$

So the number is of the form, $60k + 1.$

Now,

$60k + 1 \equiv 0 (mod\ 7) \\ \Rightarrow60k \equiv -1 (mod\ 7)\\ \Rightarrow60k \equiv 6 (mod\ 7) \\ \Rightarrow10k \equiv 1 (mod\ 7) [gcd(7,60) = 1] \\ \Rightarrow10k \equiv -21 + 1(mod\ 7) \\ \Rightarrow10k \equiv -20 (mod\ 7) [gcd(7,20) = 1] \\ \Rightarrow k \equiv -2 (mod\ 7) \\ \Rightarrow k \equiv 5 (mod\ 7)$

So minimum positive value $k = 5$ gives the number $60\times 5 + 1 = 301$

Aravind Vishnu
Apr 23, 2015

$\text{let} \,x\, \text{be the number. We have}\\ x=1(\text{mod}2,3,4,5 \text{and}\, 6)\\ \text{lcm}[2,3,4,5,6]=60\\ \text{Therefore}\, x=1(\text{mod}60)\\ \text{and}\, x=0(\text{mod}7)\\ \text{such smallest positive number is}\, 301.$

Ahmed Mahmoud
Apr 19, 2015

The numbers divided by 5 gives 1 remainder means it should end either 1 or 6. But in case of number ends with 6 will be divided by 2. So only number ending with 1 have to consider. Also the number should be divisible by 7. So when number ending with 3 is multiplied by 7 will give result of number ending 1. So, possibilities are 7 * 3, 7 * 13, 7 * 23, etc

In that least number which solves this problem 7 * 43 = 301.

Moderator note:

There is a simpler way to solve this. Can you find it?

The least common multiple of 2, 3, 4, 5 and 6 is equal to 60. So we need to find out the lowest natural number value of i at which 60i + 1 is divisible by 7. And here, i = 5. Thus, the answer is 301.

Shyam Sundar - 6 years, 1 month ago

Here's a systematic way to show that $i=5$ works without guessing:

$7\mid 60i+1\implies 7\mid 4i+1\implies 4i\equiv (-1)\equiv 6\pmod{7}$

Now, since $\gcd(2,7)=1$ , we get,

$2i\equiv 3\pmod{7}\implies i\equiv 3\times 2^{-1}\pmod{7}$

Using Extended Euclidean Algorithm, we find the multiplicative modular inverse of $2$ modulo $7$ . We get,

$i\equiv 3\times 2^{-1}\equiv 3\times 4\equiv 12\equiv 5\pmod{7}$

Hence, $i=7\omega+5~,~\omega\in\Bbb{Z}$ . Since we need smallest positive integer, we take $\omega=0$ yielding $i=5$ which gives us the answer as $301$ .

Prasun Biswas - 6 years, 1 month ago

Let's keep this simple.. The problem says that the number is 7 times something. It also says that It leaves a remainder when divided by those numbers 2, 4 3, 5, 6, .
What this simply means is that the multiple to be multiplied by 7 cannot be a multiple of 2, or , 3, or 5 !! So 7 must be multiplied by a prime number. Take the largest number in the list, multiply by 7 then add 1. So the number to be multiplied by 7 is 43 !!

43 * 7 = 301 !!

DarkMind S. - 4 years, 9 months ago

DarkMind S.
Aug 25, 2016

Let's keep this simple.. The problem says that the number is 7 times something. It also says that It leaves a remainder when divided by those numbers 2, 4 3, 5, 6, .

What this simply means is that the multiple to be multiplied by 7 cannot be a multiple of 2, or , 3, or 5 !!! So 7 must be multiplied by a prime number.

Take the largest number in the list, multiply by 7 then add 1. So the number to be multiplied by 7 is 43 !!!

43 * 7 = 301 !!!!

Divided by 2, 3, 4, 5, 6 gives remainder 1?

The answer is 301.

5 solutions

Moderator note:

0 pending reports