2019 AIME I Problems/Problem 14
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.