Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2023 AIME I Problems/Problem 15"

(→‎Solution)
(→‎Solution)
Line 19: Line 19:
 
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,
−
\begin{eqnarray*}
+
<cmath>
 +
\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{eqnarray*}
+
\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 33:
 
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 40:
  
 
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 52:
 
& = \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 66:
  
 
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 85: Line 94:
 
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 102:
 
& < \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>.

Revision as of 12:31, 8 February 2023

Problem 15

Find the largest prime number $p<1000$ for which there exists a complex number $z$ satisfying

  • the real and imaginary parts of $z$ are integers;
  • $|z|=\sqrt{p}$, and
  • there exists a triangle with side lengths $p$, the real part of $z^{3}$, and the imaginary part of $z^{3}$.

Answer: 349

Suppose $z=a+bi$; notice that $\arg(z^{3})\approx 45^{\circ}$, so by De Moivre’s theorem $\arg(z)\approx 15^{\circ}$ and $\tfrac{b}{a}\approx tan(15^{\circ})=2-\sqrt{3}$. Now just try pairs $(a, b)=(t, \left(2-\sqrt{3}\right)t)$ going down from $t=\lfloor\sqrt{1000}\rfloor$, writing down the value of $a^{2}+b^{2}$ on the right; and eventually we arrive at $(a, b)=(18, 5)$ the first time $a^{2}+b^{2}$ is prime. Therefore, $p=\boxed{349}$.

Solution

Denote $z = a + i b$. Thus, $a^2 + b^2 = p$.

Thus, \[z^3 = a \left( a^2 - 3 b^2 \right) + i b \left( - b^2 + 3 a^2 \right) .\]

Because $p$, ${\rm Re} \left( z^3 \right)$, ${\rm Im} \left( z^3 \right)$ are three sides of a triangle, we have ${\rm Re} \left( z^3 \right) > 0$ and ${\rm Im} \left( z^3 \right) > 0$. Thus, \begin{align*} a \left( a^2 - 3 b^2 \right) & > 0 , \hspace{1cm} (1) \\ b \left( - b^2 + 3 a^2 \right) & > 0. \hspace{1cm} (2) \end{align*}

Because $p$, ${\rm Re} \left( z^3 \right)$, ${\rm Im} \left( z^3 \right)$ are three sides of a triangle, we have the following triangle inequalities: \begin{align*} {\rm Re} \left( z^3 \right) + {\rm Im} \left( z^3 \right) & > p \hspace{1cm} (3) \\ p + {\rm Re} \left( z^3 \right) & > {\rm Im} \left( z^3 \right) \hspace{1cm} (4) \\ p + {\rm Im} \left( z^3 \right) & > {\rm Re} \left( z^3 \right) \hspace{1cm} (5) \end{align*}

We notice that $| z^3 | = p^{3/2}$, and ${\rm Re} \left( z^3 \right)$, ${\rm Im} \left( z^3 \right)$, and $| z^3 |$ form a right triangle. Thus, ${\rm Re} z^3 + {\rm Im} z^3 > p^{3/2}$. Because $p > 1$, $p^{3/2} > p$. Therefore, (3) holds.

Conditions (4) and (5) can be written in the joint form as \[\left| {\rm Re} \left( z^3 \right) - {\rm Im} \left( z^3 \right) \right| < p . \hspace{1cm} (4)\]


We have \begin{align*} {\rm Re} \left( z^3 \right) - {\rm Im} \left( z^3 \right) & = \left( a^3 - 3 a b^2 \right) - \left( - b^3 + 3 a^2 b \right) \\ & = \left( a + b \right) \left( a^2 - 4 ab + b^2 \right) \end{align*} and $p = a^2 + b^2$.

Thus, (5) can be written as \[\left| \left( a + b \right) \left( a^2 - 4 ab + b^2 \right) \right| < a^2 + b^2 . \hspace{1cm} (6)\]

Therefore, we need to jointly solve (1), (2), (6). From (1) and (2), we have either $a, b >0$, or $a, b < 0$. In (6), by symmetry, without loss of generality, we assume $a, b > 0$.

Thus, (1) and (2) are reduced to \[a > \sqrt{3} b . \hspace{1cm} (7)\]

Let $a = \lambda b$. Plugging this into (6), we get \begin{align*} \left| \left( \left( \lambda - 2 \right)^2 - 3 \right) \right| < \frac{1}{b} \frac{\lambda^2 + 1}{\lambda + 1} . \hspace{1cm} (8) \end{align*}

Because $p= a^2 + b^2$ is a prime, $a$ and $b$ are relatively prime.

Therefore, we can use (7), (8), $a^2 + b^2 <1000$, and $a$ and $b$ are relatively prime to solve the problem.

To facilitate efficient search, we apply the following criteria: \begin{enumerate} \item To satisfy (7) and $a^2 + b^2 < 1000$, we have $1 \leq b \leq 15$. In the outer layer, we search for $b$ in a decreasing order. In the inner layer, for each given $b$, we search for $a$. \item Given $b$, we search for $a$ in the range $\sqrt{3} b < a < \sqrt{1000 - b^2}$. \item We can prove that for $b \geq 9$, there is no feasible $a$. The proof is as follows.

For $b \geq 9$, to satisfy $a^2 + b^2 < 1000$, we have $a \leq 30$. Thus, $\sqrt{3} < \lambda \leq \frac{30}{9}$. Thus, the R.H.S. of (8) has the following upper bound \begin{align*} \frac{1}{b} \frac{\lambda^2 + 1}{\lambda + 1} & < \frac{1}{b} \frac{\lambda^2 + \lambda}{\lambda + 1} \\ & = \frac{\lambda}{b} \\ & \leq \frac{\frac{30}{9}}{9} \\ & < \frac{10}{27} . \end{align*}

Hence, to satisfy (8), a necessary condition is \begin{align*} \left| \left( \left( \lambda - 2 \right)^2 - 3 \right) \right| < \frac{10}{27} . \end{align*}

However, this cannot be satisfied for $\sqrt{3} < \lambda \leq \frac{30}{9}$. Therefore, there is no feasible solution for $b \geq 9$. Therefore, we only need to consider $b \leq 8$.

\item We eliminate $a$ that are not relatively prime to $b$.

\item We use the following criteria to quickly eliminate $a$ that make $a^2 + b^2$ a composite number. \begin{enumerate} \item For $b \equiv 1 \pmod{2}$, we eliminate $a$ satisfying $a \equiv 1 \pmod{2}$. \item For $b \equiv \pm 1 \pmod{5}$ (resp. $b \equiv \pm 2 \pmod{5}$), we eliminate $a$ satisfying $a \equiv \pm 2 \pmod{5}$ (resp. $a \equiv \pm 1 \pmod{5}$). \end{enumerate}

\item For the remaining $\left( b, a \right)$, check whether (8) and the condition that $a^2 + b^2$ is prime are both satisfied.

The first feasible solution is $b = 5$ and $a = 18$. Thus, $a^2 + b^2 = 349$.

\item For the remaining search, given $b$, we only search for $a \geq \sqrt{349 - b^2}$. \end{enumerate}

Following the above search criteria, we find the final answer as $b = 5$ and $a = 18$. Thus, the largest prime $p$ is $p = a^2 + b^2 = \boxed{\textbf{(349) }}$.

~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com)

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2023_AIME_I_Problems/Problem_15&oldid=188868"