HMMT-Feb 2016 team, Problem 2

For positive integers $n$, let $c_{n}$ be the smallest positive integer for which $n^{c_{n}}-1$ is divisible by 210 , if such a positive integer exists, and $c_{n}=0$ otherwise. What is $c_{1}+c_{2}+\cdots+c_{210}$ ?

Solution: In order for $c_{n} \neq 0$, we must have $\operatorname{gcd}(n, 210)=1$, so we need only consider such $n$. The number $n^{c_{n}}-1$ is divisible by 210 iff it is divisible by each of $2,3,5$, and 7 , and we can consider the order of $n$ modulo each modulus separately; $c_{n}$ will simply be the LCM of these orders. We can ignore the modulus 2 because order is always 1 . For the other moduli, the sets of orders are \[ \begin{aligned} a \in\{1,2\} & \bmod 3 \\ b \in\{1,2,4,4\} & \bmod 5 \\ c \in\{1,2,3,3,6,6\} & \bmod 7 \end{aligned} \] By the Chinese Remainder Theorem, each triplet of choices from these three multisets occurs for exactly one $n$ in the range $\{1,2, \ldots, 210\}$, so the answer we seek is the sum $\operatorname{lcm}(a, b, c)$ over $a, b, c$ in the Cartesian product of these multisets. For $a=1$ this table of LCMs is as follows: \begin{center} \begin{tabular}{ccccccc}  & 1 & 2 & 3 & 3 & 6 & 6 \\ \hline 1 & 1 & 2 & 3 & 3 & 6 & 6 \\ 2 & 2 & 2 & 6 & 6 & 6 & 6 \\ 4 & 4 & 4 & 12 & 12 & 12 & 12 \\ 4 & 4 & 4 & 12 & 12 & 12 & 12 \\ \end{tabular} \end{center} which has a sum of $21+56+28+56=161$. The table for $a=2$ is identical except for the top row, where $1,3,3$ are replaced by $2,6,6$, and thus has a total sum of 7 more, or 168 . So our answer is $161+168=\mathbf{3 2 9}$. This can also be computed by counting how many times each LCM occurs: \begin{itemize}   \item 12 appears 16 times when $b=4$ and $c \in\{3,6\}$, for a contribution of $12 \times 16=192$;   \item 6 appears 14 times, 8 times when $c=6$ and $b \leq 2$ and 6 times when $c=3$ and $(a, b) \in$ $\{(1,2),(2,1),(2,2)\}$, for a contribution of $6 \times 14=84$;   \item 4 appears 8 times when $b=4$ and $a, c \in\{1,2\}$, for a contribution of $4 \times 8=32$;   \item 3 appears 2 times when $c=3$ and $a=b=1$, for a contribution of $3 \times 2=6$;   \item 2 appears 7 times when $a, b, c \in\{1,2\}$ and $(a, b, c) \neq(1,1,1)$, for a contribution of $2 \times 7=14$;   \item 1 appears 1 time when $a=b=c=1$, for a contribution of $1 \times 1=1$. \end{itemize} The result is again $192+84+32+6+14+1=329$. $\fbox{329}$.

Answer: 329