0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – lulu Jan 25 '16 at 14:17
  • $\begingroup$ The part "After reduction..." is incorrect. You can't reduce it that way. $\endgroup$ – user236182 Jan 25 '16 at 14:22
  • $\begingroup$ 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. $\endgroup$ – lulu Jan 25 '16 at 14:22
1
$\begingroup$

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}

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.