Prove that there exists $1\le a\le p-2$ such that $p^2\not\mid (a+1)^{p-1}-1$ and $p^2\not\mid a^{p-1}-1$ 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.
 A: 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.
A: Using your idea, but still not a full answer.
Let $P=\{1,2,\dots,p-1\}$. For any $a\in P$ we have that $a^{p-1}=1+k_a p+\ell_a p^2$ from Fermat's little theorem, with $0\leq k_a\leq p-1$ for all $a\in P$.
Let $A=\{a\in P: k_a\neq 0\}$.
Let's assume that the statement of the problem is false. Then we cannot have $k_a$ and $k_{a+1}$ both not $0$. However, using your claim, we also cannot have $k_a$ and $k_{a+1}$ both $0$ since then $k_{p-a-1}$ and $k_{p-1}$ would be non-zero. Therefore we are assuming that the sequence $k_1,k_2,\dots ,k_{p-1}$ must alternate between zero and non-zero values.
But clearly $k_1=0$. So wlog, assume that $k_{odd}=0$ and $k_{even}\neq 0$.
We can say a bit more. Note that $k_{ab}=k_a+k_b$. Setting $k:=k_2$ for simplicity, it is then easy to see (e.g. using prime factorization and the fact that all primes after $2$ are odd) that $k_a=\lfloor {\log_2{a}}\rfloor k$ for all $1\leq a\leq p-1$.
For example, for $p=11$, the sequence $\{k_a\}$ would be $0,k,0,2k,0,k,0,3k,0,k$.
In fact, just for laughs, one can compute explicitly what $k$ should be in this situation by noting that $(\prod_{a=1}^{p-1} a)^{p-1}\equiv 1\mod{p}$ and therefore $k$ would have to be the inverse of $\sum_{k=1}^{\infty}\lfloor\frac{p-1}{2^k}\rfloor$ ($\mod{p}$).
The question remains why such a setup is not possible. Doing some direct computations for $p=5,7,11$ seems to suggest that the issue is that in reality the $k_a$ sequence doesn't have this many $0$s.
A: EDIT: As originally written, this proof is incorrect; it fails to account for the cases where $k=0$. Reworking it.

I think we can move this out of group theory to elementary number theory, working mostly in modulo $p^2$. We know from Euler's theorem that
$$a^{\phi(p^2)} \equiv 1 \pmod{p^2} \iff \\ a^{p(p-1)} \equiv 1 \pmod{p^2} \iff \\ (a^p)^{p-1} \equiv 1 \pmod{p^2}$$
as long as $a \not \in \{p, 2p, \cdots p(p-1)\}$. But we know $0 <a< p-1$ already.
Let's look at that $a^p$ that shows up in the last expression. Euler's theorem tells us $a^p \equiv a \pmod p$, which implies $a^p \equiv a + kp \pmod {p^2}$ for some $k <p$. But that further implies $a^{p-1} -1 \equiv ka'p \pmod {p^2}$, where $a'$ is the inverse of $a \pmod {p^2}$.
Since $k < p$, we know $p \nmid k$. Similarly, $p \nmid a'$, because $(a,p) \neq 1 \iff a$ is not invertible $\pmod {p^2}$. And that means that $p^2 \nmid ka'p$, which means $p^2 \nmid a^{p-1} -1$.
Since this is true for all $a$, it will be true for all $a+1$, as $1 < a+1 \leq p-1$ under our constraints. Hence
$$\forall a \in \{1,2, \cdots p-2\}: p^2 \nmid (a+1)^{p-1} - 1$$
which is the first result desired, and technically more stringent.

For the second result we can start partway through, noting that
$$a^{p-1} \equiv 1 +ka'p \pmod {p^2} \implies \\ a^{p-2} \equiv a' + kp(a')^2 \pmod {p^2} \iff \\ a^{p-2} -1 \equiv a' + kp(a')^2 -1 \pmod {p^2}$$
OK, that's a bit ugly. We know $p \nmid a$, so we can multiply the whole thing by $a$, preserving divisibility:
$$a(a^{p-2} -1) \equiv kpa' -a +1 \pmod {p^2}$$
Obviously $p \mid kpa'$. But just as obviously, $p \nmid a -1$. A multiple of $p$ plus a non-multiple of $p$ cannot be a multiple of $p$, much less of $p^2$. Multiplying back through by $a'$, which is also not a multiple of $p$, gives us
$$a^{p-2} -1 \equiv q(mp -r) \pmod{p^2} $$
In this expression, we know $p \nmid q, p \nmid r$. Therefore the right side is non-zero $\pmod{p^2}$, and
$$\forall a \in \{1,2, \cdots p-2\}: p^2 \nmid a^{p-2} - 1$$
which is the second desired result.

I'm not 100% confident in this, but I think it stands muster; feel free to point out holes.
