Let $p$ be a prime $\ge 5$ prove that there exists $1\le a\le p-2$ such that (1) $p^2\not\mid a^{p-1}-1$ and (2) $p^2\not\mid (a+1)^{p-1}-1$.
This problem seems really complicated. I saw an answer on AoPS here but I didn't understand it because I don't know Group Theory. I wonder if there exists an elementary answer using just elementary number theory.
I thought that this would be a construction problem so I tried to construct the solution but I didn't succeed. Then I tried to prove that at least one of (1) or (2) is true. Here is my work till now,
Let $S=\{2,…,p-2\}$ (Guess why we don't care about the number 1), and $A=\{a\in S\mid a^{p-1}\not\equiv 1\pmod{p^2}\}$.
Claim 1: $a\not\in A\implies p-a\in A$
Assume that we have $$\cases{a^{p-1}\equiv 1\pmod{p^2}\\ (p-a)^{p-1}\equiv 1\pmod{p^2}}\text{ and }(p-a)^{p-1}=\sum_{k=0}^{p-1} {p-1\choose k}p^{p-1-k}a^{k}(-1)^k$$
Hence $$(p-a)^{p-1}\equiv a^{p-1}-p(p-1)a^{p-2}\equiv 1\pmod{p^2}$$
With some basic manipulation you would get $$p\mid a$$ A clear contradiction.
Edit:
I've just proved a nice thing,
Claim 2: $a\in A \implies a+1\not\in A$
The proof is simple. we have two cases, assume by way of contradiction that $\exists a\in S$ such that $a\in A$ and $a+1\in A$ then we're done. The second case is $\exists a\in S$ such that $a\not\in A$ and $a+1\not\in A$ then by Claim 1 we know $p-a\in A$ and $p-a-1\in A$ then we are also done.
Best Answer
First note that $$(p-a)^{p-1} - a^{p-1} = \sum_{k=2}^{p-1}\binom{p-1}{k}p^k(-a)^{p-1-k} + \binom{p-1}{1}p(-a)^{p-2} \equiv -p(p-1)a^{p-2}\equiv pa^{p-2} \not \equiv 0\mod p^2$$ so at least one of $p-a$ or $a$ is in $P = \{1\leq a\leq p-1|a^{p-1}\not\equiv 1 \mod p^2\}$. In particular $p-1\in P$ because $1 \not \in P$.
We have also shown that $|P| \geq (p-1)/2$ since at one number in each pairs of numbers $(p-i,i)$ must be in $P$.
Let $p = 2k+1, k \geq 2$ and consider the $k-1$ pairs $\{(2,3), (4,5),\ldots, (2k-2,2k-1)\}$. If there is a pair $(2i,2i+1)$ in this set such that both numbers are in $P$ then we have satisfied the problem (set $a = 2i$). If this is not the case, then at most one element of each pair must be in $P$, but $1 \not \in P$ and $p \in P$ and $|P| \geq k$ so exactly one entry in each pair must be an element of $P$.
If $2k-1 = p-2\in P$ then we are done because $2k = p-1 \in P$. If not, then $2k-2 = p-3 \in P$. In that case, we need show $2k-3 = p-4 \in P$. Suppose for the sake of contradiction, this is not true. Then since $p -2 \not \in P$ we have $$1 \equiv (p-2)^{p-1} \equiv 2^{p-1}+p2^{p-2} \mod p^2$$ by letting $a = 2$ in our calculation above. By squaring, we get $1 \equiv 4^{p-1}+ p2^{2(p-1)}\equiv 4^{p-1} + p4^{p-1} \mod p^2$.
Similarly, $$1 \equiv (p-4)^{p-1} \equiv 4^{p-1} + p4^{p-2}\mod p^2$$ so $$0 \equiv 4^{p-1} + p4^{p-1} - 4^{p-1} - p4^{p-2} \equiv 3p4^{p-2} \mod p^2$$ which is impossible. Hence, it must be the case that $p-4 \in P$.
So we have show that that either $p-2,p-1$ satisfy the claim or $p-4,p-3$ satisfy the claim. It is worth checking some examples on your own that the first solution works when $p = 5$ but not the second and for $p > 5$ the second works but not the first.