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

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 $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 \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 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$. 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)^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\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 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 $m\equiv-2\pmod{17}$, 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=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 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 $m\equiv-8\pmod{17}$, 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+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

Video Solution 1 by OmegaLearn.org

https://youtube/UyoCHBeII6g

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

Page

Toolbox

Search