Find the least number which when divided by 2, 3, 4, 5, 6 leaves a remainder of 1 but it is divided by 7 completely.

Question

I came across a question which is as follows:

Find out the smallest number which leaves remainder of 1 when divided by 2, 3, 4, 5, 6 but divided by 7 completely.

What I did is given below step wise.

Step 1- Find out the LCM of 2, 3, 4, 5, 6 which is 60.

Step 2- Add 1 to 60 which is 61.

Step 3- Multiple 61 by 7 repeatedly till it fulfills the condition that remainder should be 1.

Step 4- I got the answer 146461 which seems to correct.

So now my question is:

1) Is this answer correct? If yes how to verify that this is smallest number which fulfills above condition?

2) I think this is not the best way to do this question. So Can anyone give a better way to solve this problem?

Thanks in advance

Answer 1

You definitely need $n\equiv 1\pmod {60}$ and $n\equiv 0\pmod 7$. So the trick is to apply the Chinese remainder theorem. Solve $60x+7y=1$ with $(x,y)=(2,-17)$.

Then $n\equiv 1\cdot 7\cdot (-17)+0\cdot 60\cdot 2\pmod{420}$, or $n\equiv -119\pmod{420}$. The smallest such positive number is $420-119=301$.

Answer 2

Here's another way to tackle it. You already figured out that you're looking for $60k+1$. When you multiply $60$ by $k$ you want a predecessor to a multiplication of $7$.

$60 \equiv 4 \pmod 7$ and $5 \times 4 = 20$ which is a predecessor to a multiplication of $7$.

So $k=5$.

Answer 3

From $x\equiv 1 \pmod{60}$ we can proceed by adding the modulus until we find something congruent to $0\pmod{7}$:

$\pmod{60}:x\equiv 1 \equiv 61 \equiv 121 \equiv 181 \equiv 241 \equiv 301$.

Since $301\equiv 0\pmod{7}$, it gives the minimal solution.

Answer 4

Consider $60k+1,$ $$60(7n)+1=420n+1$$ $$60(7n+1)+1=420n+61$$ $$60(7n+2)+1=420n+121$$ $$60(7n+3)+1=420n+181$$ $$60(7n+4)+1=420n+241$$ $$60(7n+5)+1=420n+301$$ $$60(7n+6)+1=420n+361.$$ Now by divisibility test for 7, among $1, 61, 121, 181, 241, 301, 361$, only $301$ is divisible by $7.$

Therefore any number of the form $420n+301$ satisfies the given requirements.

Answer 5

Below are a few different approaches (besides the standard Extended Euclidean Algorithm).

${\rm mod}\ 60\!:\ x\equiv 1\equiv 7n\!\iff\! n\equiv\dfrac{1}7\equiv \dfrac{-59}7\equiv \dfrac{-119}7\equiv -17\,$

therefore $\smash[t]{\,x = 7(\overbrace{-17\!+\!60k}^{\large n}) = -119+420k}$

Alternatively $\:\! $ mod $\,60\!:\ \color{#c00}{7^4\equiv 1}\,$ (by true mod $3,4,5)\,$ so $\smash[b]{\,\color{#c00}{7^{-1}\equiv 7^3}\equiv 7(\underbrace{-11}_{\Large 7^2})\equiv -17}$

Alternatively $ $ we can employ $ $ Inverse Reciprocity

$\qquad\!\! \dfrac{1}7\ {\rm mod}\ 60\ \equiv\ \dfrac{1-60\overbrace{\left(\color{#c00}{\dfrac{1}{60}}\ {\rm mod}\ 7\right)}^{\Large \color{#0a0}{\equiv\, 2}}}7\,\equiv\, \dfrac{-119}7 \,\equiv\, -17\ $

where we've used: $\ \ {\rm mod}\ 7\!:\,\ \color{#c00}{\dfrac{1}{60}}\equiv \dfrac{8}4\color{#0a0}{\equiv 2}\,\ $ (or recurse on $\,\dfrac{1}{60}\bmod 7 \,\equiv\, \dfrac{1}4 \bmod 7\,)$

See here and its links for further methods and elaboration.

Remark $ $ In the first method we found a numerator $\,-119\equiv 1\pmod{60}$ that's also divisible by $7$ by brute force, i.e. we tested $\,1-60k\,$ for $\,k=1,2\ldots$ But now we see that the solution $\,\color{#0a0}{ k\equiv 2}\,$ is simply $\, k = \color{#c00}{\dfrac{1}{60}}\,\bmod\, 7,\,$ a "reciprocal" of our sought $\,\dfrac{1}7\bmod 60\,$ (i.e. swap $\,7, 60)$.

Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.

Answer 6

Since no-one has mentioned it in their answers so far, your step 3 is wrong, or at least ill-advised, in that you are coming across a lot of answers that do not meet your carefully-set-up satisfaction of the first five conditions. For example, $61\times 7 = 427$ does not meet the desired remainders for $4$ or $5$.

The problem is that you have abandoned the safety of $n\equiv 1 \bmod 60$. The way to retain this in a simple search is to add 60 repeatedly looking for divisibility by 7.

We can do a bit better than that, though. We can translate into smaller numbers to make life easier for ourselves. $60 \equiv 4 \bmod 7$ (and of course $61 \equiv 5 \bmod 7$) so we can ask: how many 4s do we need to add to 5 before the answer is divisible by 7?

Again we can slog through the possibilities but the multiples of 7 are easier to cope with. We add two 4s (13 - and maybe see that we've reached $6 \bmod 7$) and add another two 4s to reach $21 \equiv 7 \equiv 0 \bmod 7$ - adding four 4s altogether. So back on our Actual Problem, we need to add four 60s - $4\times 60=240$ to our original $61$ so $ 240+61=301$ for the smallest positive solution.

Note that $60$ is your interval between satisfying those first 5 conditions, but we could also have started our search at $1$ rathe than $61$, with (of course) the same eventual result.