Difference between revisions of "2019 AIME I Problems/Problem 14"
(→Solution) |
(→Note to solution) |
||
Line 13: | Line 13: | ||
===Note to solution=== | ===Note to solution=== | ||
− | <math>\phi( | + | <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 <math>\phi(k)=k\cdot \prod^n_{i=1}\left(1-\dfrac{1}{k_i}\right).</math><math> A property of the Totient function is that, for any prime </math>p<math>, </math>\phi(p)=p-1<math>. |
− | |||
− | Furthermore, the order <math>a< | + | [[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)$. | ||
==Video Solution== | ==Video Solution== |
Revision as of 19:22, 18 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 p\phi(p)=p-1$.
[[Euler's Totient Theorem]] states that <cmath>a^{\phi(k)} \equiv 1\pmod k</cmath> if$ (Error compiling LaTeX. ! Missing $ inserted.)\gcd(a,k)=1$.
Furthermore, the order$ (Error compiling LaTeX. ! Missing $ inserted.)ananda^{d} \equiv 1\pmod ndd|\phi(n)$.
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.