Finding the elements in the group of units of the ring of integers modulo n that are their own inverse. Let $n > 1$ be any positive integer and consider $(\mathbb{Z}/n)^\times$. We want to find all elements $x \in (\mathbb{Z}/n)^\times$ such that $x \equiv x^{-1} \mod n$.
After testing a few different $n$, I am certain that the only elements will be $1$ and $n - 1$. This is certainly true when $n$ is prime. Showing it when $n$ is composite is more difficult:
Assume that $x \equiv x^{-1} \mod n$. Then $x^2 \equiv 1 \mod n$ and so $x^2 - 1 \equiv 0 \mod n$, which implies that $(x - 1)(x + 1) \equiv 0 \mod n$. Now if $n$ is prime, we could just conclude that $n | (x - 1)$ or $n | (x + 1)$. But I am unsure what to do in the case that $n$ is composite.
 A: We sketch the full theory. There will be some detail for you to fill in. We use classical number-theoretic language. The translation to more algebraic language is straightforward. 
Suppose that $n$ has the prime power factorization $p_0^{a_0} p_1^{a_1} \cdots p_k^{a_k}$, where $p_0=2$ and the other $p_i$ are distinct odd primes. 
If $u^2\equiv 1\pmod{n}$, then $u^2\equiv 1\pmod{p_i^{a_i}}$ for $0\le i\le k$. 
Conversely, if $u_0,u_1,\dots, u_k$ are units modulo the prime powers, then by solving the system of congruences $x\equiv u_i\pmod{p_i^{a_i}}$ (Chinese Remainder Theorem) we obtain a unit modulo $n$ such that $u^2\equiv 1$.
So we need only deal with powers of odd primes, and powers of $2$.
For powers of odd primes, there are only the $2$ obvious solutions to $u_i^2\equiv 1\pmod{p_i^{a_i}}$.  This is easily proved by using the fact that $p_i^{a_i}$ divides $x^2-1$ if and only if $it divides one of $x-1$ or $x+1$. 
The prime $2$ is special. For $2^1$ there is $1$ solution, for $2^2$ there are $2$.  If $s\ge 3$, there are $4$ solutions modulo $2^s$. They are $u\equiv \pm 1\pmod{2^s}$ and $u\equiv 2^{s-1}\pm 1\pmod{2^s}$. 
The total number of solutions of the congruence $x^2\equiv 1\pmod{n}$  is $2^k$ if $a_0=0$ or $1$, $2^{k+1}$ if $a_0=2$, and $2^{k+2}$ if $a_0\ge 3$. In particular, the number can be very large if $n$ has a large number of distinct prime factors. 
