Difference between revisions of "2006 iTest Problems/Problem 34"

(created page w/ solution & categorization)
 
m (fixed links)
 
(One intermediate revision by the same user not shown)
Line 7: Line 7:
 
Then we can compute <math>d = \lambda(2006)</math> (where <math>\lambda</math> is the [[Carmichael function]]) by Carmichael's theorem: it is <math>\text{lcm}(\lambda(2), \lambda(17), \lambda(59)) = \text{lcm}(1, 16, 58) = 2^4 * 29 = 464</math>.
 
Then we can compute <math>d = \lambda(2006)</math> (where <math>\lambda</math> is the [[Carmichael function]]) by Carmichael's theorem: it is <math>\text{lcm}(\lambda(2), \lambda(17), \lambda(59)) = \text{lcm}(1, 16, 58) = 2^4 * 29 = 464</math>.
  
As for solving <math>P(i) = d</math>, we must have <math>i</math> odd (otherwise it would not be coprime to <math>2</math>), and we must also have <math>i</math> be a primitive root modulo <math>17</math> as well as a primitive root modulo <math>59</math>. There are <math>\phi(\phi(17)) = \phi(16) = 8</math> primitive roots modulo <math>17</math> (where <math>\phi</math> is the [[Euler totient function]]) and <math>\phi(\phi(59)) = \phi(58) = (2-1)*(29-1) = 28</math> primitive roots modulo <math>59</math>. Then we have <math>m = 1 * 8 * 28 = 224</math> by the [[Chinese remainder theorem]], so our answer is <math>d + m = 464 + 224 = 688</math> and we are done.
+
As for solving <math>P(i) = d</math>, we must have <math>i</math> odd (otherwise it would not be coprime to <math>2</math>), and we must also have <math>i</math> be a primitive root modulo <math>17</math> as well as a primitive root modulo <math>59</math>. There are <math>\phi(\phi(17)) = \phi(16) = 8</math> primitive roots modulo <math>17</math> (where <math>\phi</math> is the [[Totient function|Euler totient function]]) and <math>\phi(\phi(59)) = \phi(58) = (2-1)*(29-1) = 28</math> primitive roots modulo <math>59</math>. Then we have <math>m = 1 * 8 * 28 = 224</math> by the [[Chinese Remainder Theorem]], so our answer is <math>d + m = 464 + 224 = 688</math> and we are done.
  
 
== See also ==
 
== See also ==
Line 13: Line 13:
 
{{iTest box|year=2006|num-b=33|num-a=35|ver=[[2006 iTest Problems/Problem U1|U1]] '''•''' [[2006 iTest Problems/Problem U2|U2]] '''•''' [[2006 iTest Problems/Problem U3|U3]] '''•''' [[2006 iTest Problems/Problem U4|U4]] '''•''' [[2006 iTest Problems/Problem U5|U5]] '''•''' [[2006 iTest Problems/Problem U6|U6]] '''•''' [[2006 iTest Problems/Problem U7|U7]] '''•''' [[2006 iTest Problems/Problem U8|U8]] '''•''' [[2006 iTest Problems/Problem U9|U9]] '''•''' [[2006 iTest Problems/Problem U10|U10]]}}
 
{{iTest box|year=2006|num-b=33|num-a=35|ver=[[2006 iTest Problems/Problem U1|U1]] '''•''' [[2006 iTest Problems/Problem U2|U2]] '''•''' [[2006 iTest Problems/Problem U3|U3]] '''•''' [[2006 iTest Problems/Problem U4|U4]] '''•''' [[2006 iTest Problems/Problem U5|U5]] '''•''' [[2006 iTest Problems/Problem U6|U6]] '''•''' [[2006 iTest Problems/Problem U7|U7]] '''•''' [[2006 iTest Problems/Problem U8|U8]] '''•''' [[2006 iTest Problems/Problem U9|U9]] '''•''' [[2006 iTest Problems/Problem U10|U10]]}}
  
[[Category:iTest]] [[Category:Number Theory Problem]]
+
[[Category:iTest]] [[Category:Number Theory Problems]]

Latest revision as of 17:04, 13 September 2020

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

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.

See also

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