Difference between revisions of "2023 AIME I Problems/Problem 15"
R00tsofunity (talk | contribs) (Created page with "==Problem 15== Find the largest prime number <math>p<1000</math> for which there exists a complex number <math>z</math> satisfying * the real and imaginary parts of <math>z</m...") |
|||
Line 7: | Line 7: | ||
==Answer: 349== | ==Answer: 349== | ||
Suppose <math>z=a+bi</math>; notice that <math>\arg(z^{3})\approx 45^{\circ}</math>, so by De Moivre’s theorem <math>\arg(z)\approx 15^{\circ}</math> and <math>\tfrac{b}{a}\approx tan(15^{\circ})=2-\sqrt{3}</math>. Now just try pairs <math>(a, b)=(t, \left(2-\sqrt{3}\right)t)</math> going down from <math>t=\lfloor\sqrt{1000}\rfloor</math>, writing down the value of <math>a^{2}+b^{2}</math> on the right; and eventually we arrive at <math>(a, b)=(18, 5)</math> the first time <math>a^{2}+b^{2}</math> is prime. Therefore, <math>p=\boxed{349}</math>. | Suppose <math>z=a+bi</math>; notice that <math>\arg(z^{3})\approx 45^{\circ}</math>, so by De Moivre’s theorem <math>\arg(z)\approx 15^{\circ}</math> and <math>\tfrac{b}{a}\approx tan(15^{\circ})=2-\sqrt{3}</math>. Now just try pairs <math>(a, b)=(t, \left(2-\sqrt{3}\right)t)</math> going down from <math>t=\lfloor\sqrt{1000}\rfloor</math>, writing down the value of <math>a^{2}+b^{2}</math> on the right; and eventually we arrive at <math>(a, b)=(18, 5)</math> the first time <math>a^{2}+b^{2}</math> is prime. Therefore, <math>p=\boxed{349}</math>. | ||
+ | |||
+ | ==Solution== | ||
+ | |||
+ | Denote <math>z = a + i b</math>. Thus, <math>a^2 + b^2 = p</math>. | ||
+ | |||
+ | Thus, | ||
+ | \[ | ||
+ | z^3 = a \left( a^2 - 3 b^2 \right) + i b \left( - b^2 + 3 a^2 \right) . | ||
+ | \] | ||
+ | |||
+ | 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, | ||
+ | \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 <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: | ||
+ | \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 <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>. | ||
+ | Because <math>p > 1</math>, <math>p^{3/2} > p</math>. | ||
+ | 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 <math>p = a^2 + b^2</math>. | ||
+ | |||
+ | 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 <math>a, b >0</math>, or <math>a, b < 0</math>. | ||
+ | In (6), by symmetry, without loss of generality, we assume <math>a, b > 0</math>. | ||
+ | |||
+ | Thus, (1) and (2) are reduced to | ||
+ | \[ | ||
+ | a > \sqrt{3} b . \hspace{1cm} (7) | ||
+ | \] | ||
+ | |||
+ | Let <math>a = \lambda b</math>. 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 <math>p= a^2 + b^2</math> is a prime, <math>a</math> and <math>b</math> are relatively prime. | ||
+ | |||
+ | Therefore, we can use (7), (8), <math>a^2 + b^2 <1000</math>, and <math>a</math> and <math>b</math> are relatively prime to solve the problem. | ||
+ | |||
+ | To facilitate efficient search, we apply the following criteria: | ||
+ | \begin{enumerate} | ||
+ | \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 inner layer, for each given <math>b</math>, we search for <math>a</math>. | ||
+ | \item Given <math>b</math>, we search for <math>a</math> in the range <math>\sqrt{3} b < a < \sqrt{1000 - b^2}</math>. | ||
+ | \item We can prove that for <math>b \geq 9</math>, there is no feasible <math>a</math>. | ||
+ | The proof is as follows. | ||
+ | |||
+ | For <math>b \geq 9</math>, to satisfy <math>a^2 + b^2 < 1000</math>, we have <math>a \leq 30</math>. | ||
+ | Thus, <math>\sqrt{3} < \lambda \leq \frac{30}{9}</math>. | ||
+ | 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 <math>\sqrt{3} < \lambda \leq \frac{30}{9}</math>. | ||
+ | Therefore, there is no feasible solution for <math>b \geq 9</math>. | ||
+ | Therefore, we only need to consider <math>b \leq 8</math>. | ||
+ | |||
+ | \item We eliminate <math>a</math> that are not relatively prime to <math>b</math>. | ||
+ | |||
+ | \item We use the following criteria to quickly eliminate <math>a</math> that make <math>a^2 + b^2</math> a composite number. | ||
+ | \begin{enumerate} | ||
+ | \item For <math>b \equiv 1 \pmod{2}</math>, we eliminate <math>a</math> satisfying <math>a \equiv 1 \pmod{2}</math>. | ||
+ | \item 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>). | ||
+ | \end{enumerate} | ||
+ | |||
+ | \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. | ||
+ | |||
+ | The first feasible solution is <math>b = 5</math> and <math>a = 18</math>. | ||
+ | Thus, <math>a^2 + b^2 = 349</math>. | ||
+ | |||
+ | \item For the remaining search, given <math>b</math>, we only search for <math>a \geq \sqrt{349 - b^2}</math>. | ||
+ | \end{enumerate} | ||
+ | |||
+ | Following the above search criteria, we find the final answer as <math>b = 5</math> and <math>a = 18</math>. | ||
+ | Thus, the largest prime <math>p</math> is <math>p = a^2 + b^2 = \boxed{\textbf{(349) }}</math>. | ||
+ | |||
+ | ~Steven Chen (Professor Chen Education Palace, www.professorchenedu.com) |
Revision as of 13:28, 8 February 2023
Problem 15
Find the largest prime number for which there exists a complex number
satisfying
- the real and imaginary parts of
are integers;
, and
- there exists a triangle with side lengths
, the real part of
, and the imaginary part of
.
Answer: 349
Suppose ; notice that
, so by De Moivre’s theorem
and
. Now just try pairs
going down from
, writing down the value of
on the right; and eventually we arrive at
the first time
is prime. Therefore,
.
Solution
Denote . Thus,
.
Thus, \[ z^3 = a \left( a^2 - 3 b^2 \right) + i b \left( - b^2 + 3 a^2 \right) . \]
Because ,
,
are three sides of a triangle, we have
and
.
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 ,
,
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 , and
,
, and
form a right triangle. Thus,
.
Because
,
.
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 .
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 , or
.
In (6), by symmetry, without loss of generality, we assume
.
Thus, (1) and (2) are reduced to \[ a > \sqrt{3} b . \hspace{1cm} (7) \]
Let . 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 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
\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 .
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.
\begin{enumerate}
\item For
, we eliminate
satisfying
.
\item For
(resp.
), we eliminate
satisfying
(resp.
).
\end{enumerate}
\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
.
\end{enumerate}
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)