Difference between revisions of "2018 AIME I Problems/Problem 11"
m (added a solution for this problem) |
m (→Solution 2) |
||
(19 intermediate revisions by 11 users not shown) | |||
Line 5: | Line 5: | ||
==Solutions== | ==Solutions== | ||
− | == | + | ==Solution 1== |
− | Note that the given condition is equivalent to <math>3^n \equiv 1 \pmod{143^2}</math> and <math>143=11\cdot 13</math>. Because <math>gcd(11^2, 13^2) = 1</math>, the desired condition is equivalent to <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>. | + | Note that the given condition is equivalent to <math>3^n \equiv 1 \pmod{143^2}</math> and <math>143=11\cdot 13</math>. Because <math>\gcd(11^2, 13^2) = 1</math>, the desired condition is equivalent to <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>. |
If <math>3^n \equiv 1 \pmod{121}</math>, one can see the sequence <math>1, 3, 9, 27, 81, 1, 3, 9...</math> so <math>5|n</math>. | If <math>3^n \equiv 1 \pmod{121}</math>, one can see the sequence <math>1, 3, 9, 27, 81, 1, 3, 9...</math> so <math>5|n</math>. | ||
− | Now if <math>3^n \equiv 1 \pmod{169}</math>, it is harder. But we do observe that <math>3^3 \equiv 1 \pmod{13}</math>, therefore <math>3^3 = 13a + 1</math> for some integer <math>a</math>. So our goal is to find the first number <math>p_1</math> such that <math>(13a+1)^ {p_1} \equiv 1 \pmod{169}</math>. | + | Now if <math>3^n \equiv 1 \pmod{169}</math>, it is harder. But we do observe that <math>3^3 \equiv 1 \pmod{13}</math>, therefore <math>3^3 = 13a + 1</math> for some integer <math>a</math>. So our goal is to find the first number <math>p_1</math> such that <math>(13a+1)^ {p_1} \equiv 1 \pmod{169}</math>. Then, <math>p_1 \equiv 0 \pmod{13}, </math> which follows from the binomial theorem. It is not difficult to see that the smallest <math>p_1=13</math>, so ultimately <math>3^{39} \equiv 1 \pmod{169}</math>. Therefore, <math>39|n</math>. |
The first <math>n</math> satisfying both criteria is thus <math>5\cdot 39=\boxed{195}</math>. | The first <math>n</math> satisfying both criteria is thus <math>5\cdot 39=\boxed{195}</math>. | ||
Line 19: | Line 19: | ||
Note that Euler's Totient Theorem would not necessarily lead to the smallest <math>n</math> and that in this case that <math>n</math> is greater than <math>1000</math>. | Note that Euler's Totient Theorem would not necessarily lead to the smallest <math>n</math> and that in this case that <math>n</math> is greater than <math>1000</math>. | ||
− | We wish to find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{143^2}</math>. This factors as <math>143^2=11^{2}*13^{2}</math>. Because <math>gcd(121, 169) = 1</math>, we can simply find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>. | + | We wish to find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{143^2}</math>. This factors as <math>143^2=11^{2}*13^{2}</math>. Because <math>\gcd(121, 169) = 1</math>, we can simply find the least <math>n</math> such that <math>3^n \equiv 1 \pmod{121}</math> and <math>3^n \equiv 1 \pmod{169}</math>. |
− | Quick inspection yields <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^3 \equiv 1 \pmod{13}</math>. Now we must find the smallest <math>k</math> such that <math>3^{3k} \equiv 1 \pmod{ | + | Quick inspection yields <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^3 \equiv 1 \pmod{13}</math>. Now we must find the smallest <math>k</math> such that <math>3^{3k} \equiv 1 \pmod{169}</math>. Euler's gives <math>3^{156} \equiv 1 \pmod{169}</math>. So <math>3k</math> is a factor of <math>156</math>. This gives <math>k=1,2, 4, 13, 26, 52</math>. Some more inspection yields <math>k=13</math> is the smallest valid <math>k</math>. So <math>3^5 \equiv 1 \pmod{121}</math> and <math>3^{39} \equiv 1 \pmod{169}</math>. The least <math>n</math> satisfying both is <math>lcm(5, 39)=\boxed{195}</math>. (RegularHexagon) |
==Solution 3 (Big Bash)== | ==Solution 3 (Big Bash)== | ||
Line 69: | Line 69: | ||
\end{array}</cmath> | \end{array}</cmath> | ||
− | The powers of <math>3</math> repeat in cycles of <math>5</math> | + | The powers of <math>3</math> repeat in cycles of <math>5</math> and <math>39</math> in modulo <math>121</math> and modulo <math>169</math>, respectively. The answer is <math>\text{lcm}(5, 39) = \boxed{195}</math>. |
− | ==Solution 4(Order+Bash)== | + | ~Minor edit by Yiyj1 |
+ | |||
+ | ==Solution 4 (Order+Bash)== | ||
We have that <cmath>3^n \equiv 1 \pmod{143^2}.</cmath>Now, <math>3^{110} \equiv 1 \pmod{11^2}</math> so by the Fundamental Theorem of Orders, <math>\text{ord}_{11^2}(3)|110</math> and with some bashing, we get that it is <math>5</math>. Similarly, we get that <math>\text{ord}_{13^2}(3)=39</math>. Now, <math>\text{lcm}(39,5)=\boxed{195}</math> which is our desired solution. | We have that <cmath>3^n \equiv 1 \pmod{143^2}.</cmath>Now, <math>3^{110} \equiv 1 \pmod{11^2}</math> so by the Fundamental Theorem of Orders, <math>\text{ord}_{11^2}(3)|110</math> and with some bashing, we get that it is <math>5</math>. Similarly, we get that <math>\text{ord}_{13^2}(3)=39</math>. Now, <math>\text{lcm}(39,5)=\boxed{195}</math> which is our desired solution. | ||
Line 79: | Line 81: | ||
-Stormersyle | -Stormersyle | ||
− | ==Solution 6(LTE)== | + | ==Solution 6 (LTE)== |
We can see that <math>3^n-1 = 143^2*x</math>, which means that <math>v_{11}(3^n-1) \geq 2</math>, <math>v_{13}(3^n-1) \geq 2</math>. <math>v_{11}(3^n-1) = v_{11}(242) + v_{11}(\frac{n}{5})</math>, <math>v_{13}(3^n-1) = v_{13}(26) + v_{13}(\frac{n}{3})</math> by the Lifting the Exponent lemma. From the first equation we gather that 5 divides n, while from the second equation we gather that both 13 and 3 divide n as <math>v_{13}(3^n-1) \geq 2</math>. Therefore the minimum possible value of n is <math>3\times5\times13=\boxed{195}</math>. | We can see that <math>3^n-1 = 143^2*x</math>, which means that <math>v_{11}(3^n-1) \geq 2</math>, <math>v_{13}(3^n-1) \geq 2</math>. <math>v_{11}(3^n-1) = v_{11}(242) + v_{11}(\frac{n}{5})</math>, <math>v_{13}(3^n-1) = v_{13}(26) + v_{13}(\frac{n}{3})</math> by the Lifting the Exponent lemma. From the first equation we gather that 5 divides n, while from the second equation we gather that both 13 and 3 divide n as <math>v_{13}(3^n-1) \geq 2</math>. Therefore the minimum possible value of n is <math>3\times5\times13=\boxed{195}</math>. | ||
Line 86: | Line 88: | ||
==Solution 7== | ==Solution 7== | ||
Note that the problem is basically asking for the least positive integer <math>n</math> such that <math>11^2 \cdot 13^2 | 3^n - 1.</math> It is easy to see that <math>n = \text{lcm } (a, b),</math> where <math>a</math> is the least positive integer satisfying <math>11^2 | 3^a - 1</math> and <math>b</math> the least positive integer satisfying <math>13^2 | 3^b - 1</math>. Luckily, finding <math>a</math> is a relatively trivial task, as one can simply notice that <math>3^5 = 243 \equiv 1 \mod 121</math>. However, finding <math>b</math> is slightly more nontrivial. The order of <math>3^k</math> modulo <math>13</math> (which is <math>3</math>) is trivial to find, as one can either bash out a pattern of remainders upon dividing powers of <math>3</math> by <math>13</math>, or one can notice that <math>3^3 = 27 \equiv 1 \mod 13</math> (the latter which is the definition of period/orders by FLT). We can thus rewrite <math>3^3</math> as <math>(2 \cdot 13 + 1) \mod 13^2</math>. Now suppose that <cmath>3^{3k} \equiv (13n + 1) \mod 13^2. </cmath> I claim that <math>3^{3(k+1)} \equiv (13(n+2) + 1) \mod 13^2. </math> | Note that the problem is basically asking for the least positive integer <math>n</math> such that <math>11^2 \cdot 13^2 | 3^n - 1.</math> It is easy to see that <math>n = \text{lcm } (a, b),</math> where <math>a</math> is the least positive integer satisfying <math>11^2 | 3^a - 1</math> and <math>b</math> the least positive integer satisfying <math>13^2 | 3^b - 1</math>. Luckily, finding <math>a</math> is a relatively trivial task, as one can simply notice that <math>3^5 = 243 \equiv 1 \mod 121</math>. However, finding <math>b</math> is slightly more nontrivial. The order of <math>3^k</math> modulo <math>13</math> (which is <math>3</math>) is trivial to find, as one can either bash out a pattern of remainders upon dividing powers of <math>3</math> by <math>13</math>, or one can notice that <math>3^3 = 27 \equiv 1 \mod 13</math> (the latter which is the definition of period/orders by FLT). We can thus rewrite <math>3^3</math> as <math>(2 \cdot 13 + 1) \mod 13^2</math>. Now suppose that <cmath>3^{3k} \equiv (13n + 1) \mod 13^2. </cmath> I claim that <math>3^{3(k+1)} \equiv (13(n+2) + 1) \mod 13^2. </math> | ||
− | + | ||
+ | Proof: | ||
To find <math>3^{3(k+1)}, </math> we can simply multiply <math>3^{3k}</math> by <math>3^3, </math> which is congruent to <math>2 \cdot 13 + 1</math> modulo <math>13^2</math>. | To find <math>3^{3(k+1)}, </math> we can simply multiply <math>3^{3k}</math> by <math>3^3, </math> which is congruent to <math>2 \cdot 13 + 1</math> modulo <math>13^2</math>. | ||
− | By expanding the product out, we obtain <cmath>3^{3(k+1)} \equiv (13n + 1)(2 \cdot 13 + 1) = 13^2 \cdot 2n + 13n + 2 \cdot 13 + 1 \mod 13^2, </cmath> and since the <math>13^2</math> on the LHS cancels out, we're left with < | + | By expanding the product out, we obtain <cmath>3^{3(k+1)} \equiv (13n + 1)(2 \cdot 13 + 1) = 13^2 \cdot 2n + 13n + 2 \cdot 13 + 1 \mod 13^2, </cmath> and since the <math>13^2</math> on the LHS cancels out, we're left with <cmath>13n + 2 \cdot 13 + 1 \mod 13^2 \implies 13(n+2) + 1 \mod 13^2</cmath>. Thus, our claim is proven. |
− | Let < | + | Let <math>f(n)</math> be the second to last digit when <math>3^{3k}</math> is written in base <math>13^2</math>. |
− | Using our proof, it is easy to see that < | + | Using our proof, it is easy to see that <math>f(n)</math> satisfies the recurrence <math>f(1) = 2</math> and <math>f(n+1) = f(n) + 2</math>. Since this implies <math>f(n) = 2n, </math> we just have to find the least positive integer <math>n</math> such that <math>2n</math> is a multiple of <math>13</math>, which is trivially obtained as <math>13</math>. |
− | The least integer < | + | The least integer <math>n</math> such that <math>3^n - 1</math> is divisible by <math>13^2</math> is <math>3 \cdot 13 = 39, </math> so our final answer is <math>\text{lcm } (5, 39) = \boxed{195}.</math> |
-fidgetboss_4000 | -fidgetboss_4000 | ||
+ | -minor edits made by srisainandan6 | ||
+ | |||
+ | ==Solution 8 (Official MAA)== | ||
+ | The requested positive integer is the least value of <math>n>0</math> such that <math>3^n\equiv 1\pmod{143^2}.</math> Note that <math>143=11\cdot 13.</math> The least power of <math>3</math> that is congruent to <math>1</math> modulo <math>11^2</math> is <math>3^5=243=2\cdot 11^2+1.</math> It follows that. <math>3^n\equiv 1\pmod {11^2}</math> if and only if <math>n=5j</math> for some positive integer <math>j</math>. | ||
+ | |||
+ | The least power of <math>3</math> that is congruent to <math>1</math> modulo <math>13</math> is <math>3^3=27=2\cdot 13+1.</math> It follows that <math>3^n\equiv 1\pmod{13}</math> if and only if <math>n=3k</math> for some positive integer <math>k</math>. Additionally, for some positive integer <math>k</math>, the Binomial Theorem shows that <math>3^{3k}=(26+1)^k=26\cdot k+1 \pmod{13^2}</math>. In particular, <math>3^n=3^{3k}\equiv 1\pmod {13^2}</math> if and only if <math>k=13m</math> for some positive integer <math>m</math>, that is, if and only if <math>n=39m.</math> | ||
+ | |||
+ | Because <math>11^2</math> and <math>13^2</math> are relatively prime, <math>3^n\equiv 1\pmod {143^2}</math> if and only if <math>3^n\equiv 1\pmod{11^2}</math> and <math>3^n \equiv 1\pmod {13^2}</math>. This occurs if and only if <math>n</math> is a multiple of both of the relatively prime integers <math>5</math> and <math>39</math>, so the least possible value of <math>n</math> is <math>5\cdot 39=195.</math> | ||
+ | |||
+ | ==Solution 9 (Motivation and LTE)== | ||
+ | |||
+ | We first note that we wish to find <math>3^n \equiv 1 \pmod{11^2}</math> and <math>3^n \equiv 1 \pmod{13^2}.</math> Not thinking of anything else, we try a few numbers for the first condition to get that <math>5 \mid n.</math> For the second condition, upon testing up to 729, we find that it doesn't yield a solution readily, so we use Lifting the Exponent from our toolkit to get that | ||
+ | <cmath>v_{13}(27^m-1^m)=v_{13}(26)+v(m)=1+v(m), 3m = n</cmath> which clearly implies <math>m=13</math> and <math>39 | n.</math> Our answer is then obviously <math>39 \cdot 5 = \boxed{195}.</math> | ||
+ | |||
+ | ~Dhillonr25 | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2018|n=I|num-b=10|num-a=12}} | {{AIME box|year=2018|n=I|num-b=10|num-a=12}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 15:34, 4 February 2023
Contents
Problem
Find the least positive integer such that when is written in base , its two right-most digits in base are .
Solutions
Solution 1
Note that the given condition is equivalent to and . Because , the desired condition is equivalent to and .
If , one can see the sequence so .
Now if , it is harder. But we do observe that , therefore for some integer . So our goal is to find the first number such that . Then, which follows from the binomial theorem. It is not difficult to see that the smallest , so ultimately . Therefore, .
The first satisfying both criteria is thus .
-expiLnCalc
Solution 2
Note that Euler's Totient Theorem would not necessarily lead to the smallest and that in this case that is greater than .
We wish to find the least such that . This factors as . Because , we can simply find the least such that and .
Quick inspection yields and . Now we must find the smallest such that . Euler's gives . So is a factor of . This gives . Some more inspection yields is the smallest valid . So and . The least satisfying both is . (RegularHexagon)
Solution 3 (Big Bash)
Listing out the powers of , modulo and modulo , we have:
The powers of repeat in cycles of and in modulo and modulo , respectively. The answer is .
~Minor edit by Yiyj1
Solution 4 (Order+Bash)
We have that Now, so by the Fundamental Theorem of Orders, and with some bashing, we get that it is . Similarly, we get that . Now, which is our desired solution.
Solution 5 (Easy Binomial Theorem)
We wish to find the smallest such that , so we want and . Note that , so repeats with a period of , so . Now, in order for , then . Because , repeats with a period of , so . Hence, we have that for some positive integer , , so and . Thus, we have that , , and , so the smallest possible value of is . -Stormersyle
Solution 6 (LTE)
We can see that , which means that , . , by the Lifting the Exponent lemma. From the first equation we gather that 5 divides n, while from the second equation we gather that both 13 and 3 divide n as . Therefore the minimum possible value of n is .
-bradleyguo
Solution 7
Note that the problem is basically asking for the least positive integer such that It is easy to see that where is the least positive integer satisfying and the least positive integer satisfying . Luckily, finding is a relatively trivial task, as one can simply notice that . However, finding is slightly more nontrivial. The order of modulo (which is ) is trivial to find, as one can either bash out a pattern of remainders upon dividing powers of by , or one can notice that (the latter which is the definition of period/orders by FLT). We can thus rewrite as . Now suppose that I claim that
Proof: To find we can simply multiply by which is congruent to modulo . By expanding the product out, we obtain and since the on the LHS cancels out, we're left with . Thus, our claim is proven. Let be the second to last digit when is written in base . Using our proof, it is easy to see that satisfies the recurrence and . Since this implies we just have to find the least positive integer such that is a multiple of , which is trivially obtained as . The least integer such that is divisible by is so our final answer is
-fidgetboss_4000 -minor edits made by srisainandan6
Solution 8 (Official MAA)
The requested positive integer is the least value of such that Note that The least power of that is congruent to modulo is It follows that. if and only if for some positive integer .
The least power of that is congruent to modulo is It follows that if and only if for some positive integer . Additionally, for some positive integer , the Binomial Theorem shows that . In particular, if and only if for some positive integer , that is, if and only if
Because and are relatively prime, if and only if and . This occurs if and only if is a multiple of both of the relatively prime integers and , so the least possible value of is
Solution 9 (Motivation and LTE)
We first note that we wish to find and Not thinking of anything else, we try a few numbers for the first condition to get that For the second condition, upon testing up to 729, we find that it doesn't yield a solution readily, so we use Lifting the Exponent from our toolkit to get that which clearly implies and Our answer is then obviously
~Dhillonr25
See Also
2018 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 10 |
Followed by Problem 12 | |
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.