Difference between revisions of "2024 AIME I Problems/Problem 13"
m (→Solution 2) |
|||
Line 20: | Line 20: | ||
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, | + | Here, |
So we have to find the smallest positive integer | So we have to find the smallest positive integer | ||
\begin{array}{|c|cccccccccccccccc|} | \begin{array}{|c|cccccccccccccccc|} | ||
Line 29: | Line 29: | ||
So | So | ||
\begin{align*} | \begin{align*} | ||
− | 0&\equiv(17k+2)^4+1\equiv\mathrm | + | 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 36: | ||
If | If | ||
\begin{align*} | \begin{align*} | ||
− | 0&\equiv(17k-2)^4+1\equiv\mathrm | + | 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 43: | ||
If | If | ||
\begin{align*} | \begin{align*} | ||
− | 0&\equiv(17k+8)^4+1\equiv\mathrm | + | 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 50: | ||
If | If | ||
\begin{align*} | \begin{align*} | ||
− | 0&\equiv(17k-8)^4+1\equiv\mathrm | + | 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*} |
Revision as of 20:20, 4 February 2024
Contents
[hide]Problem
Let be the least prime number for which there exists a positive integer such that is divisible by . Find the least positive integer such that is divisible by .
Solution
From there, we could get
By doing binomial expansion bash, the four smallest in this case are , yielding
~Bluesoul
Solution 2
If
For integer
If
If
If
In conclusion, the smallest possible
Solution by Quantum-Phantom
Solution 3
We work in the ring
Video Solution 1 by OmegaLearn.org
Video Solution 2
~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.