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