PMO Area Stage

Solution:

Answer: 996

The function $\varphi$ is the well-known Euler totient function which satisfies the property
$$\frac{\varphi(n)}{n}=\prod_{\substack{p \mid n \\ p \text{ prime }}}\left(1-\frac{1}{p}\right)$$
for any integer $n>2$. Note that the problem defines $\varphi(1)=0$.

For any $k \in \mathbb{N}$, the number $42^{k}$ has $(k+1)^{3}$ factors, each of which takes the form $2^{a} 3^{b} 7^{c}$ where $a, b, c \in\{0,1,2, \ldots, k\}$. Since $\varphi(n) / n$ depends only on the prime factors of $n$, we partition this set of factors into 8 forms with the same value for $\varphi(n) / n$.

Hence, the problem wants us to find the largest $k<10^{3}$ so that $a(k) \equiv 0\ (\bmod\ 42)$, or equivalently, $a(k) \equiv 0\ (\bmod\ 2)$, $a(k) \equiv 0\ (\bmod\ 3)$, and $a(k) \equiv 0\ (\bmod\ 7)$. Observe that

- $a(k) \equiv k\ (\bmod\ 2)$, which is 0 iff $k$ is even.
- $a(k) \equiv k+2k^{2}\ (\bmod\ 3)$, which is 0 iff $k \equiv 0$ or $1\ (\bmod\ 3)$
- $a(k) \equiv k+5k^{3}\ (\bmod\ 7)$, which is 0 iff $k \equiv 0,2$, or $5\ (\bmod\ 7)$.

The numbers 999 and 997 are not even. $998 \equiv 2\ (\bmod\ 3)$. 996 is even, $\equiv 0\ (\bmod\ 3)$, and $\equiv 2\ (\bmod\ 7)$. Therefore, the answer is 996.