$ax \equiv b \; (\mathrm{mod} \; p)$

 

정리1

Let $p$ be a prime  and $a \not \equiv 0 \; (\mathrm{mod} \; p)$.

Then $ax \equiv b \; (\mathrm{mod} \; p)$ has a unique solution modulo $p$

 

  Show 1 : $ax \equiv b \; (\mathrm{mod} \; p)$ has a solution

  Since $gcd(a,p)=1$, by Euclidean algorithm there exists $x_{0}, y_{0} \in \mathbb{Z}$  s.t.  $ax_{0} + py_{0} =1$

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

  $\Rightarrow$ $a(bx_{0}) \equiv b \; (\mathrm{mod} \; p)$

 

  Show 2 : $bx_{0}$ is a unique solution modulo $p$

  Suppose $ax_{1} \equiv b \; (\mathrm{mod} \; p)$  and  $ax_{2} \equiv b \; (\mathrm{mod} \; p)$

  $\Rightarrow$ $ax_{1} \equiv ax_{2} \; (\mathrm{mod} \; p)$

 

  Since $gcd(a,p)=1$,

  so $x_{1} \equiv x_{2} \; (\mathrm{mod} \; p)$

  $\therefore$  There's only one solution $x \equiv bx_{0} \; (\mathrm{mod} \; p)$