Difference between revisions of "2024 AIME I Problems/Problem 13"
Aaryabhatta1 (talk | contribs) |
Wescarroll (talk | contribs) m ("Easy," my eyeteeth) |
||
Line 54: | Line 54: | ||
Since | Since | ||
− | ==Solution 3 (Easy)== | + | ==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. | 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. |
Revision as of 18:39, 8 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 1
If
For integer
If
If
If
In conclusion, the smallest possible
Solution by Quantum-Phantom
Solution 2
We work in the ring
Solution 3 (Easy, given specialized knowledge)
Note that means The smallest prime that does this is and for example. Now let be a primitive root of The satisfying are of the form, So if we find one such , then all are Consider the from before. Note by LTE. Hence the possible are, Some modular arithmetic yields that is the least value.
~Aaryabhatta1
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.