The 37th Korean Mathematical Olympiad Final Round

Define $$S=\{1\le a\le p^2:p^2|a^{p-1}-1\},S_p=S\cap \{1,2,\dots ,p\}.$$ We observe that $S$ is closed in multiplication mod $p^2$: if $a,b\in S$ and $ab\equiv c(\mathrm{mod}{p}^2)$ then $c\in S$.

Lemma 1. We have $|S|\le p-1$.

Proof. (Note: actually we have $|S|=p-1$ and there are several ways to show this - applying the Hensel's lemma, or utilizing the existence of primitive root mod $p^2$ etc.. We give a self-contained proof.) If $a,b\in S$ and $a\equiv b(\mathrm{mod}p)$, then we have $$p^2|a^{p-1}-b^{p-1}=(a-b)(a^{p-2}+a^{p-3}b+\cdots +b^{p-2}).$$ But as $$a^{p-2}+a^{p-3}b+\cdots +b^{p-2}\equiv (p-1)a^{p-2}(\mathrm{mod}p)$$ is not divisible by $p$, this implies $p^2|a-b$, so $a=b$. This shows that elements of $S$ are all distinct mod $p$, and obviously $S$ does not contain multiples of $p$, so $|S|\le p-1$. $\square$

We start from $$S_p\cdot S_p=\{ab:a,b\in S_p\}\subset S.$$ If we consider the map $S_p\times S_p\to S_p\cdot S_p$ given as $(a,b)\mapsto ab$, preimage of an element $m\in S_p\cdot S_p$ is of size at most $\tau (m)$ (number of divisors of $m$), as $a$ should satisfy $a|m$ and $b$ is then uniquely determined. Thus it follows that $$M|S_p\cdot S_p|\ge |S_p\times S_p|=|S_p{|}^2,M=\underset{1\le m\le p^2}{\max }\tau (m)$$ and we have $$\frac{1}{M}|S_p{|}^2\le |S_p\cdot S_p|\le |S|<p\Rightarrow |S_p|<\sqrt{pM}.$$

Meanwhile, we bound $M$ using the following lemma.

Lemma 2. For any $ϵ>0$, there exists a constant $C_{ϵ}>0$ such that $$\tau (n)<C_{ϵ}{n}^{ϵ}$$ for any positive integer $n$.

Proof. Write $n=\prod p^{e_p}$ be the prime factorization of $n$. Then we have $$\frac{\tau (n)}{n^{ϵ}}=\prod _p\frac{e_p+1}{(p^{ϵ}{)}^{e_p}}$$ The sequence $(\frac{e+1}{k^{ϵ}}{)}_e$ increases if and only if $\frac{e+2}{k}>e+1$, or equivalently $e+1<\frac{1}{k-1}$. Thus if $k\ge 2$ then this sequence always decreases, so its maximum is obtained at $e=0$, which is 1. If $1<k<2$ then this sequence increases if $e<\frac{2-k}{1-k}$ and decreases if $e>\frac{2-k}{1-k}$, so it obtains maximum at $e=\left[\frac{2-k}{1-k}\right]$. Denote this maximum as $F(k)$, then we have $$\frac{\tau (n)}{n^{ϵ}}\le \prod _{p\le 2^{1/ϵ}}\frac{e_p+1}{(p^{ϵ}{)}^{e_p}}=\prod _{p\le 2^{1/ϵ}}F(p^{ϵ})$$ so we can set $C_{ϵ}>0$ as any constant larger than that.

Using this lemma gives $M<C_{1/3}{p}^{2/3}$, which shows $$|S_p|<\sqrt{pM}<\sqrt{p\cdot C_{1/3}{p}^{2/3}}=\sqrt{C_{1/3}{p}^{5/6}}$$ Now pick $K$ such that $p>K$ implies $\sqrt{C_{1/3}{p}^{5/6}}<p/2^{2024}$, thus $|S_p|<p/2^{2024}$.