Vrftsjtryk

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

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

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

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.

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$.

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, $61times 7 = 427$ does not meet the desired remainders for $4$ or $5$.

The problem is that you have abandoned the safety of $nequiv 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 - $4times 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.

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

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

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

Alternatively $, $ mod $,60!: color{#c00}{7^4equiv 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-60overbrace{left(color{#c00}{dfrac{1}{60}} {rm mod} 7right)}^{Large color{#0a0}{equiv, 2}}}7,equiv, dfrac{-119}7 ,equiv, -17 $

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

Remark $ $ In the first method we found a numerator $,-119equiv 1pmod{60}$ that's also divisible by $7$ by brute force, i.e. we tested $,1-60k,$ for $,k=1,2ldots$ But now we see that the solution $,color{#0a0}{ kequiv 2},$ is simply the reciprocal inverse $, k, =, 1/60,bmod, 7.,$

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

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

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

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