1
$\begingroup$

I have never really directly dealt with congruences until I was introduced to the Chinese Remainder Theorem. Although there are tons of different versions of this theorem out there, currently I am more interested in solving congruences. I had some questions regarding steps that were used in solving the following congruent linear equation for $X_1$.

$99X_1\equiv1\pmod8$

Subtracting 96(which is a factor of 8 from both side)

$3X_1\equiv1\pmod 8$ (Subtracting any factor of 8 on R.H.S is like subtracting $0$. So R.H.S remains unchanged)

Adding 8 gives:

$3X_1\equiv(1+8) \pmod8$

$3X_1\equiv9\pmod8$ so $X_1=3$

Now when 8 was added why was it only added to the R.H.S . I thought any factor of 8 whether being subtracted (or added?) on R.H.S is like subtracting or adding $0$ ?

  • 0
    Use `\pmod{a}` to get $\pmod{a}$.2012-07-21

1 Answers 1

4

Precisely because adding $8$ modulo $8$ is the same as adding $0$, you can add $8$ to only one side and not change the congruence (just like you can add $0$ to only one side of $x=y$ to get $x=y+0$ and not change the equality).

Alternatively, since $0\equiv 8\pmod{8}$, you are adding the congruence $3x_1\equiv 1\pmod{8}$ to the congruence $0\equiv 8\pmod{8}$ to get $3x_1+0 \equiv 1+8\pmod{8}.$ This is like adding $x=a$ to $y=b$ in order to get $x+y=a+b$.

  • 0
    Thanks for clearing that up2012-07-21