Maths Olympiad Prep

Library / /456 of 860

Number theory Difficulty 5.2 AIME, harder Find the answer

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

A number or a short expression. Spacing and $ signs are ignored.

Solution

In order for cn0c_{n} \neq 0, we must have gcd(n,210)=1\operatorname{gcd}(n, 210)=1, so we need only consider such nn. The number ncn1n^{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 nn modulo each modulus separately; cnc_{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 a{1,2}mod3a \in\{1,2\} \bmod 3, b{1,2,4,4}mod5b \in\{1,2,4,4\} \bmod 5, c{1,2,3,3,6,6}mod7c \in\{1,2,3,3,6,6\} \bmod 7. By the Chinese Remainder Theorem, each triplet of choices from these three multisets occurs for exactly one nn in the range {1,2,,210}\{1,2, \ldots, 210\}, so the answer we seek is the sum of lcm(a,b,c)\operatorname{lcm}(a, b, c) over a,b,ca, b, c in the Cartesian product of these multisets. For a=1a=1 this table of LCMs is as follows: 123366112336622266664441212121244412121212\begin{array}{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{array} which has a sum of 21+56+28+56=16121+56+28+56=161. The table for a=2a=2 is identical except for the top row, where 1,3,31,3,3 are replaced by 2,6,62,6,6, and thus has a total sum of 7 more, or 168. So our answer is 161+168=329161+168=329.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.