Show that for every $n$ there is a prime $p$ such that

Question

Show that for every $n$ either there is a prime $p$ such that $p$ divides $n^2-1$ but not $n-1$, or $n$ is of the form $2^k-1$.

If there is a prime $p$ which divides $n^2-1$ then it divides $(n + 1)(n - 1)$. It cannot divide both of the factors so it divides either of them... the rest I cannot figure out. Can someone help?

Answer 1

We're told that for any natural number $n$, at least one of the following two statements is true:

1. There is a prime $p$ which divides $n^2-1$ but not $n-1$
2. There is a natural number $k$ such that $n = 2^k-1$

Now, let's take each of those two statements and massage them a bit. Hopefully, by the time we're through, it will be clear that for any natural number at least one of them must be true.

By the factoring $n^2-1 = (n+1)(n-1)$ and Euclid's lemma, statement 1. can be rephrased into "There is a prime $p$ which divides $n+1$ but not $n-1$". If there is such a prime, then clearly it must be odd. On the other hand, if $n+1$ has an odd prime factor $p$, then we also must have $p\nmid n-1$. Thus we can finally rewrite 1. into

1'. $n+1$ has an odd prime factor

Statement 2. can quite easily be reprased into

2'. There is a natural number $k$ such that $n+1 = 2^k$

Now can you see that for any natural number $n$, at least one of the two statements 1'. and 2'. is true?

Answer 2

If $n$ is not of the form $2^k-1$, then let $p$ be a prime factor of $n+1$ such that $p>2$. There has to be such a prime factor, since $n+1$ is not a power of $2$. Of course, $p\nmid n-1$, since$$p\mid n-1\wedge p\mid n+1\implies p\mid2.$$