2019 AIME I Problems/Problem 14

Revision as of 19:40, 14 March 2019 by Vvluo (talk | contribs) (Solution 2 the above is much better)

The 2019 AIME I takes place on March 13, 2019.

Problem 14

Find the least odd prime factor of $2019^8 + 1$.

Solution 2 the solution in the chat is better and should be sol 1

Essentially, we are trying to find the smallest prime p such that $2019^8 \equiv -1 (\mod p)$. This congruence tells us that $2019^{16} \equiv 1 (\mod p)$. 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 $\phi(p)$, which is just p-1 because p is prime.Thus, we have $16|p-1$. Now, we just test up. 17 does not work, because $2019^8 +1$ reduces to 2 modulo 17. The reason this does not work is because $2019^8$ 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 $2019^8 \equiv (-18)^8 \equiv 324^4 \equiv 33^4 \equiv 1089^2 \equiv 22^2 \equiv 96 (\mod 97)$. Thus $2019^8 +1 \equiv 0 (\mod\boxed{97})$.

See Also

2019 AIME I (ProblemsAnswer KeyResources)
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. AMC logo.png