# Thread: Linear Congruence Equation, what am I doing wrong?

1. ## Linear Congruence Equation, what am I doing wrong?

What Am I doing wrong?

Find x and y which solve both congruence equations simultaneously.

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

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

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

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

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

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

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

But plugging back x and y into the congruences, for example: $\displaystyle (85)-3(-4)\not\equiv 9 \bmod{12}$

2. Nevermind, I answered my own question.

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

3. Originally Posted by Pn0yS0ld13r
$\displaystyle x-3y\equiv 9 \bmod{12}$
$\displaystyle x+10\equiv 5 \bmod{12}$
I think you mean,
$\displaystyle x-3y \equiv 9 ~ (12)$
$\displaystyle x+10y\equiv 5 ~ (12)$