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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

====

So your question:

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

Answer 4

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

Answer 5

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.