Difference between revisions of "2019 AIME I Problems/Problem 14"
(→Solution) |
(→Solution) |
||
(11 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem | + | ==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>. | ||
Line 5: | Line 5: | ||
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>. | 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>, the order of <math>2019</math> modulo <math>p</math> is a positive divisor of <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 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>. | 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, 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=== | |
+ | <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>. | |
− | |||
− | |||
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>. | ||
+ | ==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> | ||
==Video Solution== | ==Video Solution== | ||
On The Spot STEM: | On The Spot STEM: | ||
Line 32: | Line 55: | ||
==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 18:21, 14 January 2022
Contents
Problem
Find the least odd prime factor of .
Solution
We know that for some prime . We want to find the smallest odd possible value of . By squaring both sides of the congruence, we find .
Since , the order of modulo is a positive divisor of .
However, if the order of modulo is or then will be equivalent to which contradicts the given requirement that .
Therefore, the order of modulo is . Because all orders modulo divide , we see that is a multiple of . As is prime, . Therefore, . The two smallest primes equivalent to are and . Because , and , each possible value of must be verified by manual calculation to make sure that . As and , the smallest possible is thus .
Note to solution
is the Euler Totient Function of integer . is the number of positive integers less than relatively prime to . Define the numbers to be the prime factors of . Then, we haveA property of the Totient function is that, for any prime , .
Euler's Totient Theorem states thatif .
Furthermore, the order modulo for an integer relatively prime to is defined as the smallest positive integer such that . An important property of the order is that .
Solution 2 (Basic Modular Arithmetic)
In this solution, will represent an arbitrary nonnegative integer.
We will show that any potential prime must be of the form through a proof by contradiction. Suppose that there exists some prime that can not be expressed in the form that is a divisor of . First, note that if the prime is a divisor of , then is a multiple of and is not. Thus, is not a divisor of .
Because is a multiple of , . This means that , and by raising both sides to an arbitrary odd positive integer, we have that .
Then, since the problem requires an odd prime, can be expressed as , where is an odd integer ranging from to , inclusive. By Fermat's Little Theorem, , and plugging in values, we get , where and is thus an even integer ranging from to , inclusive.
If , then , which creates a contradiction. If is not a multiple of but is a multiple of , squaring both sides of also results in the same contradictory equivalence. For all remaining , raising both sides of to the th power creates the same contradiction. (Note that and can both be expressed in the form .)
Since we have proved that no value of can work, this means that a prime must be of the form in order to be a factor of . The smallest prime of this form is , and testing it, we get so it does not work. The next smallest prime of the required form is , and testing it, we get so it works. Thus, the answer is . ~emerald_block
Solution 3 (Official MAA)
Suppose prime divides Then Squaring gives If for some it follows that But so cannot divide which is a contradiction. Thus is the least positive power congruent to By Fermat's Little Theorem, It follows that for some positive integer The least two primes of this form are and The least odd factor of is not because which implies But so Thus the least odd prime factor is
In fact, where is the -digit prime
Video Solution
On The Spot STEM:
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.