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

(Solution 1)
Line 59: Line 59:
  
 
~Aaryabhatta1
 
~Aaryabhatta1
 +
 +
 +
==Solution 4==
 +
These kind of problems, are by nature, elementary. We get:<cmath> m^4\equiv(-1) mod p^2</cmath>, thus , m is even , and <cmath>p^2=16k+1</cmath>
 +
or <cmath>p=16k+1</cmath>, since p is prime. Therefore the smallest possible such p is 17. Again,
 +
<cmath>m^4\equiv(16) mod 17</cmath>. This is where it gets a bit tricky.
 +
<cmath>(m^2-1)*(m^2+1)\equiv (0) mod 17</cmath> or <cmath>m^2\equiv 13 mod 17</cmath> Giving rise to:<cmath>m\equiv(8) mod 17</cmath>
 +
Now m lies in the series 42, 76, 110, 144..... . It is easy to see that the smallest value of m is 110 as neither 42 nor 76 satisfy all criteria.
 +
 +
~Grammaticus
 +
 +
  
 
==Video Solution==
 
==Video Solution==

Revision as of 02:29, 6 June 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


Solution 4

These kind of problems, are by nature, elementary. We get:\[m^4\equiv(-1) mod 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) mod 17\]. This is where it gets a bit tricky. \[(m^2-1)*(m^2+1)\equiv (0) mod 17\] or \[m^2\equiv 13 mod 17\] Giving rise to:\[m\equiv(8) mod 17\] Now m lies in the series 42, 76, 110, 144..... . It is easy to see that the smallest value of m is 110 as neither 42 nor 76 satisfy all criteria.

~Grammaticus


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