Using modular arithmetic show that in $<ℤ_p, +, *> , a = a^{-1}$ if and only if $a ∈ {1, p-1}$.

62 Views Asked by At

(a) Show that in $<ℤ_p, +, *> , a = a^{-1}$ if and only if $a \in \{1, p-1\}$.

(b) Using (a), prove that for any prime p, we have $(p - 2)! = 1 \ $ mod $ \ p$.

(c) Let p be a prime number greater than five. Prove that

$\underbrace{111...1}_{p-1 \ \text{ digits}}=0! \ $ mod $\ p$

1

There are 1 best solutions below

0
On

For part (a) observe the following chain of biconditionals.

$a=a^{-1}\iff a^2\equiv 1\mod p\ \iff a^2-1\equiv0\mod p\ \iff (a-1)(a+1)\equiv 0\mod p\ \iff a-1\equiv0\mod p\ \text{or}\ a+1\equiv 0\mod p\ \iff a\in\{1,p-1\}$

Let $p$ be a prime. Then $\mathbf{Z}_p$ is a field and therefore each member of $\mathbf{Z}_p$ is invertible. By part (a) we know that $1$ is its own inverse and $p-1$ is its own inverse. And $1,p-1$ are the only such members of $\mathbf{Z}_p$. So for any $a\in \{2,3,\cdots,p-2\}$ there is $b\in \{2,3,\cdots,p-2\}\setminus \{a\}$ such that $ab=1$. Hence the product $2\times3\times\cdots\times (p-2)\equiv 1\mod p$ or rather $(p-2)!\equiv 1\mod p$.