Linear congruence theorem

 

정리1 Linear congruence theorem

Let $a, c, m \in \mathbb{Z}$,  $m \geq 1$,  $g = gcd(a,m)$

1. $g \!\!\! \not | c$

$\Rightarrow$  $ax \equiv c \; (\mathrm{mod} \; m)$  has no solution

 

2. $g|c$

$\Rightarrow$  $ax \equiv c \; (\mathrm{mod} \; m)$  has $g$ solutions modulo $m$

: If $x_{0}$ is a solution ( i.e. $ax_{0} \equiv c \; (\mathrm{mod} \; m)$),

then $x_{0} + \frac{m}{g}k \;\;\; (k=0,1,2, \cdots, g-1)$  are incongruent solutions modulo $m$

 

pf)

  Suppose 1 :$ax_{0} \equiv c \; (\mathrm{mod} \; m)$

  Then $ax_{0} - km = c$ for some $k \in \mathbb{Z}$

  From the Euclidean algorithm,

  $ax_{0} - km = c$ has solution $x_{0}$ (and $k$)

  iff (if and only if) $g=gcd(a,m)|c$

  Contradiction

 

  From the above observation, if $g|c$,

  then $ax \equiv c \; (\mathrm{mod} \; m)$ has a solution $x_{0}$.

  We need to show that $ax \equiv c \; (\mathrm{mod} \; m)$ has $g$ solutions.

 

  Suppose 1 : $x_{1}$ is another solution.

  Then $ax_{0} \equiv c \equiv ax_{1} \; (\mathrm{mod} \; m)$

  $\Rightarrow$ $ax_{0} \equiv ax_{1} \; (\mathrm{mod} \; m)$

  Recall that $g = gcd(a,m)$

  $\frac{a}{g}x_{0} \equiv \frac{a}{g}x_{1} \; (\mathrm{mod} \; \frac{m}{g})$

  Since $gcd( \frac{a}{g}, \frac{m}{g}) = 1$, so

$x_{0} \equiv x_{1} \; (\mathrm{mod} \; \frac{m}{g})$

  $\therefore$  $x_{1} \equiv x_{0}, \; x_{0} + \frac{m}{g}, \;  x_{0} + 2\frac{m}{g}, \; \cdots, \; x_{0} + (g-1)\frac{m}{g}$

  $\therefore$  $ax \equiv c \; (\mathrm{mod} \; m)$ has $g$ solutions.