Sunday, 29 September 2013

systems of modulo equations not relatively prime

systems of modulo equations not relatively prime

How would I go about finding a solution to the following system?
$x\equiv 1\text{ mod }12\ \ \ \ \ \ \text{(1)}\\x\equiv4\text{ mod }21\ \
\ \ \ \ \text{(2)}\\x\equiv18\text{ mod } 35\ \ \ \ \text{(3)}$
It is a problem because $\gcd(12,21,35)\neq1$.
I can solve the system without (3) as follows I think:
Write $(1)$ as $x\equiv 1\mod4,x\equiv1\mod3$, then $(2)$ reduces to
$x\equiv 1\mod3, x\equiv4\mod21$, thus we can solve:
$x\equiv 1\mod12\\x\equiv4\mod7$
and using Euler's algorithm we find $x\equiv25\mod84$. So we now want to
solve:
$x\equiv25\mod84\ \ \ \ \ \ \text{(4)} \\ x\equiv18\mod35\ \ \ \ \ \
\text{(5)}$
But now the same trick won't work, since converting $(5)$ to
$x\equiv3\mod5,x\equiv6\mod7$ gives a problem in $(4)$, since 25 is not
divisible by $6$. This would suggest the system has no solutions, but it
does, since for example $193$ is a solution.
What did I do wrong?

No comments:

Post a Comment