# Chinese Remainder Theorem/Simultaneous congruences

Find an integer N , 0 ≤ N < 105 such that

N ≡ 2 mod 3,

N ≡ 1 mod 5, and

N ≡ 4 mod 7.

What I have done:

So I have been able to start by splitting up the summation of $x$ into 3 sections:

$x = 5*7 + 3*7 + 3*5$

with the first multiplication corresponding with the mod 3 equation, the second multiplication corresponding with the mod 5 equation and the third multiplication corresponding with the mod 7 equation.

Therefore:

$x = 35 + 21 +15$

However, I know that this isn't complete. But I am not exactly sure on how to proceed.

Any help?

• Um... $3*5 \not \equiv 4 \mod 7$ so that won't do. – fleablood Jan 29 '18 at 20:56
• What happens when $N=11 + 105 k$? – Math Lover Jan 29 '18 at 20:57

$N \equiv 2 \mod 3$ so $N = 2 + 3a$.

$N \equiv 1 \mod 5$ so $N =1 + 5b$

So $2+3a = 1 + 5b$ so $5b - 3a = 1$. One solution is $b = 2$ and $a = 3$

So $N \equiv 2 + 3*3 = 1 + 2*5 = 11 \mod 3*5$.

So $N = 11 + 15c$.

$N \equiv 4 \mod 7$ so $N = 4 + 7d$.

So $11 + 15c = 4 + 7d$ so $15c - 7d = -7$. $c =0$ and $d = 1$ is a solution.

So $N \equiv 11 = 4+7 \equiv 11 \mod 3*5*7 = 105$.

And, indeed, $11 \equiv 2 \mod 3$ and $11 \equiv 1 \mod 5$ and $11\equiv 4 \mod 7$.

$5*7 = 35 \equiv 2 \mod 3$ so that satisfies.

$3*7 = 21 \equiv 1 \mod 5$ so that satisifies.

$3*5 = 15 \equiv 1 \not \equiv 4 \mod 7$ so that does not satisfy.

But $4*3*5 \equiv 4 \mod 7$ so that does.

So $5*7 + 3*7 + 60 = 116$ solves all three. But $116 > 105$. But any $k \equiv 116 \mod 105$ so do so $116 - 105 = 11$ will do.

.... or ... when we hae $3*5 \equiv 1 \mod 7$ and we could have figured $4 \equiv -3 \mod 7$ so $-3*3*5 \equiv 4 \mod 7$.

So $N = 5*7 + 3*7 - 3*3*5 = 11$. (by taking a negative we know we won't get a number too large).

Actually, I had never done the "partitioning" before.

It works well. I like it.

With what you have:

$x = a\cdot 35 + b\cdot 21 + c\cdot 15 + d\cdot 105\\ 35 \equiv 0\pmod 7, 0\pmod 5, 2\pmod 3\\ 21 \equiv 0\pmod 7, 1\pmod 5, 0\pmod 3\\ 15 \equiv 1\pmod 7, 0\pmod 5, 0\pmod 3\\$

$a = 1, b = 1, c = 4$ would give the give the right answers for each modulus.

$x = 116 - d\cdot 105\\ x = 11$

The number $105$, and the moduli $3, 5, 7$ are small enough that you can just reason it through.

For $N \equiv 2 \bmod 3$, we just need $N$ to be one less than a multiple of $3$.

To also satisfy $N \equiv 1 \bmod 5$, we need $N \equiv 11 \bmod 15$.

So the possible solutions are $11, 26, 41, 56, 71, 86, 101$. Now we can just check which of those satisfy $4 \bmod 7$, and it's just our luck that the first number is $7 + 4 = 11$. That's our answer.

Find an integer $N$ , $0 ≤ N < 105$, such that

\begin{align} N &≡ 2 \pmod 3 \\ N &≡ 1 \pmod 5 \\ N &≡ 4 \pmod 7 \end{align}

\begin{array}{c|ccc} & 3 & 5 & 7 \\ \hline 35 & \\ 21 & \\ 15 \\ \hline \end{array}

Where $35 = \dfrac{3 \cdot 5 \cdot 7}{3} = 5 \cdot 7$, $21 = \dfrac{3 \cdot 5 \cdot 7}{5} = 3 \cdot 7$, and $15 = \dfrac{3 \cdot 5 \cdot 7}{7} = 3 \cdot 5$.

Fill in the table with $\text{[number in row$i$] mod [number in column$j$]}$

\begin{array}{r|rrr} & 3 & 5 & 7 \\ \hline 35 & 2 & 0 & 0 \\ 21 & 0 & 1 & 0\\ 15 & 0 & 0 & 1\\ \hline \end{array}

What you want is to get $1$s in the diagonal and $0$s everywhere else. So, in this case, we need to get a $1$ in the upper left corner.

The way you have to change that number is find an integer $k$ such that $35k \equiv 1 \pmod 3$. There is more than one answer. I will use $k=-1$, that is, $-35 \equiv 1 \pmod 3$. I record this, and any unchanged values, as

\begin{array}{r|rrr} & 3 & 5 & 7 \\ \hline 35 & 2 & 0 & 0 \\ 21 & 0 & 1 & 0\\ 15 & 0 & 0 & 1\\ \hline -35 & 1 & 0 & 0 \\ 21 & 0 & 1 & 0\\ 15 & 0 & 0 & 1\\ \hline \end{array}

An interesting thing to note is that $-35+21+15 \equiv 1 \pmod{105}$ where $105 = 3 \cdot 5 \cdot 7$. This will be true in all cases that apply to the CRT. It is always possible, as in this case, to find numbers such that the sum of the numbers in the bottom left column is $1$.

So, what is so important about these numbers, $-35, 21,$ and $15$?

1. They are idempotent elements of $\mathbb Z_{105}$.

\begin{align} (-35)^2 &\equiv -35 \pmod{105} \\ 21^2 &\equiv 21 \pmod{105} \\ 15^2 &\equiv 15 \pmod{105} \end{align}

1. They annihilate each other in $\mathbb Z_{105}$.

\begin{align} -35 \cdot 21 &\equiv 0 \pmod{105} \\ -35 \cdot 15 &\equiv 0 \pmod{105} \\ 21 \cdot 15 &\equiv 0 \pmod{105} \\ \end{align}

1. The Chinese Remainder Theorem states that the mapping $:\mathbb Z_{105} \to \mathbb Z_3 \times \mathbb Z_5 \times \mathbb Z_7$ defined by $:n \mapsto (n, n, n)$ is a ring isomorphism and the inverse mapping $:\mathbb Z_3 \times \mathbb Z_5 \times \mathbb Z_7 \to \mathbb Z_{105}$ defined by $(a,b,c) \mapsto -35a+21b+15c$ is also a ring isomorphism.

The number you seek is computed as

$$N \equiv 2(-35) + 1(21) + 4(15) \equiv 11 \pmod{105}$$