# Problem on modular arithmetic

I can't quite figure out how to title this question, but since this isn't quite a proof, I'm not sure if there's a better way to title this.

This is a problem from Norman Bigg's Discrete Mathematics textbook that I can't manage to figure out.

"Show that the equation $x = x^{-1}$ in $\mathbb{Z}_p$ implies that $x^2 - 1 = 0$, and deduce that $1$ and $-1$ are the only elements of $\mathbb{Z}_p$ that are equal to their own inverse."

First, $\mathbb{Z}_p$ elsewhere in the text refers to the integers modulo (some prime), though the author always took care to specify that $p$ was a prime, though that isn't the case here. This is throwing me off quite a bit, as I just worked out another example in $\mathbb{Z}_8$ where $5$ was its own inverse (as $5 \cdot 5 = 25 \equiv 1 \ \text{(mod$8$)}$. So, this doesn't hold with $p = 8$, so it seems that it must be the case that there are some restrictions on $p$, most likely that it is prime. (If I'm wrong on this, and this could apply to any $p \in \mathbb{N}$, please let me know.)

From here, I can't quite seem to string together these equations. I've been able to piece together, from our assumptions, these facts:

(a) $xx^{-1} \equiv 1 \ \text{(mod$p$)}$ since $x$ and $x^{-1}$ are inverses.

(b) $x^2 \equiv 1 \ \text{(mod$p$)}$ since $x = x^{-1}$ by assumption.

(c) By the definition of modulus, $x^2 - 1$ is a multiple of $p$, so $\exists$ some $m \in \mathbb{N}$ such that $x^2 - 1 = mp$.

(d) We need to somehow deduce that $mp$ must equal $0$. The only possible way I could think to do this is to assume that $p$ is prime and conclude that $x^2 -1$ clearly cannot be prime as it's a difference of squares. But, even then, it could certainly be a multiple of a prime, if I'm not mistaken. This doesn't seem to make much sense.

From here, it seems to me that the second part of the problem would follow. If equality in $\mathbb{Z}_p$ implies $x^2 - 1 = 0$, and we can factor the left-hand side, a difference of squares, into $(x+1)(x-1)$, then clearly $x = 1$ or $x = -1$. Assuming this is correct--please tell me if it isn't--the only real issue seems to be deducing that $x^2 - 1 = 0$.

Any helpful thoughts and hints would be very appreciated.

• Your ideas are all right. The phrasing is a little unclear, but you’re correct to say $p$ is prime. Further, you only need $x^2-1\equiv0\pmod p$. This gives $x\equiv\pm1$. – Clayton Jun 28 '18 at 3:23

You reasoning is on the right track. Since $(x-1)(x+1) = x^2 -1 \equiv 0 \pmod{p}$, $p$ divides $(x-1)(x+1)$ and since $p$ is prime (as you noted, otherwise the result can be false), either $p | (x+1)$ or $p|(x-1)$, that is, either $x \equiv 1 \pmod{p}$ or $x \equiv -1 \pmod{p}$.
If you've taken $x$ to be on $\{-1,\dots,p-2\}$, then from here you can conclude that $x^2 -1 = 0$ since $x = 1$ or $x = -1$. If not, that's not necessarily true. For example, by the above calculation $p+1$ verifies $(p+1)^2-1 \equiv 0 \pmod{p}$ but $(p+1)^2 -1 \neq 0$ as integers.
As a side note, $[x] \in \mathbb{Z}_n$ has an inverse if and only if $x$ is coprime with $n$. To talk about inverses in a general setting, one must first assure their existence. One way of doing that is taking $n$ prime, so that any non zero element has an inverse (in other words, $\mathbb{Z}_p$ is a field if $p$ prime).
The hypothesis $p$ is prime is necessary in general, because in order to conclude, you need to know that $\mathbb{Z}/p\mathbb{Z}$ (or $\mathbb{Z}_p$ with your notation) is an integral domain (ie satisfies "$ab=0\Rightarrow a=0$ or $b=0$ for every $a$, $b$"). This happens if and only if $p$ is prime (and in this case, $\mathbb{Z}/p\mathbb{Z}$ is even a field).
Then, as you stated at the end of your question, the correct way to conclude is to factorize $x^2-1$ as $(x-1)(x+1)$ in $\mathbb{Z}/p\mathbb{Z}$, and use integrity to conclude that either $x=1$ or $x=-1$ in $\mathbb{Z}/p\mathbb{Z}$ (note that if $p=2$, these two solutions are the same since $1=-1$).
NB: The difference of two squares may be a prime. For instance, $9-4=5$.