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 2==
+
==Solution 1==
  
 
If p=2, then 4n4+1 for some integer n. But (n2)20 or 1(mod4), so it is impossible. Thus p is an odd prime.
 
If p=2, then 4n4+1 for some integer n. But (n2)20 or 1(mod4), so it is impossible. Thus p is an odd prime.
  
For integer n such that p2n4+1, we have pn4+1, hence pn41, but pn81. By Fermat's theorem, pnp11, so
+
For integer n such that p2n4+1, we have pn4+1, hence pn41, but pn81. By [[Fermat's Little Theorem]], pnp11, 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)^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±2, ±8(mod17). If m2(mod17), let m=17k+2, by the binomial theorem,
 
So m±2, ±8(mod17). If m2(mod17), 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 3==
+
==Solution 2==
 
We work in the ring Z/289Z and use the formula
 
We work in the ring Z/289Z 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 12=144, the expression becomes ±12±12i, and it is easily calculated via Hensel that i=38, thus giving an answer of \(\boxed{110.00}\).
+
Since 12=144, the expression becomes ±12±12i, 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://youtube/UyoCHBeII6g
+
https://youtu.be/UyoCHBeII6g
  
 
==Video Solution 2==
 
==Video Solution 2==

Latest revision as of 22:10, 28 December 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 4n4+1 for some integer n. But (n2)20 or 1(mod4), so it is impossible. Thus p is an odd prime.

For integer n such that p2n4+1, we have pn4+1, hence pn41, but pn81. By Fermat's Little Theorem, pnp11, so pgcd(np11,n81)=ngcd(p1,8)1. Here, gcd(p1,8) mustn't be divide into 4 or otherwise pngcd(p1,8)1n41, which contradicts. So gcd(p1,8)=8, and so 8p1. The smallest such prime is clearly p=17=2×8+1. So we have to find the smallest positive integer m such that 17m4+1. We first find the remainder of m divided by 17 by doing 11xmod171234567891011121314151611(x4)+1mod1720142145500551421402 So m±2, ±8(mod17). If m2(mod17), let m=17k+2, by the binomial theorem, 0(17k+2)4+1(41)(17k)(2)3+24+1=17(1+32k)(mod172)01+32k12k(mod17). So the smallest possible k=9, and m=155.

If m2(mod17), let m=17k2, by the binomial theorem, 0(17k2)4+1(41)(17k)(2)3+24+1=17(132k)(mod172)0132k1+2k(mod17). So the smallest possible k=8, and m=134.

If m8(mod17), let m=17k+8, by the binomial theorem, 0(17k+8)4+1(41)(17k)(8)3+84+1=17(241+2048k)(mod172)0241+2048k3+8k(mod17). So the smallest possible k=6, and m=110.

If m8(mod17), let m=17k8, by the binomial theorem, 0(17k8)4+1(41)(17k)(8)3+84+1=17(2412048k)(mod172)0241+2048k3+9k(mod17). So the smallest possible k=11, and m=179.

In conclusion, the smallest possible m is 110.

Solution by Quantum-Phantom

Solution 2

We work in the ring Z/289Z and use the formula \[\sqrt[4]{-1}=\pm\sqrt{\frac12}\pm\sqrt{-\frac12}.\] Since 12=144, the expression becomes ±12±12i, and it is easily calculated via Hensel that i=38, thus giving an answer of 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


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 (ProblemsAnswer KeyResources)
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