Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

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$).

My proof is a little bit different. We will consider 3 cases: 1)$(\frac{p-1}{2})^{p-1} \not \equiv 1 \mod{p^2}$ and $(\frac{p+1}{2})^{p-1} \not \equiv 1\mod{p^2}$ 2)$(\frac{p-1}{2})^{p-1} \equiv 1 \mod{p^2}$ 3)$(\frac{p+1}{2})^{p-1} \equiv 1 \mod{p^2}$ In the first case, we obviously take $a=\frac{p-1}{2}$. Let us consider the second case. $(\frac{p-1}{2})^{p-1} \equiv 1 \mod{p^2}$ is equivalent to $(p-1)^{p-1} \equiv 2^{p-1} \mod{p^2}$ which is, after reducing $\mod{p^2}$, $p(p-1) + 2^{p-1} - 1 \equiv 0 \mod{p^2}$ From FLT $2^{p-1} - 1$ is divisible by $p$ so, $2^{p-1} - 1 = pk$. So: $p(p-1) + 2^{p-1} - 1 = p(p-1 + k) \equiv 0 \mod{p^2}$ So, $p-1+k \equiv 0 \mod{p}$ which means that $k \equiv 1 \mod{p}$ and $2^{p-1} - 1 \equiv p \mod{p^2}$ Now, we will show that $a=p-2$ satisfies required condition. Indeed: $(p-2)^{p-1} - 1 \equiv 2^{p-2}p(p-1) + 2^{p-1} - 1 \equiv p(2^{p-2}(p-1) + 1) \mod {p^2}$ And since $2^{p-2}(p-1) + 1 \equiv -2^{p-2} + 1 \not \equiv 0 \mod{p}$ above congruence is not $0 \mod{p^2}$. Now we check $p-1$: $(p-1)^{p-1} - 1 \equiv -p(p-1) + 1 - 1 \equiv -p(p-1) \not \equiv 0 \mod{p^2}$ So, in this case we are done. We are left with the case 3) but it's almost the same.

Let $ S = \{1,2,\ldots,p - 1\}$. Let $ A$ be the set of guys in $ S$ such that $ a^{p - 1}\equiv1\pmod{p^{2}}$, and $ B$ be the others. Go by contradiction. 1. $ p - 1\in B$. Binomially expand $ (p - 1)^{p - 1}$. We get the sum of a bunch of terms that are divisible by $ p^{2}$, then the last two are $ - p(p - 1) + 1\equiv p + 1\pmod{p^{2}}$, which is not 1. 2. $ |B|\ge|A|$. We'll construct an injection from $ A$ into $ B$. Say $ a\in A$. Then, $ a^{p - 1}\equiv1\pmod{p^{2}}$. Now, consider $ a\rightarrow (p - 1)a$, which is an injection since $ p$ is prime (this is really just $ a$ to $ - a$). Then, $ ((p - 1)a)^{p - 1} = a^{p - 1}(p - 1)^{p - 1}\equiv p + 1\pmod{p^{2}}$, so $ (p - 1)a\in B$. Thus, $ |B|\ge|A|$. 3. $ |A|\ge|B|$. That is, at least half of our guys in $ S$ are in $ A$. $ p - 1$ is even, so we can break $ S$ up into the pairs $ \{1,2\},\{3,4\},\ldots,\{p - 2,p - 1\}$. By assumption, each of these pairs has a number that, when raised to the power $ p - 1$, is congruent to 1 modulo $ p^{2}$, so each pair has an element of $ |A|$. The conclusion follows. 1 and 3 give us $ |A| = |B|$. Now, note further that with our pairs from step 3, we in fact need exactly one member of each pair to be in $ A$. 1 is in $ A$, so 2 is not. This makes 3 in $ A$, so 4 is not. We see that we need the odd integers to be in $ A$, but the even integers to be in $ B$. We'll now proceed to get the contradiction. Case 1: $ p\ge17$. Observe that one of $ p + 2,p + 4$ is not prime (one has to be divisible by 3, as $ p$ is not). Both integers are odd, and thus have odd factors that are furthermore at most $ p - 1$. If $ p + 2$ is composite, write it as the product of odd factors $ f_{1},f_{2}$, and note that $ (p + 2)^{p - 1} = f_{1}^{p - 1}f_{2}^{p - 1}\equiv1\pmod{p^{2}}$. The exact same thing is true of $ p + 4$ if it is composite. Now, we multiply by $ (p - 2)^{p - 1}$ or $ (p - 4)^{p - 1}$, to get that $ (p^{2} - 4)^{p - 1}$ or $ (p^{2} - 16)^{p - 1}$ is also 1 modulo $ p^{2}$. Observe that $ p - 1$ is even, so these are the same as $ 4^{p - 1},16^{p - 1}$, which have even bases, and when $ p\ge17$, this means that they are not 1 modulo $ p^{2}$, contradiction. Case 2: $ p = 7,13$. $ p + 2$ is not prime here, and so we can do the same thing as before with $ p + 2$, to get $ 4^{p - 1}$ not 1 modulo $ p^{2}$. Case 3: $ p = 5$. $ 3^{4}\equiv6\pmod{25}$. Oops. Case 4: $ p = 11$. $ 5^{10}\equiv (125)^{3}\cdot5\equiv 64\cdot5\equiv320\equiv 78\pmod{121}$. Oops. This exhausts all cases, so we're done.

Lemma: $(p-x)^{p-1} \not\equiv x^{p-1} \pmod {p^2}$ for $1\leq x\leq p-1$. Proof: $(p-x)^{p-1} \equiv (-x)^{p-1} + (p-1)p(-x)^{p-2} \equiv x^{p-1} + px^{p-2} \not\equiv x^{p-1} \pmod {p^2}$. Suppose for contradiction that for $1\leq a \leq p-2$, either $a^{p-1}-1$ or $(a+1)^{p-1}-1$ is $0$ mod $p^2$. By our lemma, since $1^{p-1} -1 \equiv 0 \pmod {p^2}$, $(p-1)^{p-1} -1 \not\equiv 0 \pmod {p^2}$, so $(p-2)^{p-1} -1 \equiv 0 \pmod {p^2}$; repeating this argument, we find $x^{p-1} - 1 \equiv 0 \pmod {p^2}$ for $x = 1, 3, ..., p-2$; since $p-1$ is even, their negatives also satisfy the equation. Since $x^{p-1}-1$ is of degree $p-1$, it can have at most $p-1$ roots mod $p^2$, so these are all the roots. Thus, $x^{p-1}-1 \equiv (x^2-1)(x^2-3^2)...(x^2-(p-2)^2) \pmod {p^2}$. Now the coefficient of the term $x^{p-3}$ is $-\sum_{k=1}^{\frac{p-1}{2}} (2k-1)^2 = - \left(\frac{p-1}{2}\right)^2 \not\equiv 0 \pmod {p^2}$. But $0<p-3<p-1$, the coefficient must be $0$ mod $p^2$. Contradiction.

we can also do this in this way : considering the lemma posted by timwu we find as said : for $x=1,3,...,p-2$ we have $x^{p-1} \equiv 1 \pmod{p^2}$. now if we find two distinct odd numbers between 1 and p like i and j such that $ij \equiv 1 \pmod{p}$ we r done because then we have $ i^{p-1} \equiv j^{p-1} \equiv 1 \pmod{p^2}$ and so $p^2 | (ij)^{p-1}-1$ which is impossible because $p | ij-1 , p \nmid p-1 \implies p^2 | ij-1 < p^2-1$ which means that we must have ij=1 which contradicts the fact that they are distinct odd natural numbers. now suppose that $2^a || p-1$ then we have that $ (p-2^a)(\frac{p-1}{2^a}) \equiv 1 \pmod{p}$ so we must check the case in which $p = 2^a +1 $ or better say $p=2^{2^n}+1$ for some n . we can check the case p=5 easily. so let's assume that n > 1. we have 5 | 2p+1 and so there exists an odd number distinct from 5 such that $5i = 2p+1 \equiv 1 \pmod{p}$ and it's easy to see that $1 < 5,i < p$ DoNe!

Can't we just use LTE ?? : $ v_p(a^{p-1}-1) = v_p(a-1) $ ?

darkpseudo wrote: Can't we just use LTE ?? : $ v_p(a^{p-1}-1) = v_p(a-1) $ ? So $p$ doesn't divide $a-1$ implies $p$ doesn't divide $a^{p-1}-1$ ?

Yes because obviously p doesn't divides a ( a< p ) .

darkpseudo wrote: Yes because obviously p doesn't divides a ( a< p ) . And what about Fermat's little theorem?

Sorry I did'nt quite understood you at first , one of the conditions of LTE is that $v_p({a-1})\geq 1 $ so there is no contradiction with Fermat theorem . Here is what I was thinking : We know that there are $\frac {p-1}{2}$ quadratic residue mod p if there exist two successif quadratic residue then take the first as ''a'' then we have $ a^{\frac{p-1}{2}} = 1 [p] $ then by LTE we have $ v_p{a^{p-1}-1}= v_p{a^{\frac{p-1}{2}}-1 = 1 }$ and the same think for a+1 since it is also a quadratic residue . But still the other case can't be proven the same way .

darkpseudo wrote: $v_p{a^{\frac{p-1}{2}}-1 = 1 }$ . Why you are sure about this? For example: $a=3$, $p=11$ and $121|3^5-1$. I believe not a lot is known about $v_p m^{p-1}-1 $ when we don't know a lot about m.

I think this problem can be tackled using group theory, just that I haven't quite found the way to do so. Has anyone tried?

can somebody prove " $ P(x)=x^{p-1}-1 $ has $ p-1 $ roots in $ \mathbb{Z}_{p^{2}} $ "

I have a different approach! Assume the statement is false. Let a number $a$ modulo $p^2$ be "good" if $a^p = a (\bmod p^2)$, otherwise let it be bad. Then there are no consecutive bad numbers in $1,2,...,p-1$, so at least half of them are good. If $a$ is good notice $(p-a)^p = -a^p = -a \neq p-a (\bmod p^2)$ and so $p-a$ is bad. Therefore there are no consecutive good numbers in $1,2,...,p-1$ either, otherwise if we take $a,b$ consecutive good numbers, then $p-a,p-b$ are consecutive bad numbers. Since every number is good or bad and 1 is good, we reach the conclusion that: 1 is good, 2 is bad, 3 is good, 4 is bad, etcetera... Notice that this implies $p^2-1,p^2-3,...$ are all good, and so we have proven $p-1$ different numbers are good. Also notice that $(pk+a)^p = a^p (\bmod p^2)$ and so, for each subcongruence of $p$ modulo $p^2$, there is only 1 good number. This implies there are $p-1$ good numbers in total, which MUST be the ones I just described ($1,3,...,p-2$ and $p^2-1,p^2-2,...,p^2-(p-2)$). Since $p \ge 5$, we get that $(p-2)^2$ is NOT one of these numbers. Therefore, it is bad. But notice that $p-2$ is good, and so $((p-2)^2)^{p-1} = ((p-2)^{p-1})^2 = (1)^2 = 1 (\bmod p^2)$, and so $p-2$ is good. Contradiction! Q.E.D

Hmm how's this? Let $S = {1, 2, \ldots, p-1}$ and $X = x \in S \mid x^{p-1} \equiv 1 \mod p$ and $Y = y \in S \mid y^{p-1} \not\equiv 1 \mod p$. The case $|Y| = 0$ is clearly impossible as $p-1 \in Y$, which can easily be verified through binomial expansion. Then, for some element $y \in Y$, the elements $X \cdot y \in Y$ and are all distinct, so $|Y| \ge |X|$. If $|Y| > |X|$, we are done as there must be two consecutive $y$ terms, so assume $|Y| = |X|$. If there are no two consecutive $y$ terms, since $1 \in X$ and $p-1 \in Y$, it must be that $1, 3, 5, \ldots \in X$. Furthermore, $Y \cdot y \in X$ since $|Y| = |X|$ and $S \cdot y$ are all distinct, so $2 \cdot 2 \equiv 4 \in X$ for $p \ge 5$, a contradiction.

Can someone tell me if there's a mistake here, it seems too easy.... Call $a$ in $S=\{1,2,...,p-1\}$ "good" if $a^{p-1}=1 [p^2]$. If the problem statement is false, then for every $1 \le a \le p-2$, at least one of $a$ and $a+1$ is good. Then at least $(p-1)/2$ numbers in $S$ are good. It is easy to prove by binomial theorem that $(p-a)^{p-1}=(a^{p-1}+pa^{p-2}) [p^2]$. If $a$ in $S$ and $a^{p-1}=1 [p^2]$ then clearly $(p-a)^{p-1} \neq 1 [p^2]$. Thus at most one of $a,p-a$ are good for every $1 \le a \le (p-1)/2$. Thus there are at most $(p-1)/2$ good numbers in $S$, and hence there are exactly $(p-1)/2$ good numbers in $S$. For the problem statement to remain false, it follows that $1,3,...,p-2$ are good and $2,4,...,p-1$ are not good. Now note that if $a$ is good and $b$ is not good then $ab$ is not good. In particular, if $p \ge 7$ we get that since $3$ is good and $2$ is not good, $6$ is not good, a contradiction. If $p=5$ we can check that the problem statement is true manually.

It is well known that there exists a primitive root in $\mathbb Z/p^2\mathbb Z$. Hence for every $h\mid p(p-1)$ there exist exactly $\varphi(h)$ values $\alpha$ such that $\text{ord}_{p^2}(\alpha)=d$. Define $X={x\text{ s.t. }p^2\nmid x^{p-1}-1}$, and note that $x\in X\iff p\mid\text{ord}_{p^2}(x)$. Clearly there are $\sum_{d\mid p-1} \varphi(pd)=(p-1)\sum_{d\mid p-1} \varphi(d)=(p-1)^2$ such $x$. But for $p\geq 5$ we have $\tfrac{(p-1)^2}{p^2}>0.5$, and then it must be possible (by PHP) to find $a,a+1\in X$, as desired $\Box$

Remark that the problem could've been: ISL'01NT4 wrote: Given a positive integer $k$, show that for every sufficiently large prime $p$ there must exist $k$ consecutive integers $x_1,x_2,\cdots, x_k$ such that none of $x_i^{p-1}-1$ is divisible by $p^2$

My solution Lemma : If $a$ is an integer not divisible by $p$, then $p^2\mid (p-a)^{p-1}-1$ iff $p^2\mid a^p-a+p$ Proof : $p^2\mid (p-a)^{p-1}-1$ $\Leftrightarrow$ (by binomial expansion) $p^2\mid p(-a)^{p-2}(p-1)+(-a)^{p-1}-1$ $\Leftrightarrow$ (because $p$ is odd) $p^2\mid pa^{p-2}+a^{p-1}-1$ Put $M:=\frac{a^{p-1}-1}p$, then $M\in\mathbb{N}$ by FLT So $p^2\mid pa^{p-2}+a^{p-1}-1$ $\Leftrightarrow$ $p^2\mid pM+ pa^{p-2}$ $\Leftrightarrow$ $p\mid M+a^{p-2}$ $\Leftrightarrow$ (because $p$ doesn't divide $a$) $p\mid aM+a^{p-1}=aM+pM+1$ $\Leftrightarrow$ $p\mid aM+1$ $\Leftrightarrow$ $p^2\mid paM+p=a^p-a+p$ $\Box$ Suppose that $p^2\mid a^{p-1}-1$ and $p^2\mid (a+1)^{p-1}-1$ for $a\in [\![1,p-2]\!]$ : by our lemma, one can find that neither $(p-a-1)^{p-1}-1$ nor $(p-a)^{p-1}-1$ is divisible by $p^2$, which would finish the proof So suppose that $p^2\mid a^{p-1}-1$ $\Rightarrow$ $p^2$ divides neither $(a-1)^{p-1}-1$ nor $(a+1)^{p-1}-1$ Suppose the problem is false, and w'll derive a contradiction $p^2\mid 1^{p-1}-1$ so $p^2$ divides not $2^{p-1}-1$ so $p\mid 3^{p-1}-1$... and so each integer $a$ odd in $[\![1,p-1]\!]$ is such as $p^2\mid a^{p-1}-1$ and contrary for even $a$. By our lemma, for an even a, because $a$ is even $p-a$ is odd, we get that $a^p-a\equiv -p\mod{p^2}$ Because $p\geq5$, we have for $a=2,4$, $2^p-2\equiv_{p^2} -p$ and $4^p-4\equiv_{p^2}-p$, so that $2^p\equiv_{p^2}2-p$ and then $-p\equiv_{p^2}4^p-4=2^{2p}-4\equiv_{p^2}(2-p)^2-4\equiv_{p^2} -4p$ so $3p\equiv 0\pmod{p^2}$, a contradiction $\Box$

eraydin wrote: can somebody prove " $ P(x)=x^{p-1}-1 $ has $ p-1 $ roots in $ \mathbb{Z}_{p^{2}} $ " Hensel Lemma can!

Cindy.tw wrote: eraydin wrote: can somebody prove " $ P(x)=x^{p-1}-1 $ has $ p-1 $ roots in $ \mathbb{Z}_{p^{2}} $ " Hensel Lemma can! A simpler way is to notice that $$x^{p(p-1)}-1=(x^{p-1}-1)(x^{(p-1)^2}+\dots +1)$$But since in $\mathbb{Z} _{p^2}$ $x^{p(p-1)}-1 $ has exactly $p(p-1)$ roots, $P(x)$ has at most $p-1$ roots and $x^{(p-1)^2}+\dots +1$ has at most $(p-1)^2$ roots, $P(x)$ has exactly $p-1$ roots.

From here, we work only in $\mathbb{Z} / p^2\mathbb{Z}$. It is well known that $x^{p-1} - 1$ has at most $p-1$ roots. Moreover, if $x$ is a root, then $-x$ is also a root. Therefore there at most $\frac{p-1}{2}$ integers between $1$ and $p-1$ that are roots. Thus the only way there are no two consecutive roots is if all the odds or all the evens are roots. Since $1$ is obviously a root, it must be the odds. Thus \[ x^{p-1}-1 = (x-1)(x+1)(x-3)(x+3) \cdots(x-p+2)(x+p-2) = (x^2 - 1)(x^2 - 9) \cdots (x - (p-2)^2 .\]However, the coefficient of $x^{p-3}$ on the right hand side is \[ - (1^2 + 3^2 + \cdots + (p-2)^2) = 2^2(1^2 + 2^2 + \cdots (p-1/2)^2) - (1^2 + 2^2 + \cdots (p-1)^2) = \frac{p (p-1)(p+1) - p(p-1)(2p-1)}{6} = \frac{p(p-1)(2-p)}{6} \]which is not divisible by $p^2$, contradiction.

, but originally when I tried this problem, I had the following approach: Assume for the contrary that among every $2$ consecutive numbers, at least one is divisible by $p^2$. Also, note that $p|a^p-a$ always due to Fermat. So, $p^3 | (i^{p-1}-1)((i+1)^{p-1} -1) \ \forall \ i \in [{1,2,...p-2}]$. Now I attempt to prove that this is not possible by proving a much stronger result, that in fact $p^3$ can not divide $\sum_{i=1}^{p-2} (i^{p-1}-1)((i+1)^{p-1} -1)$. If this is true, then clearly the problem will be finished. Now first I tried this for $p=5,7$, it works! Then I spent a (very) long time trying to play with that expression modulo $p^3$ but I could not do much at all. I could reduce it to showing that $p^3 \nmid \sum_{i=1}^{p-2} (i^2+i)^{p-1} + p + p^2 \cdot \binom{p-1}{2} - p(p-1) - 2 \sum_{i=1}^{p-1} i^{p-1}$ but then I could do nothing more. NOTE: I tried this problem with above mentioned approach for at least about $4-5$ hours spread out over two days. I tried to check this for $p=11$ but my calculator won't work upto that point (it just approximates the product then, which is not good for divisibility). So after working very long on this method, I gave up on this and worked through the official solution, But still it seems like this approach should work, in fact it does for $5,7$! But as I am not very experienced, I am not able to work through this, but these expressions seem calculatable mod $p^3$ but I just am not able to do it. So I am posting it here in the hope that someone else may be able to try it using this method (as imo, it seems pretty cool) or even check upto some larger values. If you are able to do it, please please post it here (and also PM me pls). By the way, the official solution is sooooo coool !

I knew this was Hensel's as soon as I saw it Claim: $f=X^{p-1}-1$ has precisely $p-1$ roots in $\mathbb{F}_{p^2}$ Proof: Observe that $f'=(p-1)X^{p-2}$ and thus, $f'$ doesn't have roots in $\mathbb{F}_p^\times.$ Therefore, by Hensel's Lemma, for each $i\in\mathbb{F}_p^\times$ there exists a unique $j\in \mathbb{F}_p$ such that $i+jp$ is a root of $f$ in $\mathbb{F}_{p^2}.$ Consequently, $f$ has precisely $p-1$ roots not divisible by $p$ in $\mathbb{F}_{p^2}.$ It is obvious that $pk$ is never a root of $f,$ and thus, out claim is proven. $\square$ Coming back to the problem, let's assume it is false. It then follows that each of $\{1,2\},\{2,3\},...,\{p-2,p-1\}$ has (at least) a root of $f$ in $\mathbb{F}_{p^2}.$ Hence, $f$ has at least $p-1/2$ roots in $\{1,2,...,p-1\}.$ However, if $x$ is a root then so is $-x.$ Therefore, by our claim, there are precisely $(p-1)/2$ roots in each of the intervals $[1,p-1]$ and $[p^2-p+1, p^2-1],$ and since $1$ is a root, then $3$ and $p-2$ must also be roots. This is a clear contradiction, since $3(p-2)$ will also be a root, and $p-1<3(p-2)<p^2-p+1.$

Probably some of the arguments can be simplified. By veryfing $p=5$ and $p=7$ directly (both work with $a=2$), we may assume $p\geq 11$. Observe that $a=1$ is impossible so let us consider only $\{2,3,\ldots,p-2\}$. If $g$ is a primitive root modulo $p^2$ and $x = g^k$, $1\leq k \leq \varphi(p^2) = p(p-1)$, then $x^{p-1} \equiv 1 \pmod {p^2}$ if and only if $g^{k(p-1)} \equiv 1 \pmod {p^2}$, which is if and only if $p(p-1) \mid k(p-1)$, i.e. $p$ divides $k$. So the number of solutions to $x^{p-1} \equiv 1 \pmod {p^2}$ is $\frac{p(p-1)}{p} = p-1$ which implies that the number of solutions in $\left[1,\frac{p^2-1}{2}\right]$ is $\frac{p-1}{2}$ (as if $x$ is a solution, then so is $p^2-x$ since $p-1$ is even). In particular, as $1$ is a solution and $\frac{p^2-1}{2} > p - 1$, the number of solutions in $[2,p-1]$ is at most $\frac{p-3}{2}$. Now if we suppose, for contradiction, that the desired statement does not hold, then in $\{2,\ldots,p-1\}$, $p\geq 11$, among two consecutive elements at least one has to be a solution to $x^{p-1} \equiv 1 \pmod {p^2}$. So the number of solutions in this set is at least $\frac{p-3}{2}$, which equals the abovementioned upper bound. Equality is possible if and only if the solutions in $\left[2,\frac{p^2-1}{2}\right]$ are precisely $3$, $5$, $\ldots$, $p-2$. Moreover, it is clear if $x_1$ and $x_2$ are solutions to $x^{p-1} \equiv 1 \pmod {p^2}$, then so is $x_1x_2$ - hence $(p-2)(p-4) \equiv 8-6p$ and $6p-8$ is also a solution. However, $6p-8 > p - 2$ and $6p - 8 \leq \frac{p^2-1}{2}$ (equivalent to $p(p-12) + 15 \geq 0$ which is true for $p\geq 11$) and this is a contradiction!

Let us define set $A$ to be the set of $a$ such that $a^{p-1}\not\equiv 1 \pmod{p^2}$. We would like to show that there are two elements of $A$ that are consecutive. Note that if $a\not\in A$ (i.e. if $a^{p-1}\equiv 1 \pmod{p^2}$), then $$(p-a)^{p-1}\equiv -\tbinom{p-1}{1}pa^{p-1}+a^{p-1}\equiv pa^{p-2}+1 \pmod{p^2}.$$It follows that in order for $(p-a)^{p-1}$ to be congruent to $1 \pmod{p^2}$, we need $pa^{p-2}\equiv 0\pmod{p^2}$, meaning that $p$ has to divide $a^{p-2}$. But $a$ is coprime to $p$, so $(p-a)\in A$ if $a\not\in A$. We know that $1\not\in A$, so $(p-1)\in A$. Assume for the sake of contradiction that the problem statement is false. Then we must have $(p-2)\not\in A$, $(p-3)\in A$, and $(p-4)\not\in A$. If $(p-2)\not\in A$, then $(p-2)^{p-1}\equiv 1 \pmod{p^2}$. Then, expanding and simplifying using the binomial theorem, we get $2^{p-2}p+2^{p-1}\equiv 1 \pmod{p^2}$. If $(p-4)\not\in A$, then $(p-4)^{p-1}\equiv 1\pmod{p^2}$. Expanding and simplifying using the binomial theorem, we get $2^{p-2}+2^{2p-3}\equiv 1 \pmod{p^2}$, which we can factor as $$(2^{p-1}-1)(2^{p-2}+1)\equiv 0\pmod{p^2}.$$Since $(p-2)\not\in A$, we must have $2\in A$, and so $2^{p-1}-1\not\equiv 0\pmod{p^2}$. So the only way that the above congruence could be true is if $p^2\mid 2^{p-2}+1$. However, by Fermat's Little Theorem, we have $2^{p-1}\equiv 1\pmod{p}$, so $2^{p-2}+1\equiv 2^{-1}+1 \pmod{p}$. Since the inverse of $2$ is $\tfrac{p+1}{2}$, we now have $2^{p-2}+1\equiv \tfrac{p+1}{2}+1 \pmod{p}$. We see that in order for $\tfrac{p+1}{2}+1\equiv 0 \pmod{p}$, we must have $3\equiv 0 \pmod{p}$. Since we are given $p\geq 5$, we have now reached a contradiction, so it is not possible for both $(p-2)\not\in A$ and $(p-4)\not\in A$, and we are done.

sergei93 wrote: I think this problem can be tackled using group theory, just that I haven't quite found the way to do so. Has anyone tried? Let $P(x)=x^{p-1}-1$, and let $g$ be a generator of $(\mathbb{Z}/{p^2}\mathbb{Z})^{\times}$. The set of roots of $P(x)$ are precisely the $p-1$ elements of the multiplicative subgroup $G=\langle g^p \rangle$. Given that $a$ is a root iff $-a$ is a root, the roots of the polynomial must also be $G'=\pm \{1, 3, \dots, p-2\}$ for the problem to not be true. However, it can be verified that for $p\geq 5$, $G'$ doesn't form a group under multiplication mod $p^2$. This yields the desired contradiction. $\blacksquare$

Let $A=\{x\mid 1\le x\le p-2\land x^{p-1}\not\equiv 1\pmod{p^2}\}.$ We claim $a\not\in A$ implies $p-a\in A.$ Indeed, $$(p-a)^{p-1}\equiv a^{p-1}-\binom{p-1}{1}pa^{p-2}\equiv a^{p-1}+pa^{p-2}\pmod{p^2}.\quad(*)$$Suppose FTSOC that at most one of $a,a+1$ is an element of $A$ for all $a\in[1,p-2].$ Notice $$1\not\in A\implies p-1\in A\implies p-2\not\in A\implies 2\in A\implies 3\not\in A\implies p-3\in A\implies p-4\not\in A.$$Hence by $(*),$ $$1^2\equiv\left((p-2)^{p-1}\right)^2\equiv\left(2^{p-1}+p2^{p-2}\right)^2\equiv 2^{2(p-1)}+2\cdot 2^{p-1}\cdot p2^{p-2}\equiv 4^{p-1}+p4^{p-1}\pmod{p^2}$$and $1\equiv (p-4)^{p-1}\equiv 4^{p-1}+p4^{p-2}\pmod{p^2}.$ Therefore, $4^{p-1}+p4^{p-1}\equiv 4^{p-1}+p4^{p-2}\pmod{p^2}$ or $4^{p-1}\equiv 4^{p-2}\pmod{p}$ or $4\equiv 1\pmod{p}$ since $p>2.$ This is absurd, as it implies $p\mid 3$ and we have $p>3.$ $\square$

We consider $a=p-2$ and $a=\tfrac{p-1}{2}$. I claim that at least one of these works. First suppose that $a=p-2$ doesn't work, i.e. one of $(p-2)^{p-1}-1$ and $(p-1)^{p-1}-1$ is divisible by $p^2$. By the Binomial Theorem, $$(p-1)^{p-1}-1 \equiv -(p-1)p+1-1 \equiv p \pmod{p^2},$$so we would require $p^2 \mid (p-2)^{p-1}-1$. Again by the Binomial Theorem, we have $$(p-2)^{p-1}-1 \equiv -(p-1)2^{p-2}p+2^{p-1}-1 \pmod{p^2} \implies 2^{p-1}-1 \equiv -2^{p-2}p \pmod{p^2}.$$Now we look at $a=\tfrac{p-1}{2}$. We have $$p^2 \mid (\tfrac{p-1}{2})^{p-1}-1 \iff (p-1)^{p-1}-2^{p-1} \equiv 0 \pmod{p^2} \iff -(p-1)p+1-2^{p-1} \equiv 0 \pmod{p^2} \iff 2^{p-1}-1 \equiv p \pmod{p^2},$$but since $-2^{p-2} \not \equiv 1 \pmod{p}$, this is impossible. Likewise, $p^2 \mid (\tfrac{p+1}{2})^{p-1}-1$ is equivalent to $2^{p-1}-1 \equiv -p \pmod{p^2}$, which is also impossible, hence $a=\tfrac{p-1}{2}$ works if $a=p-2$ doesn't, so we're done. $\blacksquare$

Solved with two hints from MONT. Let $S$ be the set of positive integers $k$ such that $1\le k\le p-1$ and $p^2\nmid\left(k^{p-1}-1\right).$ We will first prove that at least one of $a$ and $p-a$ is in $S$. Assume FTSOC that neither of them are in $S$. We have that $$0\equiv (p-a)^{p-1}-1\equiv -(p-1)(p)\left(a^{p-2}\right)+a^{p-1}-1\equiv p\cdot a^{p-2}\pmod{p^2},$$which is impossible because $p\nmid a$, contradiction. Now, assume FTSOC that the wanted statement is false. Then, for every two consecutive positive integers between $1$ and $p-1$, inclusive, at most one of them is in $S$. Specifically, $\left\{\frac{p-1}{2},\frac{p+1}{2}\right\}$ must have exactly one element in $S$. Assume for now that $\frac{p+1}{2}$ is the one not in $S$(the other case is symmetric). Then, $\frac{p+3}{2}$ must be in $S$, so $\frac{p-3}{2}$ must not be in $S$. Then $\frac{p-5}{2}$ must be in $S$, etc. This makes all odd positive integers within bounds in $S$ and all even positive integers within bounds not in $S$, or vice versa. However, since $1$ is clearly in $S$, we indeed have that all odd positive integers within bounds are in $S$ and all even positive integers within bounds are not in $S$. Now, this means that $p-2$ and $p-4$ are both in $S$. Plugging in, $$1\equiv (p-2)^{p-1}\equiv -(p-1)(p)\left(2^{p-2}\right)+2^{p-1}\equiv p\cdot 2^{p-2}+2^{p-1}\pmod{p^2}.$$Multiplying both sides by $2$, we get that $$p+2^p\equiv2\pmod{p^2}.$$Similarly, we also have $$p+4^p\equiv4\pmod{p^2}.$$These combine to $$p+(2-p)^2\equiv p^2-3p+4\equiv4\pmod{p^2},$$which means that $p|3$, contradiction. QED.

Call a positive integer $0\le a\le p^2-1$ $p$-powerful if $p^2\equiv a^{p-1}-1$. If $a$ is $p$-powerful and $b$ is $p$-powerful then $ab$ is $p$-powerful. There are also at most $p-1$ $p$-powerful numbers. Assume the opposite of what we want to prove, then $\{2k-1,2k\}$ has a $p$-powerful number for $1\le k\le \tfrac{p-1}{2}$, and since $-1$ is $p$-powerful, the additive inverse of each of those $p$-powerful is also $p$-powerful. That gives $p-1$ numbers. However, one of the following numbers is $p$-powerful: \[\frac{(p-2)(p-1)}{2}\]\[\frac{(p-1)(p-1)}{2}\]\[\frac{(p-2)(p+1)}{2}\]\[\frac{(p-1)(p+1)}{2}\]but none of them are between $1$ and $p-1$ or $p^2-p+1$ and $p^2-1$ inclusive. Contradiction.

Call a nonzero residue mod $p$, $a$, fortunate if $$a^{p-1}\equiv 1\pmod{p^2},$$and unfortunate otherwise. We wish to show that there exist two consecutive unfortunate residues mod $p$. Claim: At least one of $a$ and $p-a$ is unfortunate. Suppose note. Then, $$a^{p-1}\equiv 1\pmod{p^2}$$and $$(p-a)^{p-1}\equiv 1\pmod{p^2}.$$However, by binomial theorem the latter is $$p(-a)^{p-2}(p-1)+a^{p-1}\pmod {p^2}.$$However, since we know that $a^{p-1}$ is 1 mod $p^2$, this means that $p(-a)^{p-2}(p-1)$ is divisible by $p^2$, which is clearly false. Now, note that clearly 1 is fortunate. Thus, due to the claim the only possible way for there to be no two consecutive unfortunate numbers is if $a$ is unfortunate if and only if $a$ is even. Now, this means that $p-2$ and $p-4$ are both fortunate. Expanding out $$(p-2)^{p-1}\equiv 1\pmod{p^2}$$using binomial theorem would give us $$p(-2)^{p-2}(p-1)+2^{p-1}\equiv 1\pmod{p^2}$$which rearranges to $$2^{p-2}(p+2)\equiv 1\pmod{p^2}.$$Doing the same with $p-4$, we have $$4^{p-2}(p+4)\equiv 1\pmod{p^2}.$$If we square the first congruence, we get $$4^{p-2}(p^2+4p+4)\equiv 1\pmod{p^2}$$$$4^{p-2}(4p+4)\equiv 1\pmod{p^2}$$However, since $4^{p-2}$ is relatively prime to $p^2$, $p+4$ and $4p+4$ are both the inverse of $4^{p-2}$ mod $p^2$. Hence, they are congruent mod $p^2$, which means that $$3p\equiv 0\pmod{p^2},$$clearly a contradiction as $p\geq5.$

Solved with blueberryfaygo_55. Suppose otherwise. Notice that for any $a$ with $1 \le a \le p - 1$, the terms in the binomial expansion of $(p-a)^{p-1}$ are all divisible by $p^2$ except $-p(p-1) a^{p-2}$ and $a^{p-1}$, so \[ (p-a)^{p-1} \equiv a^{p-1} - p(p-1) a^{p-2} \equiv a^{p-1} + p a^{p-2} \pmod{p^2} \ \ \ \ \ \ \ (1)\] In particular, if $a^{p-1} \equiv 1\pmod{p^2}$, then $(p-a)^{p-1} \equiv 1 + pa^{p-2} \not \equiv 1\pmod{p^2}$. If $x, x+1$ (for $1 \le x \le p - 2$) satisfied $x^{p-1} - 1 \equiv (x+1)^{p-1} - 1 \equiv 0\pmod{p^2}$, then notice that $a = p - x - 1$ would satisfy $a^{p-1} - 1 $ and $(a+1)^{p-1} - 1$ aren't divisible by $p^2$. Thus, exactly one of $x^{p-1} - 1$ and $(x+1)^{p-1}$ is divisible by $p^2$. Since $p^2 \mid 1^{p-1} - 1$, we have that $p^2 \nmid 2^{p-1} - 1, p^2 \mid 3^{p-1} - 1 \ldots,$ so for each $1 \le x \le p - 2$, $p^2 \mid x^{p-1} - 1$ iff $x$ is odd. Now if we plug in an even $a$ (where $2 \le a \le p - 1$) into $(1)$, we see that the LHS is $1\pmod{p^2}$, so $a^{p-1} \equiv p a^{p-2} + 1 \pmod{p^2}$ for any even $1 \le a \le p - 2$. Multiplying both sides by $a$ gives that $a^p \equiv p a^{p-1} + a \equiv a + p \pmod{p^2}$. Note that $2$ and $4$ are both at most $p - 1$, so $2^p \equiv 2 + p \pmod{p^2}$ and $4^p \equiv 4 + p \pmod{p^2}$, so $p^2 \mid (p+2)^2 - (p + 4) = p^2 + 3p$, so $p^2 \mid 3p \implies p \mid 3$, absurd.

Let use work in $\mathbb{Z}/p^2\mathbb{Z}$. Assume FTSOC such $a$ does not exist. Let $G:=\{a\in\mathbb{Z}/p^2\mathbb{Z}\mid a^{p-1}=1\}=\langle g^p\rangle$ be a subgroup of $(\mathbb{Z}/p^2\mathbb{Z})^\times$, where $g$ is a primitive root of $\mathbb{Z}/p^2\mathbb{Z}$. Note that $|G|=p-1$. Since $p-1$ is even, if $a^{p-1}=1$ then $(-a)^{p-1}=1$. Hence \[ |G\cap\{1,\ldots,p-1\}|=|G\cap\{-1,\ldots,-(p-1)\}|. \]By the assumption, we must have $2^{p-1}=1$ or $3^{p-1}=1$ (or both). Then $2^{-1}\in G$ or $3^{-1}\in G$. Since $p\geq 5$, we have \[ 2^{-1},3^{-1}\not\in\{1,\ldots,p-1,-1,\ldots,-(p-1)\} \]so \[ |G\cap\{1,\ldots,p-1\}|=|G\cap\{-1,\ldots,-(p-1)\}|<\frac{p-1}{2}. \]Since there are $\frac{p-1}{2}$ pairs $(1,2),(3,4),\ldots,(p-2,p-1)$, it follows that one of these pairs satisfies the given condition, a contradiction. $\square$

can anyone tell me the motivation behind the TomiciO's answer

Assume FTSOC that such an $a$ does not exist. Call an $a$ bad if $p^2 \nmid a^{p-1} - 1$. So out of \[ 1, 2, \dots, p-1 \]no two consecutive numbers may be bad. Hence there are at most $\frac{p-1}{2}$ bad numbers. Now, henceforth work in $\mathbb{F}_{p^2}$, and consider the polynomial \[ X^{p-1} - 1 = 0 \] Claim: The roots of $X^{p-1} - 1 = 0$ in $\mathbb{F}_{p^2}$ are precisely \[ \{ 1, 3, 5, \dots, p-2 \} \cup \{ p^2-p+2, p^2-p+4, \dots, p^2-1 \}. \]Proof. It is well known, due to Frobenius, that $X^{p-1} - 1$ has $p-1$ roots in $\mathbb{F}_{p^2}$. Since there are at most $\frac{p-1}{2}$ bad numbers, then there are at least $\frac{p-1}{2}$ roots in $\{ 1, 2, \dots, p-1 \}$. Yet if $a$ is a root so is $p^2 - a$. Thus there are also at least $\frac{p-1}{2}$ roots in $\{ p^2-p+1, \dots, p^2-1 \}$. So the inequality is strict, thus there are exactly $\frac{p-1}{2}$ bad numbers. Since they cannot be consecutive, and $1$ is not bad, it follows that $2, 4, \dots, p-1$ are the bad numbers. Thus $1, 3, \dots, p-2$ are good. $\square$ But notice that \[ 1 = 3^{p-1} \implies \left( \frac 13 \right)^{p-1} \equiv 1 \]But $\frac 13 = \frac{2p^2+1}{3}$, since $p^2 \equiv 1 \pmod 3$. Check that \[ \frac{2p^2 + 1}{3} \le p-1 \implies 2p^2 - 3p + 4 \le 0 \implies p \le 2 \]absurd, and \[ \frac{2p^2 + 1}{3} \ge p^2-p+1 \implies 0 \ge p^2-3p+2 \implies p \le 2 \]absurd again. Thus $p-1 < \frac{2p^2+1}{3} < p^2 - p + 1$, so we found another root, contradiction. $\blacksquare$

A messy and sloppy albeit elementary solution. This problem was rather fun and had a weird combinatorial nature about it. We say a positive integer $1 \le a \le p-2$ is good if and only $p^2 \mid a^{p-1} -1$ and bad otherwise. The following is the key claim. Claim : For all $1 \le a \le p-2$, at most one of $a$ and $p-a$ is good. Proof : Consider $a$ to be good. Then, \begin{align*} (p-a)^{p-1}-1 &\equiv p^{p-1} - \binom{p-1}{1}ap^{p-2}+\dots - \binom{p-1}{p-2}a^{p-2}p + a^{p-1} -1 \pmod{p^2}\\ & \equiv -p(p-1)a^{p-2} + a^{p-1}-1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \pmod{p^2}\\ & \equiv \frac{p}{a} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \pmod{p^2}\\ & \not \equiv 0 \pmod{p^2} \end{align*}since $\gcd(p,a)=1$, which clearly implies that $(p-a)$ is bad. Clearly this holds when $p=5$ (consider $a=2$) and $p=7$ (consider again $a=2$). Now, we assume that there exists some prime $p>7$ such that the desired condition is not satisfied. Then, one of 2 or 3 must be good. If 2 is good, $p-2$ is not good, which implies that $p-3$ must be good. This in turn implies that $3$ is not good, and so on. Thus, if $2$ is good, all $2\le a \le p-2$ such that $2\mid a$ must be good, and the rest must be bad. Similarly, if $3$ is good, all $3 \le a \le p-2$ such that $2\nmid a$ must be good, and the rest bad. Case 1 : If $2$ is good, note that one of $p-3$ and $p-5$ must be a non-power of two ($p>7$). Thus, we can write this integer $a$ in the form $a=2^k l$ for positive integers $k$ and $l>1$. But then, \[(2^kl)^{p-1} \equiv 1 \pmod{p^2}\]and \[(2^k)^{p-1} \equiv 1 \pmod{p^2}\]But this implies, \[l^{p-1} \equiv 1 \pmod{p^2}\]which is a clear contradiction. Case 2 : $2$ is not good but $3$ is good. Note that then, \[2^{p-1}-1 \equiv \frac{p}{(p-2)} \pmod{p^2}\]and \[6^{p-1}-1 \equiv \frac{p}{p-6} \pmod{p^2}\]Thus, \[1 \equiv 3^{p-1} \equiv \frac{\left(\frac{2p-6}{p-6}\right)}{\left(\frac{2p-2}{p-2}\right)}\]which implies, \[(p-3)(p-2) \equiv (p-6)(p-1) \pmod{p^2}\]Thus, $p^2 \mid 12p$ which is a contradiction for all primes $p >7$. Thus, this case is impossible too, indicating that our assumption that there exist no two consecutive good integers must have been false, which finishes the proof.