5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Clayton Jun 28 '18 at 3:23
1
$\begingroup$

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).

$\endgroup$
0
$\begingroup$

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$.

$\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.