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

m (Note to solution)
(Video Solution)
Line 26: Line 26:
  
 
https://youtu.be/IF88iO5keFo
 
https://youtu.be/IF88iO5keFo
 +
 +
==Solution 2(basbhbashabsbhbasbasbhasbhsabhasbhbhasbhbash)==
 +
1. Take remainder of prime <math>p</math>
 +
 +
2. Take that to the power of <math>8</math>, mod <math>p</math>
 +
 +
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 <math>\boxed{097}</math>
 +
-Trex4days
  
 
==See Also==
 
==See Also==
 
{{AIME box|year=2019|n=I|num-b=13|num-a=15}}
 
{{AIME box|year=2019|n=I|num-b=13|num-a=15}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 00:40, 4 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 Function" of integer $p$. Euler 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 $(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

See Also

2019 AIME I (ProblemsAnswer KeyResources)
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

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png