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

Revision as of 17:55, 16 March 2020

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

Since $2019^{16} \equiv 1 \pmod{p}$ , $ord_p(2019)$ = $1, 2, 4, 8,$ or $16$

However, if $ord_p(2019)$ = $1, 2, 4,$ or $8,$ then $2019^8$ clearly will be $1 \pmod{p}$ instead of $-1 \pmod{p}$ , causing a contradiction.

Therefore, $ord_p(2019) = 16$ . Because $ord_p(2019) \vert \phi(p)$ , $\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{97}$ .

Note to solution

$\phi(p)$ is called 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$ , 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 $\gcd(a,p)=1$ .

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

Video Solution

On The Spot STEM:

https://youtu.be/_vHq5_5qCd8

https://youtu.be/IF88iO5keFo

Solution 2(basbhbashabsbhbasbasbhasbhsabhasbhbhasbhbash)

1. Take remainder of prime $p$

2. Take that to the power of $8$ , mod $p$

3. If it is congruent to 1, you are done

4. If not, repeat for next prime

5. Through 2 hours and 59 minutes of bashing, we arrive at the answer of $\boxed{097}$ -Trex4days

@@ Line 13: / Line 13: @@
 ===Note to solution===
-<math>\phi(p)</math> is called the "Euler Function" of integer <math>p</math>.
+<math>\phi(p)</math> is called the [[Euler Totient Function]] of integer <math>p</math>.
-Euler theorem: define <math>\phi(p)</math> as the number of positive integers less than <math>p</math> but relatively prime to <math>p</math>, then we have <cmath>\phi(p)=p\cdot \prod^n_{i=1}(1-\frac{1}{p_i})</cmath> where <math>p_1,p_2,...,p_n</math> are the prime factors of <math>p</math>. Then, we have <cmath>a^{\phi(p)} \equiv 1\ (\mathrm{mod}\ p)</cmath> if <math>\gcd(a,p)=1</math>.
+[[Euler's Totient Theorem]]: define <math>\phi(p)</math> as the number of positive integers less than <math>p</math> but relatively prime to <math>p</math>, then we have <cmath>\phi(p)=p\cdot \prod^n_{i=1}(1-\frac{1}{p_i})</cmath> where <math>p_1,p_2,...,p_n</math> are the prime factors of <math>p</math>. Then, we have <cmath>a^{\phi(p)} \equiv 1\ (\mathrm{mod}\ p)</cmath> if <math>\gcd(a,p)=1</math>.
 Furthermore, <math>ord_n(a)</math> for an integer <math>a</math> relatively prime to <math>n</math> is defined as the smallest positive integer <math>d</math> such that <math>a^{d} \equiv 1\ (\mathrm{mod}\ n)</math>. An important property of the order is that <math>ord_n(a)|\phi(n)</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