Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Video Solution)
(→‎Video Solution)
 
(29 intermediate revisions by 14 users not shown)
Line 1: Line 1:
−
==Problem 14==
+
==Problem==
 
Find the least odd prime factor of <math>2019^8+1</math>.
 
Find the least odd prime factor of <math>2019^8+1</math>.
 +
==Video Solution & More by MegaMath==
 +
https://www.youtube.com/watch?v=E6Vs5uf49Fc
  
 
==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 a positive divisor of <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 <math>16</math>. As <math>p</math> is prime, <math>\phi(p) = p\left(1 - \dfrac{1}{p}\right) = p - 1</math>. Therefore, <math>p\equiv 1 \pmod{16}</math>. The two smallest primes equivalent to <math>1 \pmod{16}</math> are <math>17</math> and <math>97</math>. Because <math>16 | p - 1</math>, and <math> p - 1  \geq 16</math>, each possible value of <math>p</math> must be verified by manual calculation to make sure that <math>p | 2019^8+1</math>. As <math>2019^8 \not\equiv -1 \pmod{17}</math> and <math>2019^8 \equiv -1 \pmod{97}</math>, the smallest possible <math>p</math> is thus <math>\boxed{097}</math>.
  
 
===Note to solution===
 
===Note to solution===
−
<math>\phi(p)</math> is called the "Euler Function" of integer <math>p</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 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>(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>.
+
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>.
 +
 
 +
==Solution 2 (Basic Modular Arithmetic)==
 +
 
 +
In this solution, <math>k</math> will represent an arbitrary nonnegative integer.
 +
 
 +
We will show that any potential prime <math>p</math> must be of the form <math>16k+1</math> through a proof by contradiction. Suppose that there exists some prime <math>p</math> that can not be expressed in the form <math>16k+1</math> that is a divisor of <math>2019^8+1</math>. First, note that if the prime <math>p</math> is a divisor of <math>2019</math>, then <math>2019^8</math> is a multiple of <math>p</math> and <math>2019^8+1</math> is not. Thus, <math>p</math> is not a divisor of <math>2019</math>.
 +
 
 +
Because <math>2019^8+1</math> is a multiple of <math>p</math>, <math>2019^8+1\equiv0\pmod{p}</math>. This means that <math>2019^8\equiv-1\pmod{p}</math>, and by raising both sides to an arbitrary odd positive integer, we have that <math>2019^{16k+8}\equiv-1\pmod{p}</math>.
 +
 
 +
Then, since the problem requires an odd prime, <math>p</math> can be expressed as <math>16k+m</math>, where <math>m</math> is an odd integer ranging from <math>3</math> to <math>15</math>, inclusive. By Fermat's Little Theorem, <math>2019^{p-1}\equiv1\pmod{p}</math>, and plugging in values, we get <math>2019^{16k+n}\equiv1\pmod{p}</math>, where <math>n=m-1</math> and is thus an even integer ranging from <math>2</math> to <math>14</math>, inclusive.
 +
 
 +
If <math>n=8</math>, then <math>2019^{16k+8}\equiv1\pmod{p}</math>, which creates a contradiction. If <math>n</math> is not a multiple of <math>8</math> but is a multiple of <math>4</math>, squaring both sides of <math>2019^{16k+n}\equiv1\pmod{p}</math> also results in the same contradictory equivalence. For all remaining <math>n</math>, raising both sides of <math>2019^{16k+n}\equiv1\pmod{p}</math> to the <math>4</math>th power creates the same contradiction. (Note that <math>32k</math> and <math>64k</math> can both be expressed in the form <math>16k</math>.)
 +
 
 +
Since we have proved that no value of <math>n</math> can work, this means that a prime must be of the form <math>16k+1</math> in order to be a factor of <math>2019^8+1</math>. The smallest prime of this form is <math>17</math>, and testing it, we get
 +
<cmath>2019^8+1\equiv13^8+1\equiv169^4+1\equiv(-1)^4+1\equiv1+1\equiv2\pmod{17},</cmath>
 +
so it does not work. The next smallest prime of the required form is <math>97</math>, and testing it, we get
 +
<cmath>2019^8+1\equiv(-18)^8+1\equiv324^4+1\equiv33^4+1\equiv1089^2+1\equiv22^2+1\equiv484+1\equiv-1+1\equiv0\pmod{97},</cmath>
 +
so it works. Thus, the answer is <math>\boxed{097}</math>. ~[[User:emerald_block|emerald_block]]
 +
 
 +
==Solution 3 (Official MAA)==
 +
Suppose prime <math>p>2</math> divides <math>2019^8+1.</math> Then <math>2019^8\equiv -1\pmod p.</math> Squaring gives <math>2019^{16}\equiv 1\pmod p.</math> If <math>2019^m\equiv 1 \pmod p</math> for some <math>0<m<16,</math> it follows that <cmath>2019^{\gcd(m,16)}\equiv 1\pmod p.</cmath> But <math>2019^8\equiv -1\pmod p,</math> so <math>\gcd(m,16)</math> cannot divide <math>8,</math> which is a contradiction. Thus <math>2019^{16}</math> is the least positive power congruent to <math>1\pmod p.</math> By Fermat's Little Theorem, <math>2019^{p-1}\equiv 1\pmod p.</math> It follows that <math>p=16k+1</math> for some positive integer <math>k.</math> The least two primes of this form are <math>17</math> and <math>97.</math> The least odd factor of <math>2019^8+1</math> is not <math>17</math> because <cmath>2019\equiv 13\pmod{17}\qquad \text{and}\qquad 13^2\equiv 169\equiv -1\pmod{17},</cmath> which implies <math>2019^8\equiv 1\not\equiv -1\pmod {17}.</math> But <math>2019\equiv -18\pmod{97},</math> so <cmath>\begin{align*}
 +
(-18)^2=324&\equiv 33\pmod{97}, \\
 +
33^2=1089&\equiv 22\pmod{97},\,\text{and} \\
 +
22^2=484&\equiv -1\pmod{97}.\end{align*}</cmath> Thus the least odd prime factor is <math>97.</math>
 +
 
 +
In fact, <math>2019^8+1=2\cdot97\cdot p,</math> where <math>p</math> is the <math>25</math>-digit prime <cmath>1423275002072658812388593.</cmath>
 +
 
 +
 
 +
==Solution 4==
 +
Let <math>n</math> represent the least odd prime that the question is asking for.
 +
 
 +
We can see that <math>2019^8\equiv -1\pmod n.</math>
 +
 
 +
Squaring both sides we get <math>2019^{16}\equiv 1\pmod n.</math>
 +
 
 +
From Fermat's Little Theorem <math>a^{n-1}\equiv 1\pmod n</math>, we know that <math>n-1</math> has to be a multiple of 16. So we want to test prime numbers that fit this.
 +
 
 +
The first prime we get is 17 and when we try it in <math>2019^8\equiv -1\pmod n,</math>
 +
 
 +
<math>2019^{8}\equiv 13^8\pmod {17}</math>
 +
 
 +
<math>169^{4}\equiv 16^4\pmod {17}</math>
 +
 
 +
<math>256^2\equiv 1\pmod {17}</math>
 +
 
 +
<math>1+1=2</math>
 +
 
 +
We see that 17 does not work. The next number that works from the application of Fermat's Little Theorem is 97 and when we try that,
 +
 
 +
<math>2019^{8}\equiv 79^8\pmod {97}</math>
 +
 
 +
<math>6241^{4}\equiv 33^4\pmod {97}</math>
 +
 
 +
<math>1089^2\equiv 22^2\pmod {97}</math>
 +
 
 +
<math>484\equiv -1\pmod {97}</math>
 +
 
 +
<math>-1+1=0</math>
 +
 
 +
Thus our answer is <math>\boxed{097}</math>.  
 +
~pengf
  
 
==Video Solution==
 
==Video Solution==
Line 27: Line 91:
 
https://youtu.be/IF88iO5keFo
 
https://youtu.be/IF88iO5keFo
  
−
==Solution 2(basbhbashabsbhbasbasbhasbhsabhasbhbhasbhbash)==
+
==Video Solution by The Power Of Logic==
−
1. Take remainder of prime <math>p</math>
+
https://youtu.be/hqg5kCz6rnQ
−
 
 
−
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}}
 +
 +
[[Category:Intermediate Number Theory Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Latest revision as of 00:22, 7 March 2024

Problem

Find the least odd prime factor of $2019^8+1$.

Video Solution & More by MegaMath

https://www.youtube.com/watch?v=E6Vs5uf49Fc

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$. Because $16 | p - 1$, and $p - 1 \geq 16$, each possible value of $p$ must be verified by manual calculation to make sure that $p | 2019^8+1$. 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)$.

Solution 2 (Basic Modular Arithmetic)

In this solution, $k$ will represent an arbitrary nonnegative integer.

We will show that any potential prime $p$ must be of the form $16k+1$ through a proof by contradiction. Suppose that there exists some prime $p$ that can not be expressed in the form $16k+1$ that is a divisor of $2019^8+1$. First, note that if the prime $p$ is a divisor of $2019$, then $2019^8$ is a multiple of $p$ and $2019^8+1$ is not. Thus, $p$ is not a divisor of $2019$.

Because $2019^8+1$ is a multiple of $p$, $2019^8+1\equiv0\pmod{p}$. This means that $2019^8\equiv-1\pmod{p}$, and by raising both sides to an arbitrary odd positive integer, we have that $2019^{16k+8}\equiv-1\pmod{p}$.

Then, since the problem requires an odd prime, $p$ can be expressed as $16k+m$, where $m$ is an odd integer ranging from $3$ to $15$, inclusive. By Fermat's Little Theorem, $2019^{p-1}\equiv1\pmod{p}$, and plugging in values, we get $2019^{16k+n}\equiv1\pmod{p}$, where $n=m-1$ and is thus an even integer ranging from $2$ to $14$, inclusive.

If $n=8$, then $2019^{16k+8}\equiv1\pmod{p}$, which creates a contradiction. If $n$ is not a multiple of $8$ but is a multiple of $4$, squaring both sides of $2019^{16k+n}\equiv1\pmod{p}$ also results in the same contradictory equivalence. For all remaining $n$, raising both sides of $2019^{16k+n}\equiv1\pmod{p}$ to the $4$th power creates the same contradiction. (Note that $32k$ and $64k$ can both be expressed in the form $16k$.)

Since we have proved that no value of $n$ can work, this means that a prime must be of the form $16k+1$ in order to be a factor of $2019^8+1$. The smallest prime of this form is $17$, and testing it, we get \[2019^8+1\equiv13^8+1\equiv169^4+1\equiv(-1)^4+1\equiv1+1\equiv2\pmod{17},\] so it does not work. The next smallest prime of the required form is $97$, and testing it, we get \[2019^8+1\equiv(-18)^8+1\equiv324^4+1\equiv33^4+1\equiv1089^2+1\equiv22^2+1\equiv484+1\equiv-1+1\equiv0\pmod{97},\] so it works. Thus, the answer is $\boxed{097}$. ~emerald_block

Solution 3 (Official MAA)

Suppose prime $p>2$ divides $2019^8+1.$ Then $2019^8\equiv -1\pmod p.$ Squaring gives $2019^{16}\equiv 1\pmod p.$ If $2019^m\equiv 1 \pmod p$ for some $0<m<16,$ it follows that \[2019^{\gcd(m,16)}\equiv 1\pmod p.\] But $2019^8\equiv -1\pmod p,$ so $\gcd(m,16)$ cannot divide $8,$ which is a contradiction. Thus $2019^{16}$ is the least positive power congruent to $1\pmod p.$ By Fermat's Little Theorem, $2019^{p-1}\equiv 1\pmod p.$ It follows that $p=16k+1$ for some positive integer $k.$ The least two primes of this form are $17$ and $97.$ The least odd factor of $2019^8+1$ is not $17$ because \[2019\equiv 13\pmod{17}\qquad \text{and}\qquad 13^2\equiv 169\equiv -1\pmod{17},\] which implies $2019^8\equiv 1\not\equiv -1\pmod {17}.$ But $2019\equiv -18\pmod{97},$ so \begin{align*} (-18)^2=324&\equiv 33\pmod{97}, \\ 33^2=1089&\equiv 22\pmod{97},\,\text{and} \\ 22^2=484&\equiv -1\pmod{97}.\end{align*} Thus the least odd prime factor is $97.$

In fact, $2019^8+1=2\cdot97\cdot p,$ where $p$ is the $25$-digit prime \[1423275002072658812388593.\]


Solution 4

Let $n$ represent the least odd prime that the question is asking for.

We can see that $2019^8\equiv -1\pmod n.$

Squaring both sides we get $2019^{16}\equiv 1\pmod n.$

From Fermat's Little Theorem $a^{n-1}\equiv 1\pmod n$, we know that $n-1$ has to be a multiple of 16. So we want to test prime numbers that fit this.

The first prime we get is 17 and when we try it in $2019^8\equiv -1\pmod n,$

$2019^{8}\equiv 13^8\pmod {17}$

$169^{4}\equiv 16^4\pmod {17}$

$256^2\equiv 1\pmod {17}$

$1+1=2$

We see that 17 does not work. The next number that works from the application of Fermat's Little Theorem is 97 and when we try that,

$2019^{8}\equiv 79^8\pmod {97}$

$6241^{4}\equiv 33^4\pmod {97}$

$1089^2\equiv 22^2\pmod {97}$

$484\equiv -1\pmod {97}$

$-1+1=0$

Thus our answer is $\boxed{097}$. ~pengf

Video Solution

On The Spot STEM:

https://youtu.be/_vHq5_5qCd8


https://youtu.be/IF88iO5keFo

Video Solution by The Power Of Logic

https://youtu.be/hqg5kCz6rnQ

See Also

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

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_AIME_I_Problems/Problem_14&oldid=216554"