2019 AIME I Problems/Problem 14

Problem 14

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

Solution

The problem tells us that $2019^8 \equiv -1 \pmod{p}$ for some prime $p$ . We want to find the smallest odd possible value of $p$ . By squaring both sides of the congruence, we get $2019^16 \equiv 1 \pmod{p}$ . This tells us that $\phi(p)$ is a multiple of 16. Since we know $p$ is prime, $\phi(p) = p(1 - \frac{1}{p})$ or $p - 1$ . Therefore, $p$ must be $1 \pmod{16}$ . The two smallest primes that are $1 \pmod{16}$ are $17$ and $97$ . $2019^8 \not\equiv -1 \pmod{17}$ , but $2019^8 \equiv -1 \pmod{97}$ , so our answer is $\boxed{097}$ .

Video Solution

On The Spot STEM:

https://youtu.be/_vHq5_5qCd8

https://youtu.be/IF88iO5keFo

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

Page

Toolbox

Search

2019 AIME I Problems/Problem 14

Contents

Problem 14

Solution

Video Solution

See Also