Difference between revisions of "2024 AIME I Problems/Problem 13"

m (Video Solution 1 by OmegaLearn.org)
Line 11: Line 11:
  
 
~Bluesoul
 
~Bluesoul
 +
 +
==Solution 2==
 +
 +
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
 +
\begin{equation*}
 +
p\mid\gcd\left(n^{p-1}-1,n^8-1\right)=n^{\gcd(p-1,8)}-1.
 +
\end{equation*}
 +
Here, gcd(p1,8) mustn't be divisible by 4 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
 +
\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)^2+1\bmod{17}&2&0&14&2&14&5&5&0&0&5&5&14&2&14&0&2\\hline
 +
\end{array}
 +
So m±2, ±8(mod17). If m2(mod17), let m=17k+2, by the binomial theorem,
 +
\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]
 +
\implies0&\equiv1+32k\equiv1-2k\pmod{17}.
 +
\end{align*}
 +
So the smallest possible k=9, and m=155.
 +
 +
If m2(mod17), let m=17k2, by the binomial theorem,
 +
\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]
 +
\implies0&\equiv1-32k\equiv1+2k\pmod{17}.
 +
\end{align*}
 +
So the smallest possible k=8, and m=134.
 +
 +
If m8(mod17), let m=17k+8, by the binomial theorem,
 +
\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]
 +
\implies0&\equiv241+2048k\equiv3+8k\pmod{17}.
 +
\end{align*}
 +
So the smallest possible k=6, and m=110.
 +
 +
If m8(mod17), let m=17k8, by the binomial theorem,
 +
\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]
 +
\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 110.
 +
 +
<font size=2>Solution by Quantum-Phantom</font>
  
 
==Video Solution 1 by OmegaLearn.org==
 
==Video Solution 1 by OmegaLearn.org==

Revision as of 19:58, 3 February 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

$n^4+1\equiv 0\pmod{p^2}\implies n^8 \equiv 1\pmod{p^2}\implies p_{min}=17$

From there, we could get $n\equiv \pm 2, \pm 8\pmod{17}$

By doing binomial expansion bash, the four smallest $n$ in this case are $110, 134, 155, 179$, yielding $\boxed{110}$

~Bluesoul

Solution 2

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 pgcd(np11,n81)=ngcd(p1,8)1. Here, gcd(p1,8) mustn't be divisible by 4 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)2+1mod1720142145500551421402 So m±2, ±8(mod17). If m2(mod17), let m=17k+2, by the binomial theorem, 0(17k+2)4+1C41(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+1C41(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+1C41(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+1C41(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

Video Solution 1 by OmegaLearn.org

https://youtube/UyoCHBeII6g

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