Prime that divides $a^2-1$ but not $a-1$

Question

I saw in our book that for any integer bigger than $1$, say integer $a$ there is a prime $p$, such that $p$ divides $a^2-1$ but not $a-1$ or otherwise $a$ is one smaller than power of two.

Why is that true?

Answer 1

Since $a^2-1=(a-1)(a+1)$, we know that any prime $p$ that divides $a^2-1$ divides either $a-1$ or $a+1$ or both. So we are interested in primes $p$ that divide $a+1$ but do not divide $a-1$.

For any positive integers $m$ and $n$ with $m>n$ we know that any common factor of $m$ and $n$ is also a factor of $m-n$. But if $m=a+1$ and $n=a-1$ then $m-n=2$, so either $\gcd(a+1,a-1)=1$ i.e. $a+1$ and $a-1$ are coprime or $\gcd(a+1,a-1)=2$.

Now consider these two case separately:

• If $a+1$ and $a-1$ are coprime then ...
• If $\gcd(a+1, a-1) = 2$ then ...