Difference between revisions of "2023 AIME I Problems/Problem 15"
(→Solution) |
(→Problem) |
||
(23 intermediate revisions by 12 users not shown) | |||
Line 1: | Line 1: | ||
− | ==Problem | + | ==Problem== |
Find the largest prime number <math>p<1000</math> for which there exists a complex number <math>z</math> satisfying | Find the largest prime number <math>p<1000</math> for which there exists a complex number <math>z</math> satisfying | ||
− | * the real and imaginary | + | * the real and imaginary part of <math>z</math> are both integers; |
− | * <math>|z|=\sqrt{p}</math> | + | * <math>|z|=\sqrt{p},</math> and |
− | * there exists a triangle | + | * there exists a triangle whose three side lengths are <math>p,</math> the real part of <math>z^{3},</math> and the imaginary part of <math>z^{3}.</math> |
− | == | + | ==Solution== |
− | + | Assume that <math>z=a+bi</math>. Then, | |
+ | <cmath>z^3=(a^3-3ab^2)+(3a^2b-b^3)i</cmath>Note that by the Triangle Inequality, | ||
+ | <cmath>|(a^3-3ab^2)-(3a^2b-b^3)|<p\implies |a^3+b^3-3ab^2-3a^2b|<a^2+b^2</cmath>Thus, we know | ||
+ | <cmath>|a+b||a^2+b^2-4ab|<a^2+b^2</cmath>Without loss of generality, assume <math>a>b</math> (as otherwise, consider <math>i^3\overline z=b+ai</math>). If <math>|a/b|\geq 4</math>, then | ||
+ | <cmath>17b^2\geq a^2+b^2>|a+b||a^2+b^2-4ab|\geq |b-4b||16b^2-16b^2+b^2|=3b^3</cmath>`Thus, this means <math>b\leq\frac{17}3</math> or <math>b\leq 5</math>. Also note that the roots of <math>x^2-4x+1</math> are <math>2\pm\sqrt 3</math>, so thus if <math>b\geq 6</math>, | ||
+ | <cmath>2\sqrt 3b=(2(2-\sqrt 3)-4)b<a<4b</cmath>Note that | ||
+ | <cmath>1000>p=a^2+b^2\geq 12b^2+b^2=13b^2</cmath>so <math>b^2<81</math>, and <math>b<9</math>. If <math>b=8</math>, then <math>16\sqrt 3\leq a\leq 32</math>. Note that <math>\gcd(a,b)=1</math>, and <math>a\not\equiv b\pmod 2</math>, so <math>a=29</math> or <math>31</math>. However, then <math>5\mid a^2+b^2</math>, absurd. | ||
+ | |||
+ | If <math>b=7</math>, by similar logic, we have that <math>14\sqrt 3 <a< 28</math>, so <math>b=26</math>. However, once again, <math>5\mid a^2+b^2</math>. If <math>b=6</math>, by the same logic, <math>12\sqrt3<a<24</math>, so <math>a=23</math>, where we run into the same problem. Thus <math>b\leq 5</math> indeed. | ||
+ | |||
+ | If <math>b=5</math>, note that | ||
+ | <cmath>(a+5)(a^2+25-20a)<a^2+25\implies a<20</cmath>We note that <math>p=5^2+18^2=349</math> works. Thus, we just need to make sure that if <math>b\leq 4</math>, <math>a\leq 18</math>. But this is easy, as | ||
+ | <cmath>p>(a+b)(a^2+b^2-4ab)\geq (4+18)(4^2+18^2-4\cdot 4\cdot 18)>1000</cmath>absurd. Thus, the answer is <math>\boxed{349}</math>. | ||
− | |||
+ | ==Solution 2== | ||
Denote <math>z = a + i b</math>. Thus, <math>a^2 + b^2 = p</math>. | Denote <math>z = a + i b</math>. Thus, <math>a^2 + b^2 = p</math>. | ||
Line 19: | Line 31: | ||
Because <math>p</math>, <math>{\rm Re} \left( z^3 \right)</math>, <math>{\rm Im} \left( z^3 \right)</math> are three sides of a triangle, we have <math>{\rm Re} \left( z^3 \right) > 0</math> and <math>{\rm Im} \left( z^3 \right) > 0</math>. | Because <math>p</math>, <math>{\rm Re} \left( z^3 \right)</math>, <math>{\rm Im} \left( z^3 \right)</math> are three sides of a triangle, we have <math>{\rm Re} \left( z^3 \right) > 0</math> and <math>{\rm Im} \left( z^3 \right) > 0</math>. | ||
Thus, | Thus, | ||
+ | <cmath> | ||
\begin{align*} | \begin{align*} | ||
a \left( a^2 - 3 b^2 \right) & > 0 , \hspace{1cm} (1) \\ | a \left( a^2 - 3 b^2 \right) & > 0 , \hspace{1cm} (1) \\ | ||
b \left( - b^2 + 3 a^2 \right) & > 0. \hspace{1cm} (2) | b \left( - b^2 + 3 a^2 \right) & > 0. \hspace{1cm} (2) | ||
\end{align*} | \end{align*} | ||
+ | </cmath> | ||
Because <math>p</math>, <math>{\rm Re} \left( z^3 \right)</math>, <math>{\rm Im} \left( z^3 \right)</math> are three sides of a triangle, we have the following triangle inequalities: | Because <math>p</math>, <math>{\rm Re} \left( z^3 \right)</math>, <math>{\rm Im} \left( z^3 \right)</math> are three sides of a triangle, we have the following triangle inequalities: | ||
+ | <cmath> | ||
\begin{align*} | \begin{align*} | ||
{\rm Re} \left( z^3 \right) + {\rm Im} \left( z^3 \right) & > p \hspace{1cm} (3) \\ | {\rm Re} \left( z^3 \right) + {\rm Im} \left( z^3 \right) & > p \hspace{1cm} (3) \\ | ||
Line 30: | Line 45: | ||
p + {\rm Im} \left( z^3 \right) & > {\rm Re} \left( z^3 \right) \hspace{1cm} (5) | p + {\rm Im} \left( z^3 \right) & > {\rm Re} \left( z^3 \right) \hspace{1cm} (5) | ||
\end{align*} | \end{align*} | ||
+ | </cmath> | ||
We notice that <math>| z^3 | = p^{3/2}</math>, and <math>{\rm Re} \left( z^3 \right)</math>, <math>{\rm Im} \left( z^3 \right)</math>, and <math>| z^3 |</math> form a right triangle. Thus, <math>{\rm Re} z^3 + {\rm Im} z^3 > p^{3/2}</math>. | We notice that <math>| z^3 | = p^{3/2}</math>, and <math>{\rm Re} \left( z^3 \right)</math>, <math>{\rm Im} \left( z^3 \right)</math>, and <math>| z^3 |</math> form a right triangle. Thus, <math>{\rm Re} z^3 + {\rm Im} z^3 > p^{3/2}</math>. | ||
Line 36: | Line 52: | ||
Conditions (4) and (5) can be written in the joint form as | Conditions (4) and (5) can be written in the joint form as | ||
− | + | <cmath> | |
\left| {\rm Re} \left( z^3 \right) - {\rm Im} \left( z^3 \right) \right| < p . \hspace{1cm} (4) | \left| {\rm Re} \left( z^3 \right) - {\rm Im} \left( z^3 \right) \right| < p . \hspace{1cm} (4) | ||
− | + | </cmath> | |
+ | |||
We have | We have | ||
+ | <cmath> | ||
\begin{align*} | \begin{align*} | ||
{\rm Re} \left( z^3 \right) - {\rm Im} \left( z^3 \right) | {\rm Re} \left( z^3 \right) - {\rm Im} \left( z^3 \right) | ||
Line 46: | Line 64: | ||
& = \left( a + b \right) \left( a^2 - 4 ab + b^2 \right) | & = \left( a + b \right) \left( a^2 - 4 ab + b^2 \right) | ||
\end{align*} | \end{align*} | ||
+ | </cmath> | ||
and <math>p = a^2 + b^2</math>. | and <math>p = a^2 + b^2</math>. | ||
Thus, (5) can be written as | Thus, (5) can be written as | ||
− | + | <cmath> | |
\left| \left( a + b \right) \left( a^2 - 4 ab + b^2 \right) \right| | \left| \left( a + b \right) \left( a^2 - 4 ab + b^2 \right) \right| | ||
< a^2 + b^2 . \hspace{1cm} (6) | < a^2 + b^2 . \hspace{1cm} (6) | ||
− | + | </cmath> | |
Therefore, we need to jointly solve (1), (2), (6). | Therefore, we need to jointly solve (1), (2), (6). | ||
Line 59: | Line 78: | ||
Thus, (1) and (2) are reduced to | Thus, (1) and (2) are reduced to | ||
− | + | <cmath> | |
a > \sqrt{3} b . \hspace{1cm} (7) | a > \sqrt{3} b . \hspace{1cm} (7) | ||
− | + | </cmath> | |
Let <math>a = \lambda b</math>. Plugging this into (6), we get | Let <math>a = \lambda b</math>. Plugging this into (6), we get | ||
+ | <cmath> | ||
\begin{align*} | \begin{align*} | ||
\left| \left( \left( \lambda - 2 \right)^2 - 3 \right) \right| | \left| \left( \left( \lambda - 2 \right)^2 - 3 \right) \right| | ||
< \frac{1}{b} \frac{\lambda^2 + 1}{\lambda + 1} . \hspace{1cm} (8) | < \frac{1}{b} \frac{\lambda^2 + 1}{\lambda + 1} . \hspace{1cm} (8) | ||
\end{align*} | \end{align*} | ||
+ | </cmath> | ||
Because <math>p= a^2 + b^2</math> is a prime, <math>a</math> and <math>b</math> are relatively prime. | Because <math>p= a^2 + b^2</math> is a prime, <math>a</math> and <math>b</math> are relatively prime. | ||
Line 74: | Line 95: | ||
To facilitate efficient search, we apply the following criteria: | To facilitate efficient search, we apply the following criteria: | ||
− | \begin{enumerate} | + | |
+ | \begin{enumerate*} | ||
\item To satisfy (7) and <math>a^2 + b^2 < 1000</math>, we have <math>1 \leq b \leq 15</math>. | \item To satisfy (7) and <math>a^2 + b^2 < 1000</math>, we have <math>1 \leq b \leq 15</math>. | ||
In the outer layer, we search for <math>b</math> in a decreasing order. | In the outer layer, we search for <math>b</math> in a decreasing order. | ||
Line 85: | Line 107: | ||
Thus, <math>\sqrt{3} < \lambda \leq \frac{30}{9}</math>. | Thus, <math>\sqrt{3} < \lambda \leq \frac{30}{9}</math>. | ||
Thus, the R.H.S. of (8) has the following upper bound | Thus, the R.H.S. of (8) has the following upper bound | ||
+ | <cmath> | ||
\begin{align*} | \begin{align*} | ||
\frac{1}{b} \frac{\lambda^2 + 1}{\lambda + 1} | \frac{1}{b} \frac{\lambda^2 + 1}{\lambda + 1} | ||
Line 92: | Line 115: | ||
& < \frac{10}{27} . | & < \frac{10}{27} . | ||
\end{align*} | \end{align*} | ||
+ | </cmath> | ||
Hence, to satisfy (8), a necessary condition is | Hence, to satisfy (8), a necessary condition is | ||
+ | <cmath> | ||
\begin{align*} | \begin{align*} | ||
\left| \left( \left( \lambda - 2 \right)^2 - 3 \right) \right| | \left| \left( \left( \lambda - 2 \right)^2 - 3 \right) \right| | ||
< \frac{10}{27} . | < \frac{10}{27} . | ||
\end{align*} | \end{align*} | ||
+ | </cmath> | ||
However, this cannot be satisfied for <math>\sqrt{3} < \lambda \leq \frac{30}{9}</math>. | However, this cannot be satisfied for <math>\sqrt{3} < \lambda \leq \frac{30}{9}</math>. | ||
Line 106: | Line 132: | ||
\item We use the following criteria to quickly eliminate <math>a</math> that make <math>a^2 + b^2</math> a composite number. | \item We use the following criteria to quickly eliminate <math>a</math> that make <math>a^2 + b^2</math> a composite number. | ||
− | + | ||
− | + | * For <math>b \equiv 1 \pmod{2}</math>, we eliminate <math>a</math> satisfying <math>a \equiv 1 \pmod{2}</math>. | |
− | + | ||
− | + | * For <math>b \equiv \pm 1 \pmod{5}</math> (resp. <math>b \equiv \pm 2 \pmod{5}</math>), we eliminate <math>a</math> satisfying <math>a \equiv \pm 2 \pmod{5}</math> (resp. <math>a \equiv \pm 1 \pmod{5}</math>). | |
+ | |||
\item For the remaining <math>\left( b, a \right)</math>, check whether (8) and the condition that <math>a^2 + b^2</math> is prime are both satisfied. | \item For the remaining <math>\left( b, a \right)</math>, check whether (8) and the condition that <math>a^2 + b^2</math> is prime are both satisfied. | ||
Line 117: | Line 144: | ||
\item For the remaining search, given <math>b</math>, we only search for <math>a \geq \sqrt{349 - b^2}</math>. | \item For the remaining search, given <math>b</math>, we only search for <math>a \geq \sqrt{349 - b^2}</math>. | ||
− | |||
Following the above search criteria, we find the final answer as <math>b = 5</math> and <math>a = 18</math>. | Following the above search criteria, we find the final answer as <math>b = 5</math> and <math>a = 18</math>. | ||
Line 123: | Line 149: | ||
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ||
+ | |||
+ | ==Video Solution== | ||
+ | |||
+ | https://youtu.be/V0KFMIXmp08 | ||
+ | |||
+ | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) | ||
+ | |||
+ | |||
+ | ==Video Solution== | ||
+ | |||
+ | https://youtu.be/tELK8fy36bs | ||
+ | |||
+ | ~MathProblemSolvingSkills.com | ||
+ | |||
+ | |||
+ | ==Animated Video Solution== | ||
+ | |||
+ | https://youtu.be/1Y8ql7eHt34 | ||
+ | |||
+ | ~Star League (https://starleague.us) | ||
+ | |||
+ | |||
+ | ==See also== | ||
+ | {{AIME box|year=2023|n=I|num-b=14|after=Last Problem}} | ||
+ | |||
+ | [[Category:Intermediate Algebra Problems]] | ||
+ | [[Category:Intermediate Number Theory Problems]] | ||
+ | {{MAA Notice}} |
Latest revision as of 00:49, 21 August 2024
Contents
Problem
Find the largest prime number for which there exists a complex number satisfying
- the real and imaginary part of are both integers;
- and
- there exists a triangle whose three side lengths are the real part of and the imaginary part of
Solution
Assume that . Then, Note that by the Triangle Inequality, Thus, we know Without loss of generality, assume (as otherwise, consider ). If , then `Thus, this means or . Also note that the roots of are , so thus if , Note that so , and . If , then . Note that , and , so or . However, then , absurd.
If , by similar logic, we have that , so . However, once again, . If , by the same logic, , so , where we run into the same problem. Thus indeed.
If , note that We note that works. Thus, we just need to make sure that if , . But this is easy, as absurd. Thus, the answer is .
Solution 2
Denote . Thus, .
Thus,
Because , , are three sides of a triangle, we have and . Thus,
Because , , are three sides of a triangle, we have the following triangle inequalities:
We notice that , and , , and form a right triangle. Thus, . Because , . Therefore, (3) holds.
Conditions (4) and (5) can be written in the joint form as
We have
and .
Thus, (5) can be written as
Therefore, we need to jointly solve (1), (2), (6). From (1) and (2), we have either , or . In (6), by symmetry, without loss of generality, we assume .
Thus, (1) and (2) are reduced to
Let . Plugging this into (6), we get
Because is a prime, and are relatively prime.
Therefore, we can use (7), (8), , and and are relatively prime to solve the problem.
To facilitate efficient search, we apply the following criteria:
\begin{enumerate*} \item To satisfy (7) and , we have . In the outer layer, we search for in a decreasing order. In the inner layer, for each given , we search for . \item Given , we search for in the range . \item We can prove that for , there is no feasible . The proof is as follows.
For , to satisfy , we have . Thus, . Thus, the R.H.S. of (8) has the following upper bound
Hence, to satisfy (8), a necessary condition is
However, this cannot be satisfied for . Therefore, there is no feasible solution for . Therefore, we only need to consider .
\item We eliminate that are not relatively prime to .
\item We use the following criteria to quickly eliminate that make a composite number.
- For , we eliminate satisfying .
- For (resp. ), we eliminate satisfying (resp. ).
\item For the remaining , check whether (8) and the condition that is prime are both satisfied.
The first feasible solution is and . Thus, .
\item For the remaining search, given , we only search for .
Following the above search criteria, we find the final answer as and . Thus, the largest prime is .
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Video Solution
~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)
Video Solution
~MathProblemSolvingSkills.com
Animated Video Solution
~Star League (https://starleague.us)
See also
2023 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 14 |
Followed by Last Problem | |
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.