Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2024 AIME I Problems/Problem 13"
(→‎Solution 4)
 
(18 intermediate revisions by 12 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==
−
 
 
−
<math>n^4+1\equiv 0\pmod{p^2}\implies n^8 \equiv 1\pmod{p^2}\implies p_{min}=17</math>
 
−
 
 
−
From there, we could get <math>n\equiv \pm 2, \pm 8\pmod{17}</math>
 
−
 
 
−
By doing binomial expansion bash, the four smallest <math>n</math> in this case are <math>110, 134, 155, 179</math>, yielding <math>\boxed{110}</math>
 
−
 
 
−
~Bluesoul
 
−
 
 
−
==Solution 2==
 
  
 
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 theorem, \(p\mid n^{p-1}-1\), so
+
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.
 
\end{equation*}
 
\end{equation*}
−
Here, \(\gcd(p-1,8)\) mustn't be divisible by \(4\) 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\).
+
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
 
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|}
 
\begin{array}{|c|cccccccccccccccc|}
 
\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)^2+1\bmod{17}&2&0&14&2&14&5&5&0&0&5&5&14&2&14&0&2\\\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}
 
\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,
 
\begin{align*}
 
\begin{align*}
−
0&\equiv(17k+2)^4+1\equiv\mathrm C_4^1(17k)(2)^3+2^4+1=17(1+32k)\pmod{17^2}\\[3pt]
+
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}.
 
\implies0&\equiv1+32k\equiv1-2k\pmod{17}.
 
\end{align*}
 
\end{align*}
Line 36: Line 26:
 
If \(m\equiv-2\pmod{17}\), let \(m=17k-2\), by the binomial theorem,
 
If \(m\equiv-2\pmod{17}\), let \(m=17k-2\), by the binomial theorem,
 
\begin{align*}
 
\begin{align*}
−
0&\equiv(17k-2)^4+1\equiv\mathrm C_4^1(17k)(-2)^3+2^4+1=17(1-32k)\pmod{17^2}\\[3pt]
+
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}.
 
\implies0&\equiv1-32k\equiv1+2k\pmod{17}.
 
\end{align*}
 
\end{align*}
Line 43: Line 33:
 
If \(m\equiv8\pmod{17}\), let \(m=17k+8\), by the binomial theorem,
 
If \(m\equiv8\pmod{17}\), let \(m=17k+8\), by the binomial theorem,
 
\begin{align*}
 
\begin{align*}
−
0&\equiv(17k+8)^4+1\equiv\mathrm C_4^1(17k)(8)^3+8^4+1=17(241+2048k)\pmod{17^2}\\[3pt]
+
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}.
 
\implies0&\equiv241+2048k\equiv3+8k\pmod{17}.
 
\end{align*}
 
\end{align*}
Line 50: Line 40:
 
If \(m\equiv-8\pmod{17}\), let \(m=17k-8\), by the binomial theorem,
 
If \(m\equiv-8\pmod{17}\), let \(m=17k-8\), by the binomial theorem,
 
\begin{align*}
 
\begin{align*}
−
0&\equiv(17k-8)^4+1\equiv\mathrm C_4^1(17k)(-8)^3+8^4+1=17(241-2048k)\pmod{17^2}\\[3pt]
+
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}.
 
\implies0&\equiv241+2048k\equiv3+9k\pmod{17}.
 
\end{align*}
 
\end{align*}
Line 59: Line 49:
 
<font size=2>Solution by Quantum-Phantom</font>
 
<font size=2>Solution by Quantum-Phantom</font>
  
−
==Solution 3==
+
==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
 +
 +
 +
==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
 +
 +
Where is the justification for why <math>m</math> is even? If there is none, then this is just a "lucky solve"
 +
~inaccessibles
 +
 +
==Video Solution==
 +
https://www.youtube.com/watch?v=_ambewDODiA
 +
 +
~MathProblemSolvingSkills.com
 +
 +
  
 
==Video Solution 1 by OmegaLearn.org==
 
==Video Solution 1 by OmegaLearn.org==
−
https://youtube/UyoCHBeII6g
+
https://youtu.be/UyoCHBeII6g
  
 
==Video Solution 2==
 
==Video Solution 2==

Latest revision as of 17:39, 24 November 2024

Problem

Let $p$ be the least prime number for which there exists a positive integer $n$ such that $n^{4}+1$ is divisible by $p^{2}$. Find the least positive integer $m$ such that $m^{4}+1$ is divisible by $p^{2}$.

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}.\] 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 $n^4 + 1 \equiv 0 \pmod{p}$ means $\text{ord}_{p}(n) = 8 \mid p-1.$ The smallest prime that does this is $17$ and $2^4 + 1 = 17$ for example. Now let $g$ be a primitive root of $17^2.$ The satisfying $n$ are of the form, $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}}.$ So if we find one such $n$, then all $n$ are $n, n^3, n^5, n^7.$ Consider the $2$ from before. Note $17^2 \mid 2^{4 \cdot 17} + 1$ by LTE. Hence the possible $n$ are, $2^{17}, 2^{51}, 2^{85}, 2^{119}.$ Some modular arithmetic yields that $2^{51} \equiv \boxed{110}$ is the least value.

~Aaryabhatta1


Solution 4

These kinds of problems are, by nature, elementary. We get: \[m^4 \equiv -1 \pmod{p^2},\] thus, $m$ is even, and \[p^2 = 16k + 1\] or \[p = 16k + 1,\] since $p$ is prime. Therefore, the smallest possible such $p$ is $17$. Again, \[m^4 \equiv 16 \pmod{17}.\] This is where it gets a bit tricky. \[(m^2 - 4)(m^2 + 4) \equiv 0 \pmod{17}\] or \[m^2 \equiv 13 \pmod{17}.\] This gives rise to: \[m \equiv 8 \pmod{17}.\] Now, $m$ lies in the series $42, 76, 110, 144, \ldots$. It is easy to see that the smallest value of $m$ is $110$ as neither $42$ nor $76$ satisfy all criteria.

~Grammaticus

Where is the justification for why $m$ is even? If there is none, then this is just a "lucky solve" ~inaccessibles

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

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2024_AIME_I_Problems/Problem_13&oldid=235506"