# 2019 AIME I Problems/Problem 14

## Problem 14

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

## Solution

We know 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 find $2019^{16} \equiv 1 \pmod{p}$.

Since $2019^{16} \equiv 1 \pmod{p}$, the order of $2019$ modulo $p$ is a positive divisor of $16$.

However, if the order of $2019$ modulo $p$ is $1, 2, 4,$ or $8,$ then $2019^8$ will be equivalent to $1 \pmod{p},$ which contradicts the given requirement that $2019^8\equiv -1\pmod{p}$.

Therefore, the order of $2019$ modulo $p$ is $16$. Because all orders modulo $p$ divide $\phi(p)$, we see that $\phi(p)$ is a multiple of $16$. As $p$ is prime, $\phi(p) = p\left(1 - \dfrac{1}{p}\right) = p - 1$. Therefore, $p\equiv 1 \pmod{16}$. The two smallest primes equivalent to $1 \pmod{16}$ are $17$ and $97$. As $2019^8 \not\equiv -1 \pmod{17}$ and $2019^8 \equiv -1 \pmod{97}$, the smallest possible $p$ is thus $\boxed{097}$.

### Note to solution

$\phi(p)$ is the Euler Totient Function of integer $p$. Euler's Totient Theorem: define $\phi(p)$ as the number of positive integers less than $p$ but relatively prime to $p$. We have $$\phi(p)=p\cdot \prod^n_{i=1}\left(1-\dfrac{1}{p_i}\right)$$ where $p_1,p_2,...,p_n$ are the prime factors of $p$. Then, we have $$a^{\phi(p)} \equiv 1\pmod p$$ if $\gcd(a,p)=1$.

Furthermore, the order $a$ modulo $n$ for an integer $a$ relatively prime to $n$ is defined as the smallest positive integer $d$ such that $a^{d} \equiv 1\pmod n$. An important property of the order $d$ is that $d|\phi(n)$.

## Video Solution

On The Spot STEM:

## See Also

 2019 AIME I (Problems • Answer Key • Resources) Preceded byProblem 13 Followed byProblem 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.

Invalid username
Login to AoPS