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

Revision as of 21:44, 6 June 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)$ .

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

Video Solution

On The Spot STEM:

https://youtu.be/_vHq5_5qCd8

https://youtu.be/IF88iO5keFo

@@ Line 18: / Line 18: @@
 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]]
 ==Video Solution==

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

Page

Toolbox

Search