1
$\begingroup$

Sorry for the weird title, but I don't know how else to phrase this.

Say I have a set of numbers, and the remainders each get by dividing them by a certain number. For instance:

$x \equiv 1 \pmod{3}$

$x \equiv 2 \pmod{4}$

$x \equiv 4 \pmod{5}$

$x \equiv 2 \pmod{7}$

I know the math is similar to finding the least common multiple, but I can't grok it. How do I find $x$ in the above equations, assuming they all use the same $x$?

Additionally, after that's found, how do I find further multiples that fit these restrictions?

$\endgroup$
4
  • $\begingroup$ You should write $x\equiv 1\pmod 3$. In MathJax, x \equiv 1 \pmod 3 .Read $x$ is congruent to $1$ mod (modulo) $3$. $\endgroup$ Feb 24, 2016 at 17:10
  • $\begingroup$ I don't think you or @NFTaussig understand, or you're using symbols I don't understand; I'm not saying x is (1 mod 3), I'm saying 1 is (x mod 3) $\endgroup$
    – Ky -
    Feb 24, 2016 at 18:59
  • 1
    $\begingroup$ @Ben C. R. Leggiero This convention of writing congruences is exactly the same as what you mean. (mod $m$) at the end of the line indicates that the whole line should be considered modulo $m$. $x≡n\pmod m$ is the same as $n≡x\pmod m$. (Only in computer programming is this any different because of the nature of how computer programs work) $\endgroup$
    – Shuri2060
    Feb 24, 2016 at 19:19
  • $\begingroup$ @QuestionAsker Thanks for clarifying! :) $\endgroup$
    – Ky -
    Feb 24, 2016 at 19:43

3 Answers 3

6
$\begingroup$

You can use the Chinese Remainder theorem for this. (By the way, you should write "(mod $m$)" at the end of each line rather than in the middle.)

Conventionally, you write:

$x ≡ n$ (mod $m$)

https://en.wikipedia.org/wiki/Chinese_remainder_theorem

On the other hand, if there are a small number of a congruences to be solved, you can solve the congruences intuitively (which is actually the method from which the Chinese remainder theorem is derived):

$x ≡ 1$ (mod 3)

$x ≡ 2$ (mod 4)

$x ≡ 4$ (mod 5)

$x ≡ 2$ (mod 7)

Consider the first congruence: $x ≡ 1$ (mod 3).

The smallest $x$ which satisfies this is 1.

Next consider $x ≡ 2$ (mod 4). If you add multiples of 3 to 1, then the 1st congruence will still be satisfied. So keep adding 3 until you find an $x$ which satisfies $x ≡ 2$ (mod 4):

1, 4, 7, 10

Next consider $x ≡ 4$ (mod 5). If you add multiples of the LCM of 3 and 4 (12), the first 2 congruences will still be satisfied.

After the first 3 congruences are satisfied, start adding multiples of the LCM of 3, 4 and 7 until the fourth is satisfied too.

Repeat this method until you find the solution for all of the congruences (note that when you add multiples of the LCM, you may not need to add any at all (in other words add it 0 times), as the congruence you are considering may already be satisfied).

This method will definitely work if all of the modulos in the congruences are coprime (as there is always a solution if this is the case).

When you get $x$ from applying this method, if you add any multiple of the LCM of 3, 4, 5 and 7, the 4 congruences will still be satisfied. So the solution would be:

$x$ (mod $\operatorname{lcm}(3, 4, 5, 7)$)

$\endgroup$
5
  • 2
    $\begingroup$ BTW you use \pmod to write things like $x\equiv2\pmod3$ $x\equiv2\pmod3$ or $a^2\equiv b^2\pmod{11}$ $a^2\equiv b^2\pmod{11}$. I am not sure whether it was your intention to have all four congruences in the same row. You can make linebreaks using <br> or two spaces, see Markdown help. $\endgroup$ Feb 24, 2016 at 18:57
  • $\begingroup$ Thank you - and no I didn't - thanks! $\endgroup$
    – Shuri2060
    Feb 24, 2016 at 18:59
  • $\begingroup$ Kinda confused why you say the solution is $x \pmod{\operatorname{lcm}(3, 4, 5, 7)}$ since I just read that as $x \pmod{420}$... shouldn't there be a $394$ in there somewhere? $\endgroup$
    – Ky -
    Feb 25, 2016 at 14:54
  • $\begingroup$ Sorry? I don't quite understand. I didn't actually do the system of congruences - so I don't know what the actual answer is. However, what the last line says is that if you find a solution, $x$, then if you add 420 to that solution, then the system of congruences still holds. (This is in response to "Additionally, after that's found, how do I find further multiples that fit these restrictions?") $\endgroup$
    – Shuri2060
    Feb 25, 2016 at 16:37
  • $\begingroup$ Ah right, I've just done it and found 394 as the answer. So the $x$ is 394 and your answer would be $394\pmod{420}$. Adding any multiple of 420 to 394 would still satisfy the equations. $\endgroup$
    – Shuri2060
    Feb 25, 2016 at 16:51
4
$\begingroup$

Since $x\equiv2\pmod{4}$ and $x\equiv2\pmod{7}$, we must have that $x\equiv2\pmod{28}$.

We can use the Extended Euclidean Algorithm as implemented in this answer to solve the following equivalences.

Since $140=5\cdot28$, solve $$ \begin{align} x&\equiv1\pmod{3}\\ x&\equiv0\pmod{140} \end{align} $$ getting $x\equiv280\pmod{420}$.

Since $84=3\cdot28$, solve $$ \begin{align} x&\equiv1\pmod{5}\\ x&\equiv0\pmod{84} \end{align} $$ getting $x\equiv336\pmod{420}$.

Since $15=3\cdot5$, solve $$ \begin{align} x&\equiv1\pmod{28}\\ x&\equiv0\pmod{15} \end{align} $$ getting $x\equiv225\pmod{420}$.

We can get the solution to the original equivalence as $$ x\equiv\overbrace{1\cdot280}^{\substack{1\pmod{3}\\0\pmod{4}\\0\pmod{5}\\0\pmod{7}}}+\overbrace{4\cdot336}^{\substack{0\pmod{3}\\0\pmod{4}\\4\pmod{5}\\0\pmod{7}}}+\overbrace{2\cdot225}^{\substack{0\pmod{3}\\2\pmod{4}\\0\pmod{5}\\2\pmod{7}}}\equiv\overbrace{\ 394\ }^{\substack{1\pmod{3}\\2\pmod{4}\\4\pmod{5}\\2\pmod{7}}}\pmod{420} $$

$\endgroup$
2
$\begingroup$

This is known as the Chinese Remainder Theorem. https://en.wikipedia.org/wiki/Chinese_remainder_theorem

This page describes the general solution method.

$\endgroup$

Your Answer

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