# Difference between revisions of "2019 AIME I Problems/Problem 14"

## Problem 14

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

## Solution 1

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}$.

### Note to solution 1

$\phi(p)$ is called the "Euler Function" of integer $p$. Eular theorem: define $\phi(p)$ as the number of positive integers less than $n$ but relatively prime to $n$, then we have $$\phi(p)=p\cdot \prod^n_{i=1}(1-\frac{1}{p_i})$$ where $p_1,p_2,...,p_n$ are the prime factors of $p$. Then, we have $$a^{\phi(p)} \equiv 1\ (\mathrm{mod}\ p)$$ if $(a,p)=1$.

## Video Solution

On The Spot STEM: