Difference between revisions of "2024 AIME I Problems/Problem 13"
(The same solution is covered in solution 2, and this solution does not prove nor explain its intermediate steps.) |
(→Solution 4) |
||
| (18 intermediate revisions by 11 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 \(p=2\), then \(4\mid n^4+1\) for some integer \(n\). But \(\left(n^2\right)^2\equiv0\) or \(1\pmod4\), so it is impossible. Thus \(p\) is an odd prime. | If \(p=2\), then \(4\mid n^4+1\) for some integer \(n\). But \(\left(n^2\right)^2\equiv0\) or \(1\pmod4\), so it is impossible. Thus \(p\) is an odd prime. | ||
| − | For integer \(n\) such that \(p^2\mid n^4+1\), we have \(p\mid n^4+1\), hence \(p\nmid n^4-1\), but \(p\mid n^8-1\). By Fermat's | + | For integer \(n\) such that \(p^2\mid n^4+1\), we have \(p\mid n^4+1\), hence \(p\nmid n^4-1\), but \(p\mid n^8-1\). By [[Fermat's Little Theorem]], \(p\mid n^{p-1}-1\), so |
\begin{equation*} | \begin{equation*} | ||
p\mid\gcd\left(n^{p-1}-1,n^8-1\right)=n^{\gcd(p-1,8)}-1. | p\mid\gcd\left(n^{p-1}-1,n^8-1\right)=n^{\gcd(p-1,8)}-1. | ||
| Line 15: | Line 15: | ||
\hline | \hline | ||
\vphantom{\tfrac11}x\bmod{17}&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\\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) | + | \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} | \end{array} | ||
So \(m\equiv\pm2\), \(\pm8\pmod{17}\). If \(m\equiv2\pmod{17}\), let \(m=17k+2\), by the binomial theorem, | So \(m\equiv\pm2\), \(\pm8\pmod{17}\). If \(m\equiv2\pmod{17}\), let \(m=17k+2\), by the binomial theorem, | ||
| Line 49: | Line 49: | ||
<font size=2>Solution by Quantum-Phantom</font> | <font size=2>Solution by Quantum-Phantom</font> | ||
| − | ==Solution | + | ==Solution 2== |
We work in the ring \(\mathbb Z/289\mathbb Z\) and use the formula | We work in the ring \(\mathbb Z/289\mathbb Z\) and use the formula | ||
<cmath>\sqrt[4]{-1}=\pm\sqrt{\frac12}\pm\sqrt{-\frac12}.</cmath> | <cmath>\sqrt[4]{-1}=\pm\sqrt{\frac12}\pm\sqrt{-\frac12}.</cmath> | ||
| − | Since \(-\frac12=144\), the expression becomes \(\pm12\pm12i\), and it is easily calculated via Hensel that \(i=38\), thus giving an answer of \(\boxed{110. | + | Since \(-\frac12=144\), the expression becomes \(\pm12\pm12i\), and it is easily calculated via Hensel that \(i=38\), thus giving an answer of \(\boxed{110}\). |
| + | |||
| + | ==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 | ||
| + | |||
| + | |||
| + | ==Video Solution== | ||
| + | https://www.youtube.com/watch?v=_ambewDODiA | ||
| + | |||
| + | ~MathProblemSolvingSkills.com | ||
| + | |||
| + | |||
==Video Solution 1 by OmegaLearn.org== | ==Video Solution 1 by OmegaLearn.org== | ||
| − | https:// | + | https://youtu.be/UyoCHBeII6g |
==Video Solution 2== | ==Video Solution 2== | ||
Latest revision as of 23:10, 28 December 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 \(p=2\), then \(4\mid n^4+1\) for some integer \(n\). But \(\left(n^2\right)^2\equiv0\) or \(1\pmod4\), so it is impossible. Thus \(p\) is an odd prime.
For integer \(n\) such that \(p^2\mid n^4+1\), we have \(p\mid n^4+1\), hence \(p\nmid n^4-1\), but \(p\mid n^8-1\). By Fermat's Little Theorem, \(p\mid n^{p-1}-1\), so \begin{equation*} p\mid\gcd\left(n^{p-1}-1,n^8-1\right)=n^{\gcd(p-1,8)}-1. \end{equation*} Here, \(\gcd(p-1,8)\) mustn't be divide into \(4\) or otherwise \(p\mid n^{\gcd(p-1,8)}-1\mid n^4-1\), which contradicts. So \(\gcd(p-1,8)=8\), and so \(8\mid p-1\). The smallest such prime is clearly \(p=17=2\times8+1\). So we have to find the smallest positive integer \(m\) such that \(17\mid m^4+1\). We first find the remainder of \(m\) divided by \(17\) by doing \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\), \(\pm8\pmod{17}\). If \(m\equiv2\pmod{17}\), let \(m=17k+2\), by the binomial theorem, \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 \(k=9\), and \(m=155\).
If \(m\equiv-2\pmod{17}\), let \(m=17k-2\), by the binomial theorem, \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 \(k=8\), and \(m=134\).
If \(m\equiv8\pmod{17}\), let \(m=17k+8\), by the binomial theorem, \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 \(k=6\), and \(m=110\).
If \(m\equiv-8\pmod{17}\), let \(m=17k-8\), by the binomial theorem, \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 \(k=11\), and \(m=179\).
In conclusion, the smallest possible \(m\) is \(\boxed{110}\).
Solution by Quantum-Phantom
Solution 2
We work in the ring \(\mathbb Z/289\mathbb Z\) and use the formula
![\[\sqrt[4]{-1}=\pm\sqrt{\frac12}\pm\sqrt{-\frac12}.\]](http://latex.artofproblemsolving.com/e/e/0/ee0a7fb6fce99e26b219659345fddc24e07147db.png)
Since \(-\frac12=144\), the expression becomes \(\pm12\pm12i\), and it is easily calculated via Hensel that \(i=38\), thus giving an answer of \(\boxed{110}\).
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
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. 
