2019 AIME I Problems/Problem 14
Find the least odd prime factor of .
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 haveA 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 .
On The Spot STEM:
|2019 AIME I (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|