2006 iTest Problems/Problem 34

For each positive integer let denote the set of positive integers such that is divisible by . Define the function by the rule Let be the least upper bound of and let be the number of integers such that and . Compute the value of .

Solution 1

We find that the prime factorization of is .

Then we can compute (where is the Carmichael function) by Carmichael's theorem: it is .

As for solving , we must have odd (otherwise it would not be coprime to ), and we must also have be a primitive root modulo as well as a primitive root modulo . There are primitive roots modulo (where is the Euler totient function) and primitive roots modulo . Then we have by the Chinese Remainder Theorem, so our answer is and we are done.

Solution 2 (No Carmichael function)

First note 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 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 Therefore \( d + m = 464 + 224 = 688 \).

~Pinotation