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

(Solution)
Line 2: Line 2:
 
Find the least odd prime factor of <math>2019^8+1</math>.
 
Find the least odd prime factor of <math>2019^8+1</math>.
  
==Solution==
+
==Solution 1==
  
 
The problem tells us 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 get <math>2019^{16} \equiv 1 \pmod{p}</math>. This tells us that <math>\phi(p)</math> is a multiple of 16. Since we know <math>p</math> is prime, <math>\phi(p) = p(1 - \frac{1}{p})</math> or <math>p - 1</math>. Therefore, <math>p</math> must be <math>1 \pmod{16}</math>. The two smallest primes that are <math>1 \pmod{16}</math> are <math>17</math> and <math>97</math>. <math>2019^8 \not\equiv -1 \pmod{17}</math>, but <math>2019^8 \equiv -1 \pmod{97}</math>, so our answer is <math>\boxed{097}</math>.
 
The problem tells us 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 get <math>2019^{16} \equiv 1 \pmod{p}</math>. This tells us that <math>\phi(p)</math> is a multiple of 16. Since we know <math>p</math> is prime, <math>\phi(p) = p(1 - \frac{1}{p})</math> or <math>p - 1</math>. Therefore, <math>p</math> must be <math>1 \pmod{16}</math>. The two smallest primes that are <math>1 \pmod{16}</math> are <math>17</math> and <math>97</math>. <math>2019^8 \not\equiv -1 \pmod{17}</math>, but <math>2019^8 \equiv -1 \pmod{97}</math>, so our answer is <math>\boxed{097}</math>.
 +
 +
==Note to solution 1==
 +
<math>\phi(p)</math> is called the "Euler Function" of integer <math>p</math>.
 +
Eular theorem: define <math>\phi(p)</math> as the number of positive integers less than <math>n</math> but relatively prime to <math>n</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>(a,p)=1</math>.
  
 
==Video Solution==
 
==Video Solution==

Revision as of 10:31, 15 March 2019

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}\)\] (Error compiling LaTeX. Unknown error_msg)

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:

https://youtu.be/_vHq5_5qCd8


https://youtu.be/IF88iO5keFo

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