# Using Chinese Remainder Theorem to find an integer $x$ for which $x\equiv 3\pmod 4 x\equiv 5\pmod 9 x\equiv 10\pmod {35}$

Hello I have got problems with understanding the reduction method in CRT.

We have got system like this

$$x\equiv 3\pmod 4$$

$$x\equiv 5\pmod 9$$

$$x\equiv 10\pmod {35}$$

There is a way to do this by using highest powers $$x\equiv 3\pmod {2^2}$$

$$x\equiv 5\pmod {3^2}$$

$$x\equiv 10\pmod {5*7}$$

After reduction

$$x\equiv 1\pmod {2}$$

$$x\equiv 2\pmod {9}$$

$$x\equiv 3\pmod {7}$$

And here is my question Am I doing it good I always take the number with highest power or integer and thats all? Here are some examples

$$x\equiv 4\pmod {6}$$

$$x\equiv 13\pmod {15}$$

$$x\equiv 4\pmod {9}$$

Gives after reduction

$$x\equiv 0\pmod {2}$$

$$x\equiv 3\pmod {5}$$

$$x\equiv 4\pmod {9}$$

And one more

$$x\equiv 18\pmod {80}$$

$$x\equiv 58\pmod {100}$$

Gives

$$x\equiv 18\pmod {2^4*5}$$

$$x\equiv 58\pmod {2^2*5^2}$$

Then

$$x\equiv 2\pmod {16}$$

$$x\equiv 8\pmod {25}$$

And here is my question I just take the biggest numbers and forget about those smaller for example in

$$x\equiv 18\pmod {2^4*5}$$

$$x\equiv 58\pmod {2^2*5^2}$$

I check i got $2^4$ so I take this and i delete 5 and I make it to

$$x\equiv 18\pmod {2^4}$$

And in the second coengurence

$$x\equiv 58\pmod {2^2*5^2}$$ I take $5^2$ becouse its higher and delete $2^2$

so i have

$$x\equiv 58\pmod {5^2}$$

This is how this method work? It is a bit intuitive or this ($*5$ from first and $2^2$ from second is somehow in other way reduced?

Or i need to do something like system:

$$x\equiv 18\pmod {5}$$

$$x\equiv 18\pmod {16}$$

$$x\equiv 58\pmod {4}$$

$$x\equiv 58\pmod {25}$$

And then somehow reduce it? But in this situation I don't know how to reduce it.

And I've got one more question. Does Linear Diophantine Equations work for every linear congruence?

For GCD(x,y) = 1 and for GCD(x,y) > 1 (with more solutions)

I mean this method

$x(a) + y(b) = d$

then after making euclidean alghoritm

$x = a + y/d * t$

And I search for t which complete my equation

I will be very thankful for every help.

• Seems like a lot of work. If $x = 5+9k$ then the first few possibilities are $\{5,14,23,\dots\}$ and we note that $23\equiv 3\;mod(4)$. So now we take $x=23+36k$ and seek a $k$ such that $x\equiv 10\;mod(35)$. But this works out to $23+k\equiv 10\;mod(35)$ so $k\equiv 22$. Thus $x=23+36*22=815$ works. – lulu Jan 25 '16 at 14:17
• The part "After reduction..." is incorrect. You can't reduce it that way. – user236182 Jan 25 '16 at 14:22
• Note: in your procedure, I'm not sure how you extract square roots. Knowing that $x\equiv 3\;mod(4)$ is not equivalent to $x\equiv 1\;mod(2)$ (after all $1\equiv 1\;mod(2)$ ). I think it's a mistake to focus on that method. – lulu Jan 25 '16 at 14:22

## 1 Answer

Here is how I would solve this system of equations that you showed.

\begin{align} x &\equiv 4 \pmod{6} \\ x &\equiv 13 \pmod{15} \\ x &\equiv 4 \pmod{9} \end{align}

Simplifies to

\begin{align} x \equiv 4 \pmod{6} &\implies \left\{ \begin{array}{l} x \equiv 0 \pmod{2} \\ x \equiv 1 \pmod{3} \\ \end{array} \right .\\ x \equiv 13 \pmod{15} &\implies \left\{ \begin{array}{l} x \equiv 1 \pmod{3} \\ x \equiv 3 \pmod{5} \\ \end{array} \right . \\ x \equiv 4 \pmod{9} &\implies \left\{ x \equiv 1 \pmod{3} \right . \end{align}

Note that $x \equiv 1 \pmod 3$ does not imply that $x \equiv 4 \pmod 9$. So we discard $x \equiv 1 \pmod 3$ and retain $x \equiv 4 \pmod 9$.

Removing the redundant elements, we have

$x \equiv 0 \pmod 2$
$x \equiv 3 \pmod 5$
$x \equiv 4 \pmod 9$

We work out the solution to be

\begin{array}{llll} x \equiv 0 \pmod 2 &\implies & x = 2a \\ x \equiv 3 \pmod 5 &\implies & 2a \equiv 3 \pmod 5\\ && a \equiv 4 \pmod 5\\ && a = 5b + 4 \\ && x = 10b + 8\\ x \equiv 4 \pmod 9 &\implies & 10b + 8 \equiv 4 \pmod 9\\ && b \equiv 5 \pmod 9\\ && b = 9c + 5\\ && x = 90c + 58\\ && x \equiv 58 \pmod{90}\\ \end{array}

## example 2

\begin{align} x &\equiv 18\pmod {5} \\ x &\equiv 18\pmod {16} \\ x &\equiv 58\pmod {4} \\ x &\equiv 58\pmod {25} \\ \end{align}

$x \equiv 58 \pmod 4 \iff x \equiv 2 \pmod 4$
$x \equiv 18 \pmod{16} \implies x \equiv 2 \pmod{16} \implies x \equiv 2 \pmod 4$

So we can discard $x \equiv 58 \pmod 4$ because $x \equiv 18 \pmod{16}$ implies that it is true too.

$x \equiv 18 \pmod 5 \iff x \equiv 3 \pmod 5$
$x \equiv 58 \pmod{25} \implies x \equiv 8 \pmod{25} \implies x \equiv 3 \pmod 5$

So we can discard $x \equiv 18 \pmod 5$ because $x \equiv 58 \pmod{25}$ implies that it is true too.

So we end up with \begin{align} x &\equiv 2\pmod {16} \\ x &\equiv 8\pmod {25} \\ \end{align}

So $x \equiv 2 \pmod{16} \implies x = 16a + 2$
\begin{align} x \equiv 8 \pmod{25} &\implies 16a + 2 \equiv 8 \pmod{25} \\ &\implies 16a \equiv 6 \pmod{25} &\text{Note }16 \cdot 11 \equiv 176 \equiv 1 \pmod{25} \\ &\implies 11 \cdot 16a \equiv 11 \cdot 6 \pmod{25} \\ &\implies a \equiv 16 \pmod{25} \\ &\implies a = 25b + 16 \\ &\implies x = 16(25b + 16) + 2 \\ &\implies x = 400b + 258 \\ \end{align}