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

(Note to solution)
(Note to solution)
Line 13: Line 13:
  
 
===Note to solution===
 
===Note to solution===
<math>\phi(k)</math> is the [[Euler Totient Function]] of integer <math>k</math>. <math>\phi(k)</math> is the number of positive integers less than <math>k</math> relatively prime to <math>k</math>. Define the numbers <math>k_1,k_2,k_3,\cdots,k_n</math> to be the prime factors of <math>k</math>. Then, we have <cmath>\phi(k)=k\cdot \prod^n_{i=1}\left(1-\dfrac{1}{k_i}\right).</cmath> A property of the Totient function is that, for any prime <math>p</math>, <math>\phi(p)=p-1</math>.
+
<math>\phi(k)</math> is the Euler Totient Function of integer <math>k</math>. <math>\phi(k)</math> is the number of positive integers less than <math>k</math> relatively prime to <math>k</math>. Define the numbers <math>k_1,k_2,k_3,\cdots,k_n</math> to be the prime factors of <math>k</math>. Then, we have<cmath>\phi(k)=k\cdot \prod^n_{i=1}\left(1-\dfrac{1}{k_i}\right).</cmath>A property of the Totient function is that, for any prime <math>p</math>, <math>\phi(p)=p-1</math>.
  
[[Euler's Totient Theorem]] states that <cmath>a^{\phi(k)} \equiv 1\pmod k</cmath> if <math>\gcd(a,k)=1</math>.
+
Euler's Totient Theorem states that<cmath>a^{\phi(k)} \equiv 1\pmod k</cmath>if <math>\gcd(a,k)=1</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>.
 
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>.

Revision as of 10:38, 19 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(k)$ is the Euler Totient Function of integer $k$. $\phi(k)$ is the number of positive integers less than $k$ relatively prime to $k$. Define the numbers $k_1,k_2,k_3,\cdots,k_n$ to be the prime factors of $k$. Then, we have\[\phi(k)=k\cdot \prod^n_{i=1}\left(1-\dfrac{1}{k_i}\right).\]A property of the Totient function is that, for any prime $p$, $\phi(p)=p-1$.

Euler's Totient Theorem states that\[a^{\phi(k)} \equiv 1\pmod k\]if $\gcd(a,k)=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

Invalid username
Login to AoPS