# Linear Congruence Equation, what am I doing wrong?

• Jul 20th 2008, 08:11 PM
Pn0yS0ld13r
Linear Congruence Equation, what am I doing wrong?
What Am I doing wrong?

Find x and y which solve both congruence equations simultaneously.

$x-3y\equiv 9 \bmod{12}$
$x+10y\equiv 5 \bmod{12}$

$cx+ey\equiv a \bmod{n}$
$dx+fy\equiv b \bmod{n}$

So $a=9, b=5, c=1, d=1, e=-3, f=10, n=12$.

There is number $z$ such that $(cf-de)z\equiv 1 \bmod{n}$

So $13z \equiv 1 \bmod{12}$, thus $z=1$ (right?)

$x \equiv z(af-be) \bmod{n}$
$y \equiv z(bc-ad) \bmod{n}$

So $x \equiv 1(85) \bmod{12}$ and $y \equiv 1(-4) \bmod{12}$

But plugging back x and y into the congruences, for example: $(85)-3(-4)\not\equiv 9 \bmod{12}$
• Jul 20th 2008, 09:14 PM
Pn0yS0ld13r
Nevermind, I answered my own question.

Subtracting the congruences, $13y \equiv -4 \bmod{12}$.
Since $13 \equiv 1 \bmod 12$ and $-4 \equiv 8 \bmod 12$, $y=8$. Plugging y in any of the congruences yields $x = 9$

$x-3y\equiv 9 \bmod{12}$
$x+10\equiv 5 \bmod{12}$
$x-3y \equiv 9 ~ (12)$
$x+10y\equiv 5 ~ (12)$