Linear Congruence Equation, what am I doing wrong?

**Pn0yS0ld13r** · July 20th 2008, 07:11 PM

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

**Pn0yS0ld13r** · July 20th 2008, 08:14 PM

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$