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

Revision as of 19:16, 18 May 2020

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:

https://youtu.be/_vHq5_5qCd8

https://youtu.be/IF88iO5keFo

@@ Line 5: / Line 5: @@
 We know that <math>2019^8 \equiv -1 \pmod{p}</math> for some prime <math>p</math>. We want to find the smallest odd possible value of <math>p</math>. By squaring both sides of the congruence, we find <math>2019^{16} \equiv 1 \pmod{p}</math>.
 Since <math>2019^{16} \equiv 1 \pmod{p}</math>, the order of <math>2019</math> modulo <math>p</math> is a positive divisor of <math>16</math>.
 However, if the order of <math>2019</math> modulo <math>p</math> is <math>1, 2, 4,</math> or <math>8,</math> then <math>2019^8</math> will be equivalent to <math>1 \pmod{p},</math> which contradicts the given requirement that <math>2019^8\equiv -1\pmod{p}</math>.
 Therefore, the order of <math>2019</math> modulo <math>p</math> is <math>16</math>. Because all orders modulo <math>p</math> divide <math>\phi(p)</math>, we see that <math>\phi(p)</math> is a multiple of <math>16</math>. As <math>p</math> is prime, <math>\phi(p) = p\left(1 - \dfrac{1}{p}\right) = p - 1</math>. Therefore, <math>p\equiv 1 \pmod{16}</math>. The two smallest primes equivalent to <math>1 \pmod{16}</math> are <math>17</math> and <math>97</math>. As <math>2019^8 \not\equiv -1 \pmod{17}</math> and <math>2019^8 \equiv -1 \pmod{97}</math>, the smallest possible <math>p</math> is thus <math>\boxed{097}</math>.

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