Special Features of Z_p

In the last section in Chapter 2, we will see ${\mathbb{Z}}_p$ has some special features makes it different from ${\mathbb{Z}}_n$ for $n$ composite.

Let’s begin by analyzing ${\mathbb{Z}}_5$ and ${\mathbb{Z}}_6$.

Concrete Examples

We have mentioned that elements in ${\mathbb{Z}}_n$ will be periodic. Now let’s try to list the minimal period of each element in ${\mathbb{Z}}_5$ and ${\mathbb{Z}}_6$.

${\mathbb{Z}}_5$

We have the following table:

$[a]$	Period
$[0]$	1
$[1]$	5
$[2]$	5
$[3]$	5
$[4]$	5

Well, we explain the table by explaining the meaning of the last row:

$$\begin{array}{rl}[4]& \ne [0]\\ [4]+[4]& =[8]=[3]\ne [0]\\ [4]+[4]+[4]& =[12]=[2]\ne [0]\\ [4]+[4]+[4]+[4]& =[16]=[1]\ne [0]\\ [4]+[4]+[4]+[4]+[4]& =[20]=[0]\end{array}$$

so the period of $[4]$ is 5.

Now as we can observed in the table, every non-zero element has the same period 5, this is a special feature of ${\mathbb{Z}}_p$.

We can compute the products of two non-zero elements in ${\mathbb{Z}}_5$ and we list the results as a table:

	$[1]$	$[2]$	$[3]$	$[4]$
$[1]$	$[1]$	$[2]$	$[3]$	$[4]$
$[2]$	$[2]$	$[4]$	$[1]$	$[3]$
$[3]$	$[3]$	$[1]$	$[4]$	$[2]$
$[4]$	$[4]$	$[3]$	$[2]$	$[1]$

We notice we cannot get $[0]$ by multiplying two non-zero elements. For any $[a]\ne [0]$, we have can find a $[b]$ such that $[a]\cdot [b]=[1]$. This is also a special feature of ${\mathbb{Z}}_p$.

${\mathbb{Z}}_6$

We have the following table:

$[a]$	Period
$[0]$	1
$[1]$	6
$[2]$	3
$[3]$	2
$[4]$	3
$[5]$	6

The table can be explained similarly. We notice elements in ${\mathbb{Z}}_6$ have different periods.

Now we list the products of two non-zero elements in ${\mathbb{Z}}_6$:

	$[1]$	$[2]$	$[3]$	$[4]$	$[5]$
$[1]$	$[1]$	$[2]$	$[3]$	$[4]$	$[5]$
$[2]$	$[2]$	$[4]$	$[0]$	$[2]$	$[4]$
$[3]$	$[3]$	$[0]$	$[3]$	$[0]$	$[3]$
$[4]$	$[4]$	$[2]$	$[0]$	$[4]$	$[2]$
$[5]$	$[5]$	$[4]$	$[3]$	$[2]$	$[1]$

We notice that $[2]\cdot [3]=[0]$, so the product of two non-zero elements can be zero in ${\mathbb{Z}}_6$. This does not happen in ${\mathbb{Z}}_5$.

Also, we notice that for $[2]\ne [0]$, we cannot find a $[x]$ such that $[2]\cdot [x]=[1]$.

Special Features for ${\mathbb{Z}}_p$

Our observations can be generalized as the following:

Theorem

If $p>1$ is an integer, then the following statements are equivalent:

1. $p$ is prime.
2. For any $[a]\in {\mathbb{Z}}_p$ and $[a]\ne [0]$, there exists a $[x]\in {\mathbb{Z}}_p$ such that $[a]\cdot [x]=[1]$.
3. Whenever $[a]\cdot [b]=[0]$ in ${\mathbb{Z}}_p$, then $[a]=[0]$ or $[b]=[0]$.
4. For any $[a]\in {\mathbb{Z}}_p$ and $[a]\ne [0]$, the minimal period of $[a]$ is $p$.

To prove the theorem, we will show:

$$1\Rightarrow 2\Rightarrow 3\Rightarrow 4\Rightarrow 1.$$

Proof of $1\Rightarrow 2$

Assume $p$ is prime. Let $[a]\in {\mathbb{Z}}_p$ with $[a]\ne [0]$. By property of congruence classes, we know $a-0=a$ is not divisible by $p$. Since $p$ is prime, by this property of prime numbers, we have $\gcd (p,a)=1$. Then we can find integers $x,y$ such that $ax+py=1$. We can take the congruent classes of the equation, and we have $[a]\cdot [x]=[1]$.

Proof of $2\Rightarrow 3$

Assume $[a]\cdot [b]=[0]$ and assume $[a]\ne [0]$, then we can find a $[x]$ such that $[a]\cdot [x]=[1]$. Then we have:

$$[a]\cdot [b]=[0]\Rightarrow [x]\cdot [a]\cdot [b]=[x]\cdot [0]\Rightarrow [b]=[0].$$

Proof of $3\Rightarrow 4$

Let $[a]\in {\mathbb{Z}}_p$ and $[a]\ne [0]$. Assume the period of $[a]$ is $0<q\ne p$. Then we have:

$$[a]+[a]+\cdots +[a]=[a]\cdot [q]=[0]\Rightarrow [q]=[0],$$

this implies $p\mid q$. Now we know $[a]\cdot [p]=[0]$, so the minimal period of $[a]$ is $p$.

Proof of $4\Rightarrow 1$

Assume $p$ is not prime. Then we can find $a,b$ such that $p=ab$. Then we have:

$$[a]\cdot [b]=[0],$$

so the minimal period of $[a]$ is less than $b$ so is not $p$. This is a contradiction.

Solving Linear Equations in ${\mathbb{Z}}_n$

As alluded in the theorem, we can solve equations in ${\mathbb{Z}}_p$ by finding the multiplicative inverse, we would state this as a proposition:

Proposition

Let $p$ be a prime number, and let $[a],[b]\in {\mathbb{Z}}_p$. If $[a]\ne [0]$, then the equation $[a]\cdot [x]=[b]$ has a unique solution $[x]$.

Proof of Proposition

We have shown in the theorem that $[a]$ has a multiplicative inverse, so we can find a $[a^{\prime }]$ such that $[a]\cdot [a^{\prime }]=[1]$. Then we have:

$$[a]\cdot [x]=[b]\Rightarrow [a^{\prime }]\cdot [a]\cdot [x]=[a^{\prime }]\cdot [b]\Rightarrow [x]=[a^{\prime }]\cdot [b]=[a^{\prime }\cdot b].$$

By examining the table for ${\mathbb{Z}}_6$, we can see not every linear equation has a solution, for example:

$$[2]\cdot [x]=[1].$$

This equation has no solution in ${\mathbb{Z}}_6$.

We actually know when exactly the equation has a unique solution, we would state this as a proposition:

Proposition

Let $n>1$, and let $[a],[b]\in {\mathbb{Z}}_n$. If $\gcd (a,n)=1$, then the equation $[a]\cdot [x]=[b]$ has a unique solution $[x]$.

Proof of Proposition

We first shown there is a solution. Since $\gcd (a,n)=1$, we can find integers $m,n$ such that $am+bn=1$, multiplying the equation by $b$ we have:

$$a(mb)+b(nb)=b\Rightarrow [a]\cdot [mb]=[b].$$

Now we know there is a solution [mb]. Next we show the solution is unique. Assume there are two solutions $[x]$ and $[y]$, and let $m,n$ be the integers such that $am+bn=1$. Then we have:

$$[a]\cdot [x]=[a]\cdot [y]\Rightarrow [m]\cdot [a]\cdot [x]=[m]\cdot [a]\cdot [y]\Rightarrow [x]=[y].$$

In the homework, you will be investigating the solutions of linear equations in ${\mathbb{Z}}_n$ without demanding $\gcd (a,n)=1$.

We list a concrete example in the next subsection to illustrate the possible solution behaviors of linear equations in ${\mathbb{Z}}_n$.

Concrete Examples of Solving Linear Equations in ${\mathbb{Z}}_{12}$

Solve the following equations in ${\mathbb{Z}}_{12}$:

1. $[3]\cdot [x]=[9]$.
2. $[5]\cdot [x]=[7]$.
3. $[4]\cdot [x]=[6]$.

Solution of 1.

We notice $\gcd (3,12)=3\ne 1$, but $\gcd (3,12)=3\mid 9$, so the equation has a solution. We rewrite the equation as:

$$[3]\cdot ([x]-[3])=[0]$$

Now we first solve $[3]\cdot [y]=[0]$, this amounts to find the minimal period of $[3]$ which is $4$. So we have $[y]=[4k]$ for some $k$, since every time we have $4$ copies of $[3]$ we get $[0]$. Then we know:

$$[x]=[3]+[y]=[3]+[4k]=[3+4k].$$

We can enumerate the different solutions in to distinguished elements in ${\mathbb{Z}}_{12}$:

$$[x]==[3],[7],[11].$$

Solution of 2.

We notice $\gcd (5,12)=1$, so the equation has a unique solution. We can find the multiplicative inverse of $[5]$ which is $[5{]}^{-1}=[5]$, since $[5]\cdot [5]=[1]$. Then we have:

$$[x]=[5][5][x]=[5]\cdot [7]=[35]=[11].$$

Solution of 3.

We notice $\gcd (4,12)=4\ne 1$, but $\gcd (4,12)=4\nmid 6$, so the equation has no solution, but we need to prove it, below is the proof:

Assume there is a solution $[x]$, then for some $k\in \mathbb{Z}$ we have:

$$4x-6=12k\Rightarrow 6=4x-12k\Rightarrow 4\mid 6.$$

This is a contradiction, so the equation has no solution.