To find all positive integers $n$ such that $n|a^2-1 ; a \in \mathbb Z \implies n|a-1 $ , or $n|a+1$

Question

How do we find all positive integers $n$ such that $n|a^2-1 ; a \in \mathbb Z \implies n|a-1 $ , or $n|a+1$ ? I have found that for any odd prime $p$ and $n \in \mathbb Z^+$ , $p^n|a^2-1 ; a \in \mathbb Z \implies p^n|a-1 $ , or $p^n|a+1$ and that $2|a^2-1 \implies 2|a-1$ , or $2|a+1$ are these all the possible $n$ ?

Answer 1

Hint: Let $n\gt 1$ be odd and not a prime power. Then there exist relatively prime integers $k\gt 1$ and $l\gt 1$ such that that $n=kl$.

By the Chinese Remainder Theorem the system of congruences $x\equiv 1\pmod{k}$, $x\equiv -1\pmod{l}$ has a solution.

If $a$ is a solution, then $a^2\equiv 1\pmod{n}$, but $a\not\equiv 1\pmod{n}$ and $a\not\equiv -1\pmod{n}$.

Remark: In conjunction with the work you have already done, it only remains to deal with even $n$. A similar idea will work, except when $n$ is $2$, $4$, or of the form $2p^e$ for an odd prime $p$. If you have already seen primitive roots, the pattern will be familiar.