2001 IMO Shortlist Problems/N4

Problem

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

Solution (Elementary Group Theory)

Let us work in the group $(\mathbb{Z}/p^2\mathbb{Z})^{\times}$ .

Note that the order of this group is $\phi({p^2})=p^2-p$ . Since $(\mathbb{Z}/p^2\mathbb{Z})^{\times}$ is cyclic, we know that it is isomorphic to $(\mathbb{Z}/(p^2-p)\mathbb{Z})^{+}$ .

We can then conclude how many residues $n$ there are such that $(p-1)n\equiv0\text{ (mod }p^2-p\text{)}$ . For some arbitrary natural number $k$ , one has: $(p-1)n=k(p^2-p)$ $n=kp$ Therefore there are only $p$ possible values of $n$ . It's also notable that if this is true for $n_0$ , then it is also true for $p^2-p-n_0$ , and $2n_0$ . This implies that there are also $p$ different values of a such that $a^{p-1}\equiv 1\text{ (mod }p^2\text{)}$ , more specifically, it implies that if and only if $a_0$ has this property, so does $\frac{1}{a_0}$ and $\frac{1}{a^2}$ when working in $(\mathbb{Z}/p^2\mathbb{Z})^{\times}$ . The squares also have their inverses which are guaranteed to have the propert.

There exists no numbers $1<m_1,m_2\leq p-2$ such that $m_1m_2\equiv1\text{ (mod }p^2\text{)}$ as $(p-2)(p-2)<p^2$ and $2^2>1$ . Therefore, at most half of the values where $a_0^{p-1}\equiv 1\text{ (mod }p^2\text{)}$ are in range $1<a_0\leq p-2$ . We can again remove some of the potential values by squaring all $a_0\geq\sqrt{p}$ and taking their inverse. As long as no more than half of the values in that range can have the required property, there must be a pair $a$ and $a+1$ that satisfy the requirements by the pigeonhole principle. $\frac{p-\sqrt(p-2)-1}{2}\leq\frac{p-3}{2}$ $2\leq(\sqrt(p-2))$ $p\geq6$