Difference between revisions of "2019 AIME I Problems/Problem 14"
(→Note to solution) |
(→Note to solution) |
||
Line 13: | Line 13: | ||
===Note to solution=== | ===Note to solution=== | ||
− | <math>\phi(k)</math> is the | + | <math>\phi(k)</math> is the Euler Totient Function of integer <math>k</math>. <math>\phi(k)</math> is the number of positive integers less than <math>k</math> relatively prime to <math>k</math>. Define the numbers <math>k_1,k_2,k_3,\cdots,k_n</math> to be the prime factors of <math>k</math>. Then, we have<cmath>\phi(k)=k\cdot \prod^n_{i=1}\left(1-\dfrac{1}{k_i}\right).</cmath>A property of the Totient function is that, for any prime <math>p</math>, <math>\phi(p)=p-1</math>. |
− | + | Euler's Totient Theorem states that<cmath>a^{\phi(k)} \equiv 1\pmod k</cmath>if <math>\gcd(a,k)=1</math>. | |
Furthermore, the order <math>a</math> modulo <math>n</math> for an integer <math>a</math> relatively prime to <math>n</math> is defined as the smallest positive integer <math>d</math> such that <math>a^{d} \equiv 1\pmod n</math>. An important property of the order <math>d</math> is that <math>d|\phi(n)</math>. | Furthermore, the order <math>a</math> modulo <math>n</math> for an integer <math>a</math> relatively prime to <math>n</math> is defined as the smallest positive integer <math>d</math> such that <math>a^{d} \equiv 1\pmod n</math>. An important property of the order <math>d</math> is that <math>d|\phi(n)</math>. |
Revision as of 11:38, 19 May 2020
Problem 14
Find the least odd prime factor of .
Solution
We know that for some prime
. We want to find the smallest odd possible value of
. By squaring both sides of the congruence, we find
.
Since , the order of
modulo
is a positive divisor of
.
However, if the order of modulo
is
or
then
will be equivalent to
which contradicts the given requirement that
.
Therefore, the order of modulo
is
. Because all orders modulo
divide
, we see that
is a multiple of
. As
is prime,
. Therefore,
. The two smallest primes equivalent to
are
and
. As
and
, the smallest possible
is thus
.
Note to solution
is the Euler Totient Function of integer
.
is the number of positive integers less than
relatively prime to
. Define the numbers
to be the prime factors of
. Then, we have
A property of the Totient function is that, for any prime
,
.
Euler's Totient Theorem states thatif
.
Furthermore, the order modulo
for an integer
relatively prime to
is defined as the smallest positive integer
such that
. An important property of the order
is that
.
Video Solution
On The Spot STEM:
See Also
2019 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 13 |
Followed by Problem 15 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.