Difference between revisions of "2019 AIME I Problems/Problem 14"
Itsameyushi (talk | contribs) (→Solution 2 the solution in the chat is better and should be sol 1) |
Itsameyushi (talk | contribs) m (→Solution 2) |
||
| Line 5: | Line 5: | ||
==Solution 2== | ==Solution 2== | ||
| − | Essentially, we are trying to find the smallest prime p such that <math>2019^8 \equiv -1 (\mod p)</math>. This congruence tells us that <math>2019^{16} \equiv 1 (\mod p)</math>. Therefore, the order of 2019 modulo p is a divisor of 16, but not a divisor of 8. This tells us that the order of 2019 modulo p is exactly 16 since it is the only possibility. We know that the order of 2019 modulo p is a divisor of <math>\phi(p)</math>, which is just p-1 because p is prime.Thus, we have <math>16|p-1</math>. Now, we just test up. 17 does not work, because <math>2019^8 +1</math> reduces to 2 modulo 17. The reason this does not work is | + | Essentially, we are trying to find the smallest prime p such that <math>2019^8 \equiv -1 (\mod p)</math>. This congruence tells us that <math>2019^{16} \equiv 1 (\mod p)</math>. Therefore, the order of 2019 modulo p is a divisor of 16, but not a divisor of 8. This tells us that the order of 2019 modulo p is exactly 16 since it is the only possibility. We know that the order of 2019 modulo p is a divisor of <math>\phi(p)</math>, which is just p-1 because p is prime. Thus, we have <math>16|p-1</math>. Now, we just test up. 17 does not work, because <math>2019^8 +1</math> reduces to 2 modulo 17. The reason this does not work is that <math>2019^8</math> reduces to 1, not -1 modulo 17. Since, 33, 49, 65, and 81 are all composite, we are able to skip those cases. This brings us to 97, which gives |
<math>2019^8 \equiv (-18)^8 \equiv 324^4 \equiv 33^4 \equiv 1089^2 \equiv 22^2 \equiv 96 (\mod 97)</math>. | <math>2019^8 \equiv (-18)^8 \equiv 324^4 \equiv 33^4 \equiv 1089^2 \equiv 22^2 \equiv 96 (\mod 97)</math>. | ||
Thus <math>2019^8 +1 \equiv 0 (\mod\boxed{97})</math>. | Thus <math>2019^8 +1 \equiv 0 (\mod\boxed{97})</math>. | ||
Revision as of 20:25, 14 March 2019
The 2019 AIME I takes place on March 13, 2019.
Problem 14
Find the least odd prime factor of 
.
Solution 2
Essentially, we are trying to find the smallest prime p such that 
. This congruence tells us that 
. Therefore, the order of 2019 modulo p is a divisor of 16, but not a divisor of 8. This tells us that the order of 2019 modulo p is exactly 16 since it is the only possibility. We know that the order of 2019 modulo p is a divisor of 
, which is just p-1 because p is prime. Thus, we have 
. Now, we just test up. 17 does not work, because 
reduces to 2 modulo 17. The reason this does not work is that 
reduces to 1, not -1 modulo 17. Since, 33, 49, 65, and 81 are all composite, we are able to skip those cases. This brings us to 97, which gives
.
Thus 
.
also not the most rigorous(last part)
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. 
