Difference between revisions of "2024 AIME I Problems/Problem 13"
(→Solution) |
m (→Solution 4) |
||
(22 intermediate revisions by 16 users not shown) | |||
Line 2: | Line 2: | ||
Let <math>p</math> be the least prime number for which there exists a positive integer <math>n</math> such that <math>n^{4}+1</math> is divisible by <math>p^{2}</math>. Find the least positive integer <math>m</math> such that <math>m^{4}+1</math> is divisible by <math>p^{2}</math>. | Let <math>p</math> be the least prime number for which there exists a positive integer <math>n</math> such that <math>n^{4}+1</math> is divisible by <math>p^{2}</math>. Find the least positive integer <math>m</math> such that <math>m^{4}+1</math> is divisible by <math>p^{2}</math>. | ||
− | ==Solution== | + | ==Solution 1== |
− | + | If | |
− | + | For integer | |
+ | \begin{equation*} | ||
+ | p\mid\gcd\left(n^{p-1}-1,n^8-1\right)=n^{\gcd(p-1,8)}-1. | ||
+ | \end{equation*} | ||
+ | Here, | ||
+ | So we have to find the smallest positive integer | ||
+ | \begin{array}{|c|cccccccccccccccc|} | ||
+ | \hline | ||
+ | \vphantom{\tfrac11}x\bmod{17}&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\hline | ||
+ | \vphantom{\dfrac11}\left(x^4\right)+1\bmod{17}&2&0&14&2&14&5&5&0&0&5&5&14&2&14&0&2\\hline | ||
+ | \end{array} | ||
+ | So \(m\equiv\pm2\), | ||
+ | \begin{align*} | ||
+ | 0&\equiv(17k+2)^4+1\equiv\mathrm {4\choose 1}(17k)(2)^3+2^4+1=17(1+32k)\pmod{17^2}\[3pt] | ||
+ | \implies0&\equiv1+32k\equiv1-2k\pmod{17}. | ||
+ | \end{align*} | ||
+ | So the smallest possible | ||
− | + | If | |
+ | \begin{align*} | ||
+ | 0&\equiv(17k-2)^4+1\equiv\mathrm {4\choose 1}(17k)(-2)^3+2^4+1=17(1-32k)\pmod{17^2}\[3pt] | ||
+ | \implies0&\equiv1-32k\equiv1+2k\pmod{17}. | ||
+ | \end{align*} | ||
+ | So the smallest possible | ||
− | ~ | + | If |
+ | \begin{align*} | ||
+ | 0&\equiv(17k+8)^4+1\equiv\mathrm {4\choose 1}(17k)(8)^3+8^4+1=17(241+2048k)\pmod{17^2}\[3pt] | ||
+ | \implies0&\equiv241+2048k\equiv3+8k\pmod{17}. | ||
+ | \end{align*} | ||
+ | So the smallest possible | ||
+ | |||
+ | If | ||
+ | \begin{align*} | ||
+ | 0&\equiv(17k-8)^4+1\equiv\mathrm {4\choose 1}(17k)(-8)^3+8^4+1=17(241-2048k)\pmod{17^2}\[3pt] | ||
+ | \implies0&\equiv241+2048k\equiv3+9k\pmod{17}. | ||
+ | \end{align*} | ||
+ | So the smallest possible | ||
+ | |||
+ | In conclusion, the smallest possible | ||
+ | |||
+ | <font size=2>Solution by Quantum-Phantom</font> | ||
+ | |||
+ | ==Solution 2== | ||
+ | We work in the ring | ||
+ | <cmath>\sqrt[4]{-1}=\pm\sqrt{\frac12}\pm\sqrt{-\frac12}.</cmath> | ||
+ | Since | ||
+ | |||
+ | ==Solution 3 (Easy, given specialized knowledge)== | ||
+ | |||
+ | Note that <math>n^4 + 1 \equiv 0 \pmod{p}</math> means <math>\text{ord}_{p}(n) = 8 \mid p-1.</math> The smallest prime that does this is <math>17</math> and <math>2^4 + 1 = 17</math> for example. Now let <math>g</math> be a primitive root of <math>17^2.</math> The satisfying <math>n</math> are of the form, <math>g^{\frac{p(p-1)}{8}}, g^{3\frac{p(p-1)}{8}}, g^{5\frac{p(p-1)}{8}}, g^{7\frac{p(p-1)}{8}}.</math> So if we find one such <math>n</math>, then all <math>n</math> are <math>n, n^3, n^5, n^7.</math> Consider the <math>2</math> from before. Note <math>17^2 \mid 2^{4 \cdot 17} + 1</math> by LTE. Hence the possible <math>n</math> are, <math>2^{17}, 2^{51}, 2^{85}, 2^{119}.</math> Some modular arithmetic yields that <math>2^{51} \equiv \boxed{110}</math> is the least value. | ||
+ | |||
+ | ~Aaryabhatta1 | ||
+ | |||
+ | |||
+ | ==Solution 4== | ||
+ | These kinds of problems are, by nature, elementary. We get: <cmath> m^4 \equiv -1 \pmod{p^2},</cmath> thus, <math>m</math> is even, and <cmath>p^2 = 16k + 1</cmath> or <cmath>p = 16k + 1,</cmath> since <math>p</math> is prime. Therefore, the smallest possible such <math>p</math> is <math>17</math>. Again, | ||
+ | <cmath>m^4 \equiv 16 \pmod{17}.</cmath> This is where it gets a bit tricky. | ||
+ | <cmath>(m^2 - 4)(m^2 + 4) \equiv 0 \pmod{17}</cmath> or <cmath>m^2 \equiv 13 \pmod{17}.</cmath> This gives rise to: <cmath>m \equiv 8 \pmod{17}.</cmath> | ||
+ | Now, <math>m</math> lies in the series <math>42, 76, 110, 144, \ldots</math>. It is easy to see that the smallest value of <math>m</math> is <math>110</math> as neither <math>42</math> nor <math>76</math> satisfy all criteria. | ||
+ | |||
+ | ~Grammaticus | ||
+ | |||
+ | ==Video Solution== | ||
+ | https://www.youtube.com/watch?v=_ambewDODiA | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
+ | |||
+ | |||
+ | |||
+ | ==Video Solution 1 by OmegaLearn.org== | ||
+ | https://youtu.be/UyoCHBeII6g | ||
+ | |||
+ | ==Video Solution 2== | ||
+ | |||
+ | https://youtu.be/F3pezlR5WHc | ||
+ | |||
+ | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ||
==See also== | ==See also== | ||
{{AIME box|year=2024|n=I|num-b=12|num-a=14}} | {{AIME box|year=2024|n=I|num-b=12|num-a=14}} | ||
+ | [[Category:Intermediate Number Theory Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 17:21, 18 June 2024
Contents
[hide]Problem
Let be the least prime number for which there exists a positive integer such that is divisible by . Find the least positive integer such that is divisible by .
Solution 1
If
For integer
If
If
If
In conclusion, the smallest possible
Solution by Quantum-Phantom
Solution 2
We work in the ring
Solution 3 (Easy, given specialized knowledge)
Note that means The smallest prime that does this is and for example. Now let be a primitive root of The satisfying are of the form, So if we find one such , then all are Consider the from before. Note by LTE. Hence the possible are, Some modular arithmetic yields that is the least value.
~Aaryabhatta1
Solution 4
These kinds of problems are, by nature, elementary. We get: thus, is even, and or since is prime. Therefore, the smallest possible such is . Again, This is where it gets a bit tricky. or This gives rise to: Now, lies in the series . It is easy to see that the smallest value of is as neither nor satisfy all criteria.
~Grammaticus
Video Solution
https://www.youtube.com/watch?v=_ambewDODiA
~MathProblemSolvingSkills.com
Video Solution 1 by OmegaLearn.org
Video Solution 2
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
See also
2024 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
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.