IMO SL N$4$ $2001$: Let $p \geq 5$ be a prime number. Prove that there exists an integer $a$ with $1 \leq a \leq p-2$ such that neither $a^{p-1}-1$ nor $(a+1)^{p-1}-1$ is divisible by $p^2$.
My proof: Suppose there did not exist such an $a$. Then we have $p^2$|$a^{p-1}-1$, $p^2$|$(a+1)^{p-1}-1$. But note that this condition is equivalent to saying that $p$|$a^{p-1}-1$ and $p$|$(a+1)^{p-1}-1$ respectively. So we then have $a^{p-1}-1$=$(a+1)^{p-1}-1$(mod $p$). But by Fermat's little theorem, this is equivalent to saying that $0$=$1$(mod $p$). A contradiction. So there must exist such an $a$.
I then read the other proofs to this problem, but they were far more intricate and complicated, hinting that my proof is incorrect. For instance, one proof I found was:
It's well-known that $P(x)=x^{p-1}-1$ has $p-1$ roots in $\mathbb Z_{p^2}$. Assume what we're trying to prove doesn't hold. In each pair $(1,2),(3,4),\ldots,(p-2,p-1)$ there's at least a root of $P$, so there are at least $\frac{p-1}2$ roots of $P$ among the first $p$ residues $\pmod{p^2}$. If $x$ is a root of $P$, then so is $-x$ (in $\mathbb Z_{p^2}$, of course), so there are at least $\frac{p-1}2$ other roots of $P$ among the last $p$ residues $\pmod{p^2}$. This means that the roots of $P$ lie in the intervals $(1,p)$ and $(p^2-p,p^2)$. However, we can clearly find roots which are not in these intervals, for example the product of two roots chosen from the pairs $(\frac{p-3}2,\frac{p-1}2),(\frac{p+1}2,\frac{p+3}2)$. Their product is $\ge \frac{(p-3)(p+1)}4$ and $\le \frac{(p-1)(p+3)}4$. For $p\ge 7$ this product is outside the two intervals mentioned above, and for $p=5$ we can check it manually (take $a=1$).
This proof uses for instance special polynomials, and lemmas, while my proof seems too elementary. I am trying to find fault with my proof, but everything seems to line up. Maybe something is off with the heuristics.
So my question is; is there something wrong with my proof? If yes, how should, or what should I do next time to make this not happen again, or to prevent it?
Your proof by contradiction should start from the negation of the claim, which is:
Here the 'or' is not exclusive. You have started by assuming instead that $$a^{p-1}-1\equiv0\pmod{p^2}\qquad\textbf{ and }\qquad (a+1)^{p+1}-1\equiv0\pmod{p^2},$$ for some $a$, or all $a$, it is not clear which of the two.
Also, Fermat's little theorem tells you that $$a^{p-1}-1\equiv(a+1)^{p-1}-1\equiv0\pmod{p},$$ because $p$ does not divide $a$ or $a+1$. So the conclusion is also false.