2
$\begingroup$

I want the multiple of $7$ that has remainder $1,2,3$ divided by $2,3,4$ respectively.

Now I have had a search of similar questions, but I may have missed it since I am on a phone.

This question should be trivial to me, but I am having trouble, so that is depressing enough, please just give me a hint.


It would appear that I am dealing with:

$$\frac{7x}2\equiv 1\pmod 7$$ $$\frac{7x}{3} \equiv 2\pmod 7 $$ $$\frac{7x}{4} \equiv 3 \pmod 7$$

and then I find inverses for $2,3,4$ and multiply both sides by these, then apply Chinese remainder theorem. But having the different remainders under the same modulus makes no sense, so this leads me to believe I have formulated the question wrong, and chosen the wrong modulus. Thanks

$\endgroup$
  • $\begingroup$ The equations you set up are wrong.Try to use the definition of (\mod) to rewrite the equations. $\endgroup$ – rah4927 Jan 5 '15 at 5:44
  • $\begingroup$ @Rah Is that in the answer the correct approach? $\endgroup$ – user142198 Jan 5 '15 at 5:45
  • 3
    $\begingroup$ The first bunch is equivalent to $x\equiv -1\pmod{12}$. We also want $x\equiv 0\pmod{7}$. There will be a unique solution modulo $84$. $\endgroup$ – André Nicolas Jan 5 '15 at 5:47
3
$\begingroup$

Let $n$ be the number you want, then $n+1$ is a multiple of $2,3,4$ that is congruent to $1\bmod 7$. So a multiple of $12$ that is $1$ mod $7$. since $12$ is $5$ mod $7$ and the inverse of $5\bmod 7$ is $3$ we get $12\cdot3=36$ is a valid solution for $n+1$. thus $35$ is a valid value for $n$

Notice a much more general way to solve congruence systems is via the chinese remainder theorem.

$\endgroup$
1
$\begingroup$

Solution:

First recognise that $x \equiv 3 \pmod 4 \implies x \equiv 1 \pmod 2$. The latter criterion is redundant.

So you can simply solve this system:

$$x \equiv 3 \pmod 4$$ $$x \equiv 2 \pmod 3$$

From the second equation, $x = 3s+2$.

Subbing into second equation, $3s+2 \equiv 3 \pmod 4$, giving $3s \equiv 1 \implies s \equiv 3^{-1} = 3 \pmod 4$. Hence $s = 4t + 3$.

So $x = 3(4t+3) + 2 = 12t + 11$ or $x \equiv -1 \pmod{12}$, which is the solution of all three congruences.

Finally, you have to incorporate the divisibility by seven criterion:

$x = 7y \implies 7y \equiv -1 \pmod{12} \implies y \equiv -1.7^{-1} = -7 \equiv 5 \pmod{12}$.

Hence the required solution is $x = 7(12v + 5)$, also expressible as $x \equiv 35 \pmod{84}$. Some possible particular solutions are: $35, 119, 203,..$ etc.

$\endgroup$
  • $\begingroup$ Sorry this didn't load with my bad connection so I have only just seen it. I will read it now. $\endgroup$ – user142198 Jan 5 '15 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy