Difference between revisions of "2019 AIME I Problems/Problem 14"
|Line 48:||Line 48:|
Revision as of 15:41, 16 October 2020
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 .
Solution 2 (Basic Modular Arithmetic)
In this solution, will represent an arbitrary nonnegative integer.
We will show that any potential prime must be of the form through a proof by contradiction. Suppose that there exists some prime that can not be expressed in the form that is a divisor of . First, note that if the prime is a divisor of , then is a multiple of and is not. Thus, is not a divisor of .
Because is a multiple of , . This means that , and by raising both sides to an arbitrary odd positive integer, we have that .
Then, since the problem requires an odd prime, can be expressed as , where is an odd integer ranging from to , inclusive. By Fermat's Little Theorem, , and plugging in values, we get , where and is thus an even integer ranging from to , inclusive.
If , then , which creates a contradiction. If is not a multiple of but is a multiple of , squaring both sides of also results in the same contradictory equivalence. For all remaining , raising both sides of to the th power creates the same contradiction. (Note that and can both be expressed in the form .)
Since we have proved that no value of can work, this means that a prime must be of the form in order to be a factor of . The smallest prime of this form is , and testing it, we get so it does not work. The next smallest prime of the required form is , and testing it, we get so it works. Thus, the answer is . ~emerald_block
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|