2006 iTest Problems/Problem 34

For each positive integer $n$ let $S_n$ denote the set of positive integers $k$ such that $n^k-1$ is divisible by $2006$ . Define the function $P(n)$ by the rule $P(n):=\begin{cases}\min(s)_{s\in S_n}&\text{if }S_n\neq\emptyset,\\0&\text{otherwise}.\end{cases}$ Let $d$ be the least upper bound of $\{P(1),P(2),P(3),\ldots\}$ and let $m$ be the number of integers $i$ such that $1\leq i\leq 2006$ and $P(i) = d$ . Compute the value of $d+m$ .

Solution 1

We find that the prime factorization of $2006$ is $2*17*59$ .

Then we can compute $d = \lambda(2006)$ (where $\lambda$ is the Carmichael function) by Carmichael's theorem: it is $\text{lcm}(\lambda(2), \lambda(17), \lambda(59)) = \text{lcm}(1, 16, 58) = 2^4 * 29 = 464$ .

As for solving $P(i) = d$ , we must have $i$ odd (otherwise it would not be coprime to $2$ ), and we must also have $i$ be a primitive root modulo $17$ as well as a primitive root modulo $59$ . There are $\phi(\phi(17)) = \phi(16) = 8$ primitive roots modulo $17$ (where $\phi$ is the Euler totient function) and $\phi(\phi(59)) = \phi(58) = (2-1)*(29-1) = 28$ primitive roots modulo $59$ . Then we have $m = 1 * 8 * 28 = 224$ by the Chinese Remainder Theorem, so our answer is $d + m = 464 + 224 = 688$ and we are done.

Solution 2 (No Carmichael function)

First note $2006 = 2 \cdot 17 \cdot 59$ If $ \gcd(n, 2006) \neq 1 $ then for some prime divisor $ p $ of 2006 we have $ n^k \equiv 0 \pmod{p} $ for all $ k $, so $ n^{k-1} \not\equiv 0 \pmod{p} $; hence $ S_n $ is empty unless $ \gcd(n, 2006) = 1 $. For $ \gcd(n, 2006) = 1 $ write $a = \text{ord}_{17}(n), \quad b = \text{ord}_{59}(n).$ By the Chinese Remainder Theorem the minimal $ k $ with $ n^k \equiv 1 \pmod{2006} $ is $ P(n) = \text{lcm}(a, b) $. Fermat gives $ a \mid 16 $ and $ b \mid 58 $, so every $ P(n) $ divides $ \text{lcm}(16, 58) = 464 $; thus the least upper bound $ d \leq 464 $.

We can attain $ a = 16 $ and $ b = 58 $ because the multiplicative groups modulo the primes 17 and 59 are cyclic of orders 16 and 58: there exist residues of full order modulo 17 and modulo 59, and by CRT these choices lift to residues modulo 2006. Hence $ d = 464 $.

To count how many $ i $ with $ 1 \leq i \leq 2006 $ satisfy $ P(i) = 464 $, count pairs of residues $ (r_{17}, r_{59}) $ where $ \text{ord}_{17}(r_{17}) = 16 $ and $ \text{ord}_{59}(r_{59}) = 58 $. For a cyclic group of order $ t $ the number of elements of order $ t $ is $ \phi(t) $. Thus there are $ \phi(16) = 8 $ choices mod 17 and $ \phi(58) = \phi(2) \phi(29) = 1 \cdot 28 = 28 $ choices mod 59. The condition mod 2 is just that $ i $ is odd (automatically true for any residue coprime to 2006), and CRT makes the choices independent, so $m = 8 \cdot 28 = 224.$ Therefore $ d + m = 464 + 224 = 688 $.

$\boxed{688}$

~Pinotation

2006 iTest (Problems, Answer Key)
Preceded by: Problem 33	Followed by: Problem 35
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30 • 31 • 32 • 33 • 34 • 35 • 36 • 37 • 38 • 39 • 40 • U1 • U2 • U3 • U4 • U5 • U6 • U7 • U8 • U9 • U10

Page

Toolbox

Search

2006 iTest Problems/Problem 34

Solution 1

Solution 2 (No Carmichael function)

See also