Difference between revisions of "2021 AMC 12B Problems/Problem 20"
(→Solution 3 (Directly finding the quotient by using patterns)) |
MRENTHUSIASM (talk | contribs) (→Solution 7 (Factorization)) |
||
(45 intermediate revisions by 7 users not shown) | |||
Line 2: | Line 2: | ||
Let <math>Q(z)</math> and <math>R(z)</math> be the unique polynomials such that<cmath>z^{2021}+1=(z^2+z+1)Q(z)+R(z)</cmath>and the degree of <math>R</math> is less than <math>2.</math> What is <math>R(z)?</math> | Let <math>Q(z)</math> and <math>R(z)</math> be the unique polynomials such that<cmath>z^{2021}+1=(z^2+z+1)Q(z)+R(z)</cmath>and the degree of <math>R</math> is less than <math>2.</math> What is <math>R(z)?</math> | ||
− | <math>\textbf{(A) }-z \qquad \textbf{(B) }-1 \qquad \textbf{(C) }2021\qquad \textbf{(D) }z+1 \qquad \textbf{(E) }2z+1</math> | + | <math>\textbf{(A) }{-}z \qquad \textbf{(B) }{-}1 \qquad \textbf{(C) }2021\qquad \textbf{(D) }z+1 \qquad \textbf{(E) }2z+1</math> |
+ | |||
+ | ==Solution 1 (Difference of Cubes)== | ||
+ | Let <math>z=s</math> be a root of <math>z^2+z+1</math> so that <math>s^2+s+1=0.</math> It follows that <cmath>(s-1)\left(s^2+s+1\right)=s^3-1=0,</cmath> from which <math>s^3=1,</math> but <math>s\neq1.</math> | ||
− | == | + | Note that |
− | ===Solution 1.1=== | + | <cmath>\begin{align*} |
+ | s^{2021}+1 &= s^{3\cdot673+2}+1 \\ | ||
+ | &= (s^3)^{673}\cdot s^2+1 \\ | ||
+ | &= s^2+1 \\ | ||
+ | &= \left(s^2+s+1\right)-s \\ | ||
+ | &= -s. | ||
+ | \end{align*}</cmath> | ||
+ | Since <math>z^{2021}+1=-z</math> for each root <math>z=s</math> of <math>z^2+z+1,</math> the remainder when <math>z^{2021}+1</math> is divided by <math>z^2+z+1</math> is <math>R(z)=\boxed{\textbf{(A) }{-}z}.</math> | ||
+ | |||
+ | ~MRENTHUSIASM | ||
+ | |||
+ | ==Solution 2 (Finds Q(z) Using Patterns)== | ||
+ | |||
+ | Note that the equation above is in the form of polynomial division, with <math>z^{2021}+1</math> being the dividend, <math>z^2+z+1</math> being the divisor, and <math>Q(x)</math> and <math>R(x)</math> being the quotient and remainder respectively. Since the degree of the dividend is <math>2021</math> and the degree of the divisor is <math>2</math>, that means the degree of the quotient is <math>2021-2 = 2019</math>. Note that <math>R(x)</math> can't influence the degree of the right hand side of this equation since its degree is either <math>1</math> or <math>0</math>. Since the coefficients of the leading term in the dividend and the divisor are both <math>1</math>, that means the coefficient of the leading term of the quotient is also <math>1</math>. Thus, the leading term of the quotient is <math>z^{2019}</math>. Multiplying <math>z^{2019}</math> by the divisor gives <math>z^{2021}+z^{2020}+z^{2019}</math>. We have our <math>z^{2021}</math> term but we have these unnecessary terms like <math>z^{2020}</math>. We can get rid of these terms by adding <math>-z^{2018}</math> to the quotient to cancel out these terms, but this then gives us <math>z^{2021}-z^{2018}</math>. Our first instinct will probably be to add <math>z^{2017}</math>, but we can't do this as although this will eliminate the <math>-z^{2018}</math> term, it will produce a <math>z^{2019}</math> term. Since no other term of the form <math>z^n</math> where <math>n</math> is an integer less than <math>2017</math> will produce a <math>z^{2019}</math> term when multiplied by the divisor, we can't add <math>z^{2017}</math> to the quotient. Instead, we can add <math>z^{2016}</math> to the coefficient to get rid of the <math>-z^{2018}</math> term. Continuing this pattern, we get the quotient as <cmath>z^{2019}-z^{2018}+z^{2016}-z^{2015}+\cdots-z^2+1.</cmath> | ||
+ | The last term when multiplied with the divisor gives <math>z^2+z+1</math>. This will get rid of the <math>-z^2</math> term but will produce the expression <math>z+1</math>, giving us the dividend as <math>z^{2021}+z+1</math>. Note that the dividend we want is of the form <math>z^{2021}+1</math>. Therefore, our remainder will have to be <math>-z</math> in order to get rid of the <math>z</math> term in the expression and give us <math>z^{2021}+1</math>, which is what we want. Therefore, the remainder is <math>\boxed{\textbf{(A) }{-}z}.</math> | ||
+ | |||
+ | ~ rohan.sp ~rocketsri | ||
+ | |||
+ | ==Solution 3 (Modular Arithmetic in Polynomials)== | ||
Note that | Note that | ||
<cmath>z^3-1\equiv 0\pmod{z^2+z+1}</cmath> | <cmath>z^3-1\equiv 0\pmod{z^2+z+1}</cmath> | ||
Line 14: | Line 35: | ||
So <math>F(z) = z^2+1</math>, and | So <math>F(z) = z^2+1</math>, and | ||
<cmath>R(z)\equiv F(z) \equiv -z\pmod{z^2+z+1}</cmath> | <cmath>R(z)\equiv F(z) \equiv -z\pmod{z^2+z+1}</cmath> | ||
− | The answer is <math>\boxed{\textbf{(A) } | + | The answer is <math>\boxed{\textbf{(A) }{-}z}.</math> |
− | |||
− | |||
− | |||
− | ==Solution | + | ==Solution 4 (Complex Numbers)== |
− | One thing to note is that <math>R(z)</math> takes the form of <math>Az + B</math> for some constants A and B. | + | One thing to note is that <math>R(z)</math> takes the form of <math>Az + B</math> for some constants <math>A</math> and <math>B.</math> |
− | Note that the roots of <math>z^2 + z + 1</math> are part of the solutions of <math>z^3 -1 = 0</math> | + | Note that the roots of <math>z^2 + z + 1</math> are part of the solutions of <math>z^3 -1 = 0.</math> |
They can be easily solved with roots of unity: | They can be easily solved with roots of unity: | ||
− | <cmath>z^3 = 1 | + | <cmath>\begin{align*} |
− | + | z^3 &= 1 \\ | |
− | + | z^3 &= e^{i 0} \\ | |
− | Obviously the right two solutions are the roots of <math>z^2 + z + 1 = 0</math> | + | z &= e^{i 0}, e^{i \frac{2\pi}{3}}, e^{i\left(-\frac{2\pi}{3}\right)}. |
− | We substitute <math>e^{i \frac{2\pi}{3}}</math> into the original equation, and <math>z^2 + z + 1</math> becomes 0. Using De Moivre's | + | \end{align*}</cmath> |
− | <cmath>e^{i\frac{4042\pi}{3}} + 1 = A \cdot e^{i \frac{2\pi}{3}} + B | + | Obviously the right two solutions are the roots of <math>z^2 + z + 1 = 0.</math> |
− | + | We substitute <math>e^{i \frac{2\pi}{3}}</math> into the original equation, and <math>z^2 + z + 1</math> becomes <math>0.</math> Using De Moivre's Theorem, we get | |
+ | <cmath>\begin{align*} | ||
+ | e^{i\frac{4042\pi}{3}} + 1 &= A \cdot e^{i \frac{2\pi}{3}} + B \\ | ||
+ | e^{i\frac{4\pi}{3}} + 1 &= A \cdot e^{i \frac{2\pi}{3}} + B. | ||
+ | \end{align*}</cmath> | ||
Expanding into rectangular complex number form: | Expanding into rectangular complex number form: | ||
− | <cmath>\frac{1}{2} - \frac{\sqrt{3}}{2} i = (-\frac{1}{2}A + B) + \frac{\sqrt{3}}{2} i | + | <cmath>\frac{1}{2} - \frac{\sqrt{3}}{2} i = \left(-\frac{1}{2}A + B\right) + \frac{\sqrt{3}}{2} A i.</cmath> |
− | Comparing the real and imaginary parts, we get | + | Comparing the real and imaginary parts, we get <math>(A,B) = (-1,0).</math> So, the answer is <math>\boxed{\textbf{(A) }{-}z}.</math> |
− | < | ||
− | |||
− | + | ~Jamess2022 (burntTacos ;-)) | |
− | + | ==Solution 5 (Complex Numbers but Easier)== | |
− | |||
− | + | We have motivation to get rid of the <math>Q(z)</math> term by subtituting in either <math>e^{\frac{2\pi i}{3}}</math> or <math>e^{\frac{4\pi i}{3}}</math> for <math>z</math>, as this sets <math>z^2+z+1</math> equal to <math>0</math>. Doing so, | |
− | |||
− | |||
− | |||
− | |||
− | < | ||
− | |||
− | |||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | + | \left(e^{\frac{2\pi i}{3}}\right)^{2021} + 1 &= R\left(e^{\frac{2\pi i}{3}}\right) \\ | |
− | &= | + | e^{\frac{4042\pi i}{3}} + 1 &= R\left(e^{\frac{2\pi i}{3}}\right) \\ |
− | + | e^{\frac{4\pi i}{3}} + 1 &= R\left(e^{\frac{2\pi i}{3}}\right) \\ | |
+ | \frac{1}{2}-\frac{\sqrt{3}}{2}i &= R\left(-\frac{1}{2} + \frac{\sqrt{3}}{2} i \right). | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | + | This immediately eliminates choices <math>\textbf{(B)}</math> and <math>\textbf{(C)},</math> as they are constants. Upon a quick check, <math>R(z) = 2z+1</math> and <math>z + 1</math> both don't work, as the sign of <math>\frac{\sqrt{3}}{2}</math> has to be negative. Checking <math>R(z)</math> (or realizing that it's the only one that actually works), we see that <math>\boxed{\textbf{(A) }{-}z}</math> is the right answer. | |
+ | |||
+ | -Benedict T (countmath1) | ||
+ | |||
+ | ==Solution 6 (More Complex Numbers)== | ||
+ | Since <math>z^{2021}+1=(z^2+z+1)Q(z)+R(z),</math> we can plug in either <math>\text{cis} (240^{\circ})</math> or <math>\text{cis} (240^{\circ})</math>. Assuming <math>R(z)=ax+b,</math> we have <math>a(\text{cis}(240^{\circ}))+b=\frac{1}{2}+\frac{i\sqrt{3}}{2}</math> and <math>a(\text{cis}(120^{\circ}))+b=\frac{1}{2}-\frac{i\sqrt{3}}{2}.</math> Solving gives us <math>a=-1</math> and <math>b=0</math>, thus <math>R(z)=\boxed{\textbf{(A) }{-}z}.</math> | ||
+ | |||
+ | ~SirAppel | ||
+ | |||
+ | ==Solution 7 (Factorization)== | ||
+ | |||
+ | Notice that <math>(z^{2018} + z^{2015} + z^{2012} + \cdots + z^5 + z^2)(z^2 + z + 1) = z^{2020} + z^{2019} + \cdots + z^{4} + z^3 + z^2</math>, so | ||
<cmath>\begin{align*} | <cmath>\begin{align*} | ||
− | z^{2021}+1&=\ | + | z^{2021} + 1 = z^{2021} - 1 + 2 &= (z-1)( z^{2020} + z^{2019} + \cdots + z^{2} + z + 1 ) + 2 \\ |
− | &=\ | + | &= (z-1)[(z^{2018} + z^{2015} + z^{2012} + \cdots + z^5 + z^2)(z^2 + z + 1) + z + 1] + 2 \\ |
+ | &= (z-1)(z^{2018} + z^{2015} + z^{2012} + \cdots + z^5 + z^2)(z^2 + z + 1) + (z-1)(z+1) + 2 \\ | ||
+ | &= (z-1)(z^{2018} + z^{2015} + z^{2012} + \cdots + z^5 + z^2)(z^2 + z + 1) + z^2 + 1 \\ | ||
+ | &= (z-1)(z^{2018} + z^{2015} + z^{2012} + \cdots + z^5 + z^2)(z^2 + z + 1) + z^2 + z + 1 - z \\ | ||
+ | &= (z^2 + z + 1)[(z^{2018} + z^{2015} + z^{2012} + \cdots + z^5 + z^2)(z-1) + 1] - z. | ||
\end{align*}</cmath> | \end{align*}</cmath> | ||
− | from which <math>R(z)=\boxed{\textbf{(A) }-z} | + | Therefore, we have <cmath>Q(z) = (z^{2018} + z^{2015} + z^{2012} + \cdots + z^5 + z^2)(z-1) + 1,</cmath> from which <math>R(z) = \boxed{\textbf{(A) }{-}z}</math>. |
+ | |||
+ | ~[https://artofproblemsolving.com/wiki/index.php/User:Isabelchen isabelchen] | ||
+ | |||
+ | == Video Solution== | ||
+ | https://youtu.be/3GYJE9aK83k | ||
− | ~ | + | ~MathProblemSolvingSkills.com |
− | == Video Solution by OmegaLearn (Using Modular Arithmetic and Meta- | + | == Video Solution by OmegaLearn (Using Modular Arithmetic and Meta-Solving) == |
https://youtu.be/nnjr17q7fS0 | https://youtu.be/nnjr17q7fS0 | ||
− | ==Video Solution | + | ~ pi_is_3.14 |
+ | |||
+ | ==Video Solution (Long Division, Not Brutal)== | ||
https://youtu.be/kxPDeQRGLEg | https://youtu.be/kxPDeQRGLEg | ||
+ | |||
~hippopotamus1 | ~hippopotamus1 | ||
− | |||
− | |||
==See Also== | ==See Also== | ||
{{AMC12 box|year=2021|ab=B|num-b=19|num-a=21}} | {{AMC12 box|year=2021|ab=B|num-b=19|num-a=21}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 11:43, 24 October 2023
Contents
- 1 Problem
- 2 Solution 1 (Difference of Cubes)
- 3 Solution 2 (Finds Q(z) Using Patterns)
- 4 Solution 3 (Modular Arithmetic in Polynomials)
- 5 Solution 4 (Complex Numbers)
- 6 Solution 5 (Complex Numbers but Easier)
- 7 Solution 6 (More Complex Numbers)
- 8 Solution 7 (Factorization)
- 9 Video Solution
- 10 Video Solution by OmegaLearn (Using Modular Arithmetic and Meta-Solving)
- 11 Video Solution (Long Division, Not Brutal)
- 12 See Also
Problem
Let and
be the unique polynomials such that
and the degree of
is less than
What is
Solution 1 (Difference of Cubes)
Let be a root of
so that
It follows that
from which
but
Note that
Since
for each root
of
the remainder when
is divided by
is
~MRENTHUSIASM
Solution 2 (Finds Q(z) Using Patterns)
Note that the equation above is in the form of polynomial division, with being the dividend,
being the divisor, and
and
being the quotient and remainder respectively. Since the degree of the dividend is
and the degree of the divisor is
, that means the degree of the quotient is
. Note that
can't influence the degree of the right hand side of this equation since its degree is either
or
. Since the coefficients of the leading term in the dividend and the divisor are both
, that means the coefficient of the leading term of the quotient is also
. Thus, the leading term of the quotient is
. Multiplying
by the divisor gives
. We have our
term but we have these unnecessary terms like
. We can get rid of these terms by adding
to the quotient to cancel out these terms, but this then gives us
. Our first instinct will probably be to add
, but we can't do this as although this will eliminate the
term, it will produce a
term. Since no other term of the form
where
is an integer less than
will produce a
term when multiplied by the divisor, we can't add
to the quotient. Instead, we can add
to the coefficient to get rid of the
term. Continuing this pattern, we get the quotient as
The last term when multiplied with the divisor gives
. This will get rid of the
term but will produce the expression
, giving us the dividend as
. Note that the dividend we want is of the form
. Therefore, our remainder will have to be
in order to get rid of the
term in the expression and give us
, which is what we want. Therefore, the remainder is
~ rohan.sp ~rocketsri
Solution 3 (Modular Arithmetic in Polynomials)
Note that
so if
is the remainder when dividing by
,
Now,
So
, and
The answer is
Solution 4 (Complex Numbers)
One thing to note is that takes the form of
for some constants
and
Note that the roots of
are part of the solutions of
They can be easily solved with roots of unity:
Obviously the right two solutions are the roots of
We substitute
into the original equation, and
becomes
Using De Moivre's Theorem, we get
Expanding into rectangular complex number form:
Comparing the real and imaginary parts, we get
So, the answer is
~Jamess2022 (burntTacos ;-))
Solution 5 (Complex Numbers but Easier)
We have motivation to get rid of the term by subtituting in either
or
for
, as this sets
equal to
. Doing so,
This immediately eliminates choices
and
as they are constants. Upon a quick check,
and
both don't work, as the sign of
has to be negative. Checking
(or realizing that it's the only one that actually works), we see that
is the right answer.
-Benedict T (countmath1)
Solution 6 (More Complex Numbers)
Since we can plug in either
or
. Assuming
we have
and
Solving gives us
and
, thus
~SirAppel
Solution 7 (Factorization)
Notice that , so
Therefore, we have
from which
.
Video Solution
~MathProblemSolvingSkills.com
Video Solution by OmegaLearn (Using Modular Arithmetic and Meta-Solving)
~ pi_is_3.14
Video Solution (Long Division, Not Brutal)
~hippopotamus1
See Also
2021 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 19 |
Followed by Problem 21 |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.