Definition

Let $f(x_1,x_2,...,x_n)$ be a polynomial in n variables with integer coefficients and $f(x_1,x_2,...,x_n)\equiv 0(m)$. A solution is that $f(a_1,a_2,...,a_n)\equiv 0(m)$. Thus $\bar f(\bar a_1, \bar a_2,....,\bar a_n)=\bar 0$.

Proposition 1

For $ax\equiv b(m)$, consider $d > 0$ and $(a,m)=d$. $ax\equiv b(m)$ has solutions and have exactly d solutions iff $d|b$.

For a solution $x_0$, then there are other solutions given by $x_0 + m', x_0+2m', x_0+(d-1)m'$, where $m'=m/d$.

Proof:

If $d|b$, we shall have $ax'-my'=d$. So we have $my'=d-ax'$, times $b/d$ on both side we have $my'b/d=b-ax'b/d$. Now we have a solution $x=x'b/d$.

If $x_0$ is a solution, we have $my_0=b-ax_0$. Thus $b=my_0-ax_0$. That is $b\in(a,m) \implies d|b$.

If $x_0,x_1$ are two solutions, $ax_0\equiv b(m)$, $ax_1\equiv b(m)$. Therefore, $a(x_0-x_1)\equiv 0(m) \implies m|a(x_0-x_1)$.

By dividing $d$, we have $m'|a'(x_0-x_1)$. And as we know, $(m',a')=1$. So $m'|(x_0-x_1)$.

Now we can have a linear combination: $x_1=x_0+km'$ where $k\in\Z$.

Corollary 1

If $(a,m)=1$, then $ax\equiv b(m)$ has one and only solution.

Proof:

Clearly, the number of solution is $(a,m)=1$.

Corollary 2

If p is prime and $a \not\equiv 0(p)$ , there is one and only solution for $ax\equiv b(p)$.

Proof:

$(a,p)=1$.

Unit

Proposition 2

As previously discussed, $ax\equiv b(m)$ is equivalent to $\bar a x=\bar b$ over $\Z/m\Z$.

So we can define a unit $\bar a$ iff $\bar ax=\bar1$, that is $ax\equiv 1(m)$ is solvable. Thus iff $(a,m)=1$, $\bar a$ is a unit.

It follows there are $\phi(m)$ units in $\Z/m\Z$​.

So in $\Z/p\Z$, every nonzero element is a unit, that makes it a field.

But for a composition number $m=m_1m_2$. We have $\bar m_1 \ne \bar 0, \bar m_2 \ne \bar 0$ , however, $\overline{m_1m_2}=\bar m = \bar 0$. So $\Z/m\Z$ is not a field.

Corollary 2 (Euler's Theorem)

If $(a,m)=1$, then $a^{\phi(m)}\equiv 1 (m)$

Proof:

Since $(a,m)=1$, $\bar a$ is a unit. So $\bar a ^{\phi(m)}=\bar 1$.

Corollary 3 (Fermat's Little Theorem)

If p is prime and $p \nmid a$, then $a^{p-1}\equiv 1(p)$.

Proof:

Since $(a,p)=1$, $a^{\phi(p)}\equiv 1 (p)$. Thus $\phi(p)=p-1$.