3
$\begingroup$

I'm trying to prove that $\mathbb Z_p^*$ ($p$ prime) is a group using the Fermat's little theorem to show that every element is invertible.

Thus using the Fermat's little theorem, for each $a\in Z_p^*$, we have $a^{p-1}\equiv1$ (mod p). The problem is to prove that p-1 is the least positive integer which $a^{p-1}\equiv1$ (mod p).

Remark: $\mathbb Z_p^*$ is $\{\overline 1,...,\overline {p-1}\}$ with multiplication.

I need help.

Thanks a lot.

$\endgroup$
  • 3
    $\begingroup$ Why should it be the least positive integer? You have just proved that $\overline{x}^{-1}=\overline{x}^{p-2}$, which gives the inverse. $\endgroup$ – egreg Apr 20 '13 at 9:59
  • $\begingroup$ As far as I know, this notation is for the group of units of the ring $\mathbb{Z}_p$. So it is a group. But it turns out that $\mathbb{Z}_p^*=\{a\in\mathbb{Z}_p\;;\; a\neq 0\}$. That is: $\mathbb{Z}_p$ is a field. And that is what you are trying to prove: every nonzero element is invertible. $\endgroup$ – Julien Apr 20 '13 at 10:00
  • $\begingroup$ @egreg yes, you're right, I didn't think in this way. Thank you very much $\endgroup$ – user42912 Apr 20 '13 at 10:04
  • $\begingroup$ @julien yes, I know, thank you $\endgroup$ – user42912 Apr 20 '13 at 10:04
6
$\begingroup$

You can't show that $p-1$ is the least positive integer $r$ such that $a^r\equiv 1\pmod{p}$, because in general it isn't: for instance, the least integer for $a=1$ is $1$.

But all you need is to find an element which acts as an inverse:

$$a\cdot a^{p-2} \equiv 1 \pmod{p}$$

so that, for any $\overline{x}\in\mathbb{Z}^*_p$ you have

$$\overline{x}\cdot\overline{x}^{\,p-2} = \overline{1}$$

and so

$$\overline{x}^{\,-1}=\overline{x}^{\,p-2}$$

$\endgroup$
  • $\begingroup$ I have a question. How can we know that $\overline{x}^{\,-1}=\overline{x}^{\,p-2} \in \mathbb{Z}_{p}^{*}$? Thanks for your answer. $\endgroup$ – OpiRabbit Sep 14 '13 at 21:21
  • $\begingroup$ @nameless $\mathbb{Z}^*_p$ is a group (with respect to multiplication) and has $p-1$ elements. If a group $G$ has $n$ elements, then $g^n=1$ for any $g\in G$ and therefore $g^{-1}=g^{n-1}$. $\endgroup$ – egreg Sep 14 '13 at 21:25
  • $\begingroup$ Yes. Now, we want to show $(\mathbb{Z}_{p}^{*}, \cdot)$ is a group. For show it has an inverse, we find $\overline{x}^{p-2}$ such that $\overline{x}\cdot\overline{x}^{\,p-2} = \overline{1}$. But we need to show that $\overline{x}^{p-2}$ lies in $\mathbb{Z}_{p}^{*}$ ? $\endgroup$ – OpiRabbit Sep 14 '13 at 21:30
1
$\begingroup$

Please check my inverse solution.

Let $\overline{x} \in \mathbb{Z}_{p}^*$. Then $(x,p)=1$, that is there exist $k, q \in \mathbb{Z}$ such that $kx + qp=1$. This implies $\overline{k}\overline{x}=\overline{1}$. Suppose that $\overline{k}=\overline{0}$. Then $\overline{0}=\overline{1}$, a contradict. Thus $\overline{k} \not = \overline{0}$, so $k \not = 0$.

Now, we write $k=mp+r$ where $0 \leq r < p$. If $k<p$, then $(k,p)=1$. It follows that $\overline{k} \in \mathbb{Z}_{p}^*$. If $k=p$, then $r=0$. It follows that $\overline{k}=\overline{0}$, a contradict, thus $k \not = p$. If $k>p$, then we have $k=mp+r$ where $0 < r < p$. Hence $\overline{r} \in \mathbb{Z}_p^*$. Since $k \equiv r \, (\mod p)$, $\overline{k} \in \mathbb{Z}_p^*$.

Therefore $\mathbb{Z}_p^*$ has inverse.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.