# How can I solve a problem using the Chinese remainder theorem and how does mod operator is understood correctly?

The situation is as follows:

$$n = 3a + 2$$

$$n = 7b + 5$$

$$n = 8c + 9$$

Find the $n$ so it is less than $100$ and $a$, $b$ and $c$ are positive integers.

I know that this can be solved using the Chinese remainder theorem but I don't know how to use it. Therefore I'd like that somebody could explain me exactly how does $\mod{}$ operator works.

The only thing I know is that $\bmod$ is used to express the remainder of an euclidean division. Like this

$5$ divided by $2$ means:

$5\,\bmod\,2 = 1$

Because the remainder is $1$.

But what if the situation is like this?:

$2\,\bmod\,9$

Would this mean

$$\frac{2}{9} = 0.2 \times 9 + 2 ?$$

So the remainder is $2$? It does not seem right as going backwards does not produce $2$ in the sense $0.2\times 9 + 2$ is not $2$.

How about negative numbers

However how does it work with negative numbers? Like:

$-3\bmod 25$

As mentioned above if I follow the same route I may find weird results.

But that's only one part of the problem, as the second thing is How to understand this when $\mod{}$ is used as follows:

$24\equiv 14 \left ( \bmod 10 \right )$

From what I had understood it means that both share the same remainder which is $4$.

But the problem lies on how to translate the equations I have been given into the equation from above, the one which uses $\mod{}$?

Therefore I'd like somebody could help me with a clearly step-by-step solution that can explain how to build up the $\mod{}$ equations and how to solve them the easiest way possible.

The $\textrm{mod}$ notation is not an operator that gives you a single output.

Don't read it as if it was computer code. I would only read the $\textrm{mod}$ notation in English. $\text{mod}\;n$ means the preceding equation/formula is under modulus $n$. In the context of integer numbers, we consider each integer number by its Euclidean remainder when divided by $n$.

$\equiv$ is a notation for equivalence relations. Please read its introductions on the internet.

For example, we say 13 is equivalent (or congruent, some even say equal, depending on the context) to 23 modulus 10, denoted by $13\equiv23\;\textrm{mod}\;10$ because they have the same remainder when divided by 10, which is 3. Negative number is usually read "in reverse". For example, $13\equiv-7\;\textrm{mod}\;10$.

As for your puzzle at the beginning, you don't have to use Chinese Remainder Theorem. I think Chinese Remainder Theorem is a bit of a leap when you are just learning the mod notation. Try solving the puzzle yourself without the theorem and share where you are first.

As you say; $x\equiv a\bmod p$ tells you that when you divide $x$ by $p$, it gives you a remainder of $a$.

So, $5/2$ gives you a remainder of $1$; so this is equivalent to saying that $5\equiv 1\bmod 2.$

As for expressions such as $-3\bmod 25$. Be aware that a number having a remainder of $-3$ when divided by $25$ is the same as the number having remainder $22$; so $-3\bmod 25$ is the same as $22\bmod 25.$

Applying this to your problem at hand, $n=3a+2$ is the same as $n\equiv 2\bmod 3.$ Similarly, $n=7b+5$ is equivalent to $n\equiv 5\bmod 7.$ Finally, $n=8c+9$ is equivalent to $n\equiv 9\bmod 8,$ which is the same as $n\equiv 1\bmod 8.$ So we are interested in solving the system $$n\equiv 2\bmod 3,\quad n\equiv 5\bmod 7,\quad n\equiv 1\bmod 8.$$ As you rightfully point out, we may use the Chinese remainder theorem and come to a conclusion that this system has a unique solution in the form of $$n\equiv x\bmod3\cdot 7\cdot 8=168,$$ where $x$ is the answer we seek. So let's systematically solve this.

The congruence $n\equiv 1\bmod 8$ implies $n=8c+1.$ Substituting this into the $n\equiv 5\bmod 7$ congruence gives $$8c+1\equiv 5\bmod 7.$$ Solving this gives $$8c\equiv 4\bmod 7,$$ $$c\equiv 4\bmod 7.$$ This means there exists an integer $d$ such that $c=7d+4.$ Substituting this into our expression involving $n$ gives $n=56d+33.$ Now, substituting this expression into the $n\equiv 2\bmod 3$ congruence gives $$56d+33\equiv 2\bmod 3.$$ Solving this gives $$56d\equiv 2\bmod 3,$$ $$2d\equiv 2\bmod 3,$$ $$d\equiv 1\bmod 3.$$ This means there exists an integer $e$ such that $d=3e+1.$ Substituting this into our expression involving $n$ gives $n=168e+89.$ Now, this means that $n\equiv 89\bmod 168.$ Since this is less than $100$; we are done, concluding that $$x=89.$$

Hope this helps. Do feel free to ask me further questions if you are still confused.

• Okay let's recap. I thought it was $a \mod p$ meant let's say $5 \mod 2$ another way to say $1$, since that's the remainder and when you write $x \equiv a \mod p$ it was to relate two number which share the same remainder and just that. If it is as you say then I'm wrong or missunderstood. The second part well is not very obvious. Why having a remainder of $-3$ divided by $25$ is the same as the number having a remainder $22$? In order to speed up the calculations, is there a trick to get this number fast instead of guessing or proving this mentally each time? – Chris Steinbeck Bell Mar 22 '18 at 16:23
• Why do we want to have $n \equiv 1 \mod 8$ instead of $n \equiv 9 \mod 8$?. Now, for the execution of the theorem in the problem, it means that we want the divisor to be the least common multiple right since I'm seeing you put $\textrm{mod (3)(7)(8)}$? – Chris Steinbeck Bell Mar 22 '18 at 16:24
• I'm stopping here to ask why are we "changing" the original equation $8c+9$ into $8c+1$ for equating to the second congruence, wouldn't the original also work i mean the $8c+9$?. To solve the congruence equation with mod is tricky. From $8c+1 \equiv 5 \mod 7$ becoming into $8c \equiv 4 mod 7$ I'm assuming you take the difference between $5$ and $1$, treating it as if the congruence is a linear equation. But the $4$ is what I don't get it. Why it doesn't change?. Aren't you dividing it by $8$?. – Chris Steinbeck Bell Mar 22 '18 at 16:24
• Then for the last mod congruence. There is $56d + 33 \equiv 2 \mod 3$. What happened to the $33$? How does $56$ becomes into $2$ and in the last step are we dividing $2$ by $2$?. The very final step is a bit clear as we're going back to replace $d$ into the equation we found from the step before and all that is "left" is just take the remainder which you say is $89$. That's all I'm stuck at. Can you please clear these doubts?. – Chris Steinbeck Bell Mar 22 '18 at 16:25
• There is one thing which I forgot from all I mentioned so far and is Why did you choose to begin with $n\equiv 1 \mod 8$ Can the same results be achieved otherwise, I mean if I start from $n \equiv 2 \mod 3$?. – Chris Steinbeck Bell Mar 22 '18 at 16:27

The only thing I know is that $\textrm{mod}$ is used to express the remainder of an euclidean division. Like this

$\textrm{5 divided by 2}$ means:

$5\,\textrm{mod}\,2 = 1$

Because the remainder is $1$.

So far so good. Also note that $2 \times 2 + 1 = 5$.

But what if the situation is like this?:

$2\,\textrm{mod}\,9$

Would this mean?:

$\frac{2}{9}= 0.2\times 9 + 2$

So the remainder is $2$?. It does not seem right as going backwards does not produce $2$ in the sense $0.2\times 9 + 2$ is not $2$.

Here you got off track. The "meaning" is $0 \times 9 + 2 = 2$. Limiting our attention to integers is kind of the point of moduli and remainders.

How about negative numbers

However how does it work with negative numbers? Like:

$-3\,\text{mod}\,25$

As mentioned above if I follow the same route I may find weird results.

No kidding. $-1 \times 25 + 22 = -3$. Am I repeating what the others have already said?

But that's only one part of the problem, as the second thing is How to understand this when $\textrm{mod}$ is used as follows:

$24\equiv 14 \left ( \textrm{mod 10} \right )$

From what I had understood it means that both share the same remainder which is $4$.

That's right, and it's true of any positive integer having a least significant digit of $4$ in base $10$. Also of any negative integer having a least significant digit of $6$ in base $10$.

Picture the real number line with negative infinity far off to the left, far beyond the range of your vision, and positive infinity far off to the right, also farther away than you can see.

Now picture dots for all multiples of your modulus, like $10$. A remainder of $4$ means any number four unit steps to the right of $10$, and a remainder of $-6$ means any number six unit steps to the left.

As for the exercise, try solving it with just two congruences instead of three. For example, try to see if you can solve $n = 3a + 2$ and $n = 7b + 5$ without worrying if it also solves $n = 8c + 9$. In the space between $0$ and $21$ (which is equal to $3 \times 7$) there should be one answer, and another between $21$ and $42$, and so on and so forth.

Given $k$ being any integer whatsoever, how many primes are of the form $4k + 1$? $4k - 1$? $6k + 1$? etc. Often in number theory you look at numbers of the form $mk + r$, where $m$ is a modulus, usually positive, and $r$ is a remainder, usually satisfying $-m < r < m$.

Then the exact value of $k$ is not all that important, or it can be temporarily ignored. And so there is the convenient shorthand $n \equiv r \bmod m$, or $n \equiv r \pmod m$ (slightly more ink but zero more bytes in your TeX source). This means $n = mk + r$ but we're not too concerned with $k$, at least for now.

So, to solve $$n \equiv 2 \bmod 3$$ $$n \equiv 5 \bmod 7$$ $$n \equiv 9 \bmod 8$$ we can, um, wait a minute, let's rephrase that last one as $$n \equiv 1 \bmod 8$$ Now we have a system of simultaneous congruences, and since the moduli are coprime, we're not worried about contradictory congruences (e.g., $1 \bmod 2$ and $2 \bmod 4$).

Since I'm not going to be tested on this, I can just ask Wolfram Alpha: ChineseRemainder[{2, 5, 1}, {3, 7, 8}]. Besides, the steps to solving simultaneous congruences are covered in other Math.SE questions and answers.

Wolfram Alpha tells me the answer is 89. It checks out: $$89 = 3 \times 29 + 2$$ $$89 = 7 \times 12 + 5$$ $$89 = 8 \times 11 + 1$$ Well, that last one needs to be adjusted: $c = 10$ rather than 11.

While 89 is the only positive number less than 100 satisfying the simultaneous congruences, it is only one of infinitely many solutions without the restriction. To find the other solutions, multiply the moduli (in this case 168) and add or subtract as many times as you wish. Then for example $$257 = 3 \times 85 + 2$$ $$257 = 7 \times 36 + 5$$ $$257 = 8 \times 32 + 1$$ $-79$ also checks out, but mind your direction.

And by the way, 89 is a prime of the following forms: $6k - 1$ (same thing as $6k + 5$), $4k + 1$, $8k + 1$, and others of decreasing number-theoretic interest.

If I may pique your interest in algebraic number theory, that $89 \equiv 1 \bmod 8$ means that 2 is not prime in $\mathcal O_{\mathbb Q(\sqrt{89})}$, and indeed $$(-1)\left(\frac{9}{2} - \frac{\sqrt{89}}{2}\right)\left(\frac{9}{2} - \frac{\sqrt{89}}{2}\right) = 2.$$

• Why do we want to "reduce" or rephrase $n \equiv 9 \bmod 8$ into $n \equiv 1 \bmod 8$, so as to make the other expressions also non reducible? Why did you adjusted the last equation to make $c=10$ instead of $c=11$?. I'm stuck at this. Probably the most important part here is how to solving simultaneous congruences. Can you give an example on how to do this quickly?. – Chris Steinbeck Bell Mar 23 '18 at 5:27
• Because you were given $n = 8c + 9$, not $n = 8c + 1$. The quickest way to solve simultaneous congruences quickly is to have a computer solve them for you. Which I doubt is an option available at an exam. Any time there is more than two congruences, I find the whole process rather tedious. Wolfram Alpha can show you the steps for a particular CRT computation, as can this calculator: mathcelebrity.com/… – Robert Soupe Mar 23 '18 at 12:50
• Oops, the Math Celebrity CRT calculator gives the answer as $-415$... but you can just try adding 168 until you get a positive number. If you give it the last one as $x \equiv -7 \bmod 8$ (remember that $-8 + 1 = -7$) then it will give you 89 right off the bat. – Robert Soupe Mar 23 '18 at 12:54
• I have a calculator which does support programming maybe there is a way to make a program for solving the system. Now, $x \equiv -7 \bmod 8$ isn't the same as $1 \bmod 8$ and this wouldn't be other way to say $1 \equiv 1\bmod 8$?. So $x=1$?. CRT does not seem to work with numbers which are not coprimes let's say if it were $2,6,10$.? In such kind of situation what is the way to solve the problem? Can CRT be modified to allow these kind of numbers?. – Chris Steinbeck Bell Mar 24 '18 at 2:54
• However, beware some programming languages, like REALBasic, are a little funny about negative remainders, e.g., $-7 \equiv 7 \pmod 8$, which is wrong. Others, like Java, will tell you for example that $-7 \equiv -3 \pmod 4$, which is correct but can trip you up if you're not watching out for it. – Lisa Mar 24 '18 at 20:56

$a \equiv b \mod n$ (notice the equivalence sign, $\equiv$ has three bars, not $2$) mean that $a$ and $b$ both have the same remainder when divided by $n$.

So for example, yes $5 \equiv 1 \mod 2$ but also $5 \equiv 7 \mod 2$.

A few things to notice:

1) $a \equiv b \mod n \iff \frac {a-b}n \in \mathbb Z \iff a = b + kn$ for some integer $k$. And $a \equiv 0 \mod n\iff n|a$.

2) For any natural number $n$, we can divide the integers, $\mathbb Z$, into exactly $n$ different subsets, or "classes". Class $[0] = \{...., -2n, -n, 0, n, 2n, 3n,...\}=\{kn + 0|k\in \mathbb Z\}$; these are all the integers that have remainder $0$ when divided by $n$. Class $[1] = \{...,-2n, -n+1, 1, n+ 1, 2n+1,...\}=\{kn + 1|k\in \mathbb Z\}$; these are all the integers that have remainder $1$ when divided by $n$. And so on. Class $[i] = \{...,-2n, -n+i, i, n+ i, 2n+i,...\}=\{kn + i|k\in \mathbb Z\}$. There are exactly $n$ of these classes. $a \equiv b \mod n$ means that both $a$ and $b$ belong to the same one of these classes.

The classes in 2) are called equivalence classes because when doing basic arithmetic in regards to remainders when divided by $n$, if two numbers have the same remainder they are ... well... equivalent that is.

Proposition: If $a \equiv b \mod n$ then $a \pm k \equiv b \pm k$ and $k*a \equiv k*b \mod n$ and $a^k \equiv b^k \mod n$. Also if $c \equiv d \mod n$ then $a+c \equiv b+d \mod n$ and $ac \equiv bd\mod n$.

Ex: $5 \equiv 12 \mod 7$ so $5k \equiv 12k \mod 7$ because $12k = 7k + 5k \equiv 5k \mod 7$.

To solve an equation such as $3x \equiv 6 \mod 9$ can have multiple solutions. $x$ can be $2$ because $3*2 = 6\equiv 6 \mod 9$. But $x$ can also be $5$ because $3*5 = 15 \equiv 6 \mod 9$. $x$ could also be $8$ becase $3*8 = 24\equiv 6 \mod 9$. The next solution is $x = 11$ as $3*11=33\equiv 6 \mod 9$. But because $2 \equiv 11 \mod 9$, $2$ and $11$ are considered to be the same solution because $2$ and $11$ are equivalent (modulo $9$).

So it turns out there are three classes of solutions: $x \equiv 2 \mod 9$, or $x\equiv 5 \mod 9$, or $x \equiv 8 \mod 9$.

So the Chinese Remainder Theorem states:

If you have a system of equations:

$x \equiv a_1 \mod n_1$

$x \equiv a_2 \mod n_2$ ....

And all the $n_i$ are relatively prime (have no factors in common) then

$x \equiv b \mod n_1n_2n_3....n_m$ has one specific modulo class mod $n_1n_2n_3...n_m$.

Example:

If $x \equiv 1 \mod 2$

$x \equiv 1 \mod 3$

$x \equiv 0 \mod 5$ then

$x \equiv ???? \mod 30$ has only one solution (from the classes $[0]$ to $[29]$). That solution is $x \equiv 25 \mod 30$.

====

$n = 3a + 2 \iff n \equiv 2 \mod 3$.

$n = 7b + 5 \iff n \equiv 5 \mod 7$

$n = 8c + 9 \iff n \equiv 9 \equiv 1 \mod 8$.

As $3,7, 8$ are relatively prime, there is one solution modulo $3*7*8= 168$.

$n\equiv 3a + 2 \equiv 7b + 5 \mod 21$ has one possible value (modulo $21$)

$3a + 2$ may be $2,5,8,...., 20$. And $7b + 5$ may be $5,12, 19$. The only option in common is $n \equiv 3a +2 \equiv 7b + 5\equiv 5 \mod 21$. So $n = 21d + 5$ for some $d$.

Now we also have $n \equiv 8(c-1) +1 \mod 21*8$ and $n \equiv 21d + 5\mod 21*8$.

So $8(c-1)+1$ may be $1, 9,17,.....$ and $21d+5$ may be $5, 26, 47, 68, 89, 110, 131, 152$. The only one in common is $89$.

So $n \equiv 3a + 2 \equiv 7b + 5 \equiv 8(c-1) + 1 \equiv 89 \mod 168$

And $a = \frac {87}3; b = \frac {84}7; c = \frac {80}8$.

• I'm stuck at trying to understand what it is written after $33 \equiv 6 \bmod 9$. Where does $2 \equiv 11 \bmod 9$ comes from?. I can understand that $3x \equiv 6 \bmod 9$ can become into $3x \equiv 15 \bmod 9$. But how can it become $11 \bmod 9$?. I dont understand exactly what you meant by the example in $x \equiv 1 \bmod 2$ and then you go to $x \equiv ??? \bmod 5$ and from there you go to $25 \bmod 30$. Wouldn't it be $x \equiv 25 \bmod 5$ the same as $x \equiv 0 \bmod 5$? Then you change the modulo to $30$. Why?. – Chris Steinbeck Bell Mar 23 '18 at 5:08
• The second part during the execution of the theorem I'm stuck at after finding the least common multiple you change it to $21$, why? Excluding one factor (and only using the lcm for the factors between the equations involved in the congruency. Could it be that there is another equation that am I missing?. – Chris Steinbeck Bell Mar 23 '18 at 5:08
• The third part is not very clear, why is it $5 \bmod 21$ and not $2 \bmod 21$? Both equations are equivalent but they are accompanied by two different number why you pick $5$ and not $2$?. – Chris Steinbeck Bell Mar 23 '18 at 5:09
• The rest follows the same procedure but as I don't understand it I'm stuck at there, can you please clear these ideas?. – Chris Steinbeck Bell Mar 23 '18 at 5:09
• $x \equiv 2 \mod 9$ is a solution because $3*6 \equiv 6 \mod 9$. And $x \equiv 11\mod 9$ is a solution because $3*11 \equiv 33 =27+6 \equiv 6 \mod 9$. But $x\equiv 2 \equiv 11 \mod 9$ so those are both the same solution. There are exactly three distinct solutions (and an infinite number of equivalent solutions). – fleablood Mar 23 '18 at 15:51