Difference between revisions of "2006 iTest Problems/Problem 34"
Duck master (talk | contribs) m (fixed Category: Number Theory Problem") |
Duck master (talk | contribs) m (fixed links) |
||
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 | + | 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 == |
Latest revision as of 18:04, 13 September 2020
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
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.
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 |