HMMT February

The maximum order of an element modulo $n$ is the Carmichael function, denoted $\lambda(n)$. The following properties of the Carmichael function are established: - For primes $p>2$ and positive integers $k, \lambda\left(p^{k}\right)=(p-1) p^{k-1}$. - For a positive integer $k$, $$\lambda\left(2^{k}\right)= \begin{cases}2^{k-2} & \text { if } k \geq 3 \\ 2^{k-1} & \text { if } k \leq 2\end{cases}$$ - For a positive integer $n$ with prime factorization $n=\prod p_{i}^{k_{i}}$, $$\lambda(n)=\operatorname{lcm}\left(\lambda\left(p_{1}^{k_{1}}\right), \lambda\left(p_{2}^{k_{2}}\right), \ldots\right)$$ Meanwhile, for $n=\prod p_{i}^{k_{i}}$, we have $\varphi(n)=\prod\left(p_{i}-1\right) p_{i}^{k_{i}-1}$. Hence the intuition is roughly that the $\left(p_{i}-1\right) p_{i}^{k_{i}-1}$ terms must share divisors in order to reach a high value of $\frac{\varphi(n)}{\lambda(n)}$. We will now show that $n \geq 240$ by doing casework on the prime divisors of $z=\frac{\varphi(n)}{\lambda(n)}$. Suppose $p \mid z$ and $p>2$. This requires two terms among $\lambda\left(p_{1}^{k_{1}}\right), \lambda\left(p_{2}^{k_{2}}\right), \ldots$ to be multiples of $p$ because $\lambda(n)$ is the lcm of the terms whereas the product of these numbers has the same number of factors of $p$ as $\varphi(n)$ (note that this does not hold for $p=2$ because $\lambda\left(2^{k}\right) \neq 2^{k-1}$ in general). These correspond to either $p^{2} \mid n$ or $q \mid n$ with $q \equiv 1(\bmod p)$. Therefore $$n \geq \max \left(p^{2}(2 p+1),(2 p+1)(4 p+1)\right)$$ because the smallest primes congruent to $1(\bmod p)$ are at least $2 p+1$ and $4 p+1$. For $p \geq 5$ this gives $n>240$, so we may assume $p \leq 3$. First we address the case $p=3$. This means that two numbers among $9,7,13,19,31,37, \ldots$ divide $n$. As $7 \times 37>240$, we discard primes greater than 31. Of the remaining numbers, we have $$\lambda(9)=6, \lambda(7)=6, \lambda(13)=12, \lambda(19)=18, \lambda(31)=30$$ No candidate value of $n$ is the product of just two of these numbers as the gcd of any two of the associated $\lambda$ values is at most 6. Furthermore, multiplying by just 2 will not affect $\varphi(n)$ or $\lambda(n)$, so we must multiply at least two of these numbers by a number greater than 2. Throwing out numbers greater than 240, this leaves only $3 \times 9 \times 7$, which does not work. (A close candidate is $3 \times 7 \times 13=273$, for which $\varphi(n)=144, \lambda(n)=12$.) The remaining case is when the only prime divisors of $\frac{\varphi(n)}{\lambda(n)}$ are 2. It is not hard to see that $\lambda(n) \geq 4$ when $n \nmid 24$ (and when $n \mid 24$ it's clear that $\phi(n) \leq 8$, so we do not need to consider them). When $\lambda(n)=4$, we need $\varphi(n) \geq 4 \cdot 2^{4}=64$ and $v_{2}(n) \leq 4$, so the smallest such integer is $n=2^{4} \cdot 3 \cdot 5=240$, which we can check does indeed satisfy $\frac{\varphi(n)}{\lambda(n)}>10$. It is not difficult to check that higher values of $\lambda(n)$ will not yield any $n$ below 240, so 240 is indeed the smallest possible $n$. Note: The sequence $\frac{\varphi(n)}{\lambda(n)}$ is given by A034380 in the OEIS.