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

(Solution 2(basbhbashabsbhbasbasbhasbhsabhasbhbhasbhbash))
(Solution)
Line 4: Line 4:
 
==Solution==
 
==Solution==
  
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>.   
+
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>, <math>ord_p(2019)</math> = <math>1, 2, 4, 8,</math> or <math>16</math>
+
Since <math>2019^{16} \equiv 1 \pmod{p}</math>, the order of <math>2019</math> modulo <math>p</math> is <math>1, 2, 4, 8,</math> or <math>16</math>.
  
However, if <math>ord_p(2019)</math> = <math>1, 2, 4,</math> or <math>8,</math> then <math>2019^8</math> clearly will be <math>1 \pmod{p} </math> instead of <math>-1 \pmod{p}</math>, causing a contradiction.
+
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, <math>ord_p(2019) = 16</math>. Because <math>ord_p(2019)  \vert  \phi(p)</math>, <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{97}</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 16. As <math>p</math> is prime, <math>\phi(p) = p(1 - \frac{1}{p}) = p - 1</math>. Therefore, <math>p\equiv1 \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>, our answer is <math>\boxed{97}</math>.
  
 
===Note to solution===
 
===Note to solution===
<math>\phi(p)</math> is called the [[Euler Totient Function]] of integer <math>p</math>.
+
<math>\phi(k)</math> is the [[Euler Totient Function]] of integer <math>k</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>.
 
[[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>.
+
Furthermore, the order <math>a</math> modulo <math>n</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\pmod n</math>. An important property of the order <math>d</math> is that <math>d|\phi(n)</math>.
  
 
==Video Solution==
 
==Video Solution==

Revision as of 20:09, 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 $1, 2, 4, 8,$ or $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(1 - \frac{1}{p}) = p - 1$. Therefore, $p\equiv1 \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}$, our answer is $\boxed{97}$.

Note to solution

$\phi(k)$ is the Euler Totient Function of integer $k$. 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, 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

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