Difference between revisions of "2019 AIME I Problems/Problem 14"
Huangyi 99 (talk | contribs) m (→Video Solution) |
(→Video Solution) |
||
(46 intermediate revisions by 26 users not shown) | |||
Line 1: | Line 1: | ||
− | The 2019 | + | ==Problem== |
+ | 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== | ||
+ | |||
+ | 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>. | ||
+ | |||
+ | 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>. | ||
+ | |||
+ | ==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== | ||
On The Spot STEM: | On The Spot STEM: | ||
+ | |||
https://youtu.be/_vHq5_5qCd8 | https://youtu.be/_vHq5_5qCd8 | ||
+ | |||
+ | |||
https://youtu.be/IF88iO5keFo | https://youtu.be/IF88iO5keFo | ||
+ | |||
+ | ==Video Solution by The Power Of Logic== | ||
+ | https://youtu.be/hqg5kCz6rnQ | ||
==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 01:22, 7 March 2024
Contents
Problem
Find the least odd prime factor of .
Video Solution & More by MegaMath
https://www.youtube.com/watch?v=E6Vs5uf49Fc
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 have
A 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
Solution 4
Let represent the least odd prime that the question is asking for.
We can see that
Squaring both sides we get
From Fermat's Little Theorem , we know that
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
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,
Thus our answer is .
~pengf
Video Solution
On The Spot STEM:
Video Solution by The Power Of Logic
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.