AoPS - Problem

Source: Vietnam Mathematical Olympiad 2022 problem 4 day 1

Tags: vmo, number theory, Divisibility

799786

04.03.2022 13:31

For every pair of positive integers $(n,m)$ with $n<m$, denote $s(n,m)$ be the number of positive integers such that the number is in the range $[n,m]$ and the number is coprime with $m$. Find all positive integers $m\ge 2$ such that $m$ satisfy these condition: i) $\frac{s(n,m)}{m-n} \ge \frac{s(1,m)}{m}$ for all $n=1,2,...,m-1$; ii) $2022^m+1$ is divisible by $m^2$

Pardon me if I'm extremely tired, but here's what I think is a solution. Let $p>2$ be the smallest prime dividing $m$ (clearly $2^2\nmid 2022^n+1$). Thus, we get that \[\frac{s(1,m)-(p-1)}{m-p}=\frac{s(p,m)}{m-p}\geq\frac{s(1,m)}m\]Upon rearranging, we get \[m(p-1)\geq p\varphi(m)=ps(1,m)\geq m(p-1)\]Thus, all inequalities are equalities, so $m=p^k$ for some $k$. We know that \[-1\equiv 2022^{p^k}\equiv 2022^1\equiv 2022\pmod p\]as $p^k\equiv 1\pmod{p-1}$. Thus, we get $p\mid 2023$, so $p=7$ or $p=17$. If $p=7$, we get \[7^k\mid 2022^{7^k}+1\]which is true by Lifting the Exponent. Similarly, \[17^k\mid 2022^{17k}+1\]by LTE, showing all such numbers are either powers of $7$ or $17$.