Difference between revisions of "2021 AMC 12B Problems/Problem 20"
Jamess2022 (talk | contribs) (→Solution) |
MRENTHUSIASM (talk | contribs) m (→Solution 4 (Division Analysis Without Finding Q(z))) |
||
(26 intermediate revisions by 5 users not shown) | |||
Line 5: | Line 5: | ||
==Solution 1== | ==Solution 1== | ||
+ | ===Solution 1.1=== | ||
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 15: | Line 16: | ||
The answer is <math>\boxed{\textbf{(A) }-z}.</math> | The answer is <math>\boxed{\textbf{(A) }-z}.</math> | ||
− | ==Solution 2 ( | + | ===Solution 1.2 (More Thorough Version of Solution 1.1)=== |
+ | Instead of dealing with a nasty <math>z^2+z+1</math>, we can instead deal with the nice <math>z^3 - 1</math>, as <math>z^2+z+1</math> is a factor of <math>z^3-1</math>. Then, we try to see what <math>\frac{z^{2021} + 1}{z^3 - 1}</math> is. Of course, we will need a <math>z^{2018}</math>, getting <math>z^{2021} - z^{2018}</math>. Then, we've gotta get rid of the <math>z^{2018}</math> term, so we add a <math>z^{2015}</math>, to get <math>z^{2021} - z^{2015}</math>. This pattern continues, until we add a <math>z^2</math> to get rid of <math>z^5</math>, and end up with <math>z^{2021} - z^2</math>. We can't add anything more to get rid of the <math>z^2</math>, so our factor is <math>z^{2018} + z^{2015} + z^{2012} + \cdots + z^2</math>. Then, to get rid of the <math>z^2</math>, we must have a remainder of <math>+z^2</math>, and to get the <math>+1</math> we have to also have a <math>+1</math> in the remainder. So, our product is <cmath>z^{2021}+1= (z^3-1)(z^{2018} + z^{2015} + \cdots + z^2) + z^2+1.</cmath> Then, our remainder is <math>z^2+1</math>. The remainder when dividing by <math>z^3-1</math> must be the same when dividing by <math>z^2+z+1</math>, modulo <math>z^2+z+1</math>. So, we have that <math>z^2 + 1 \equiv R(z) \pmod{z^2+z+1}</math>, or <math>R(z) \equiv -z\pmod{z^2+z+1}</math>. This corresponds to answer choice <math>\boxed{\textbf{(A)} ~ -z}</math>. ~rocketsri | ||
+ | |||
+ | ==Solution 2 (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 A and B. | ||
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> | ||
Line 21: | Line 25: | ||
<cmath>z^3 = 1</cmath> | <cmath>z^3 = 1</cmath> | ||
<cmath>z^3 = e^{i 0}</cmath> | <cmath>z^3 = e^{i 0}</cmath> | ||
− | <cmath>z = e^{i 0}, e^{i \frac{2\pi}{3}}, e^{i -\frac{2\pi}{3}}</cmath> | + | <cmath>z = e^{i 0}, e^{i \frac{2\pi}{3}}, e^{i -\frac{2\pi}{3}}</cmath> <cmath>\newline</cmath> |
Obviously the right two solutions are the roots of <math>z^2 + z + 1 = 0</math> | 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 0. Using De Moivre's theorem, we get: | 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 theorem, we get: | ||
Line 30: | Line 34: | ||
Comparing the real and imaginary parts, we get: | Comparing the real and imaginary parts, we get: | ||
<cmath>A = -1, B = 0</cmath> | <cmath>A = -1, B = 0</cmath> | ||
− | The answer is <math>\boxed{\textbf{(A) }-z}</math>. | + | The answer is <math>\boxed{\textbf{(A) }-z}</math>. ~Jamess2022(burntTacos;-;) |
+ | |||
+ | ==Solution 3 (Directly finding the quotient by using patterns)(Probably one for MSM peeps)== | ||
+ | |||
+ | 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 R(x) 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}+....-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 \qquad}</math> | ||
+ | |||
+ | ~ rohan.sp | ||
+ | |||
+ | ==Solution 4 (Division Analysis Without Finding Q(z))== | ||
+ | By the difference of cubes or the short geometric series, we get <cmath>\left(z-1\right)\left(z^2+z+1\right)=z^3-1.</cmath> | ||
+ | We rewrite <math>\left(z^{2021}+1\right)\div\left(z^3-1\right)</math> by the polynomial division algorithm: | ||
+ | <cmath>z^{2021}+1=\left(z^3-1\right)Q'(z)+R'(z), \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (*)</cmath> | ||
+ | where <math>Q'(z)</math> and <math>R'(z)</math> are unique polynomials such that <math>\mathrm{deg}\left(R'(z)\right)<3.</math> Taking <math>(*)</math> in modulo <math>z^3-1</math> (in which <math>z^3\equiv1</math>), we have <cmath>z^{2021}+1=z^{3\cdot673+2}+1=z^{3\cdot673}z^2+1=\left(z^3\right)^{673}z^2+1\equiv z^2+1=R'(z).</cmath> | ||
+ | Substituting <math>R'(z)=z^2+1</math> back into <math>(*)</math> gives | ||
+ | <cmath>\begin{align*} | ||
+ | z^{2021}+1&=\left(z^3-1\right)Q'(z)+\left(z^2+1\right) \\ | ||
+ | &=(z-1)\left(z^2+z+1\right)Q'(z)+\left(z^2+1\right) \\ | ||
+ | &=\left(z^2+z+1\right)\left[(z-1)Q'(z)\right]+\left(z^2+1\right), \hspace{7.04mm} (**) | ||
+ | \end{align*}</cmath> | ||
+ | which almost resembles to the original equation <cmath>z^{2021}+1=(z^2+z+1)Q(z)+R(z).</cmath> Since we require that <math>\mathrm{deg}\left(R(z)\right)<2,</math> the divisor <math>z^2+z+1</math> goes into the remaining <math>z^2+1</math> for one more time. Rewriting <math>(**)</math> produces | ||
+ | <cmath>\begin{align*} | ||
+ | z^{2021}+1&=\left(z^2+z+1\right)\left[(z-1)Q'(z)+1\right]+\left[\left(z^2+1\right)-\left(z^2+z+1\right)\right] \\ | ||
+ | &=\left(z^2+z+1\right)\underbrace{\left[(z-1)Q'(z)+1\right]}_{Q(z)}+\underbrace{[-z]}_{R(z)}, | ||
+ | \end{align*}</cmath> | ||
+ | from which <math>R(z)=\boxed{\textbf{(A) }-z}.</math> | ||
+ | |||
+ | ~MRENTHUSIASM | ||
== Video Solution by OmegaLearn (Using Modular Arithmetic and Meta-solving) == | == Video Solution by OmegaLearn (Using Modular Arithmetic and Meta-solving) == | ||
https://youtu.be/nnjr17q7fS0 | https://youtu.be/nnjr17q7fS0 | ||
+ | |||
+ | ==Video Solution using long division(not brutal)== | ||
+ | https://youtu.be/kxPDeQRGLEg | ||
+ | ~hippopotamus1 | ||
~ pi_is_3.14 | ~ pi_is_3.14 |
Revision as of 20:09, 6 April 2021
Contents
- 1 Problem
- 2 Solution 1
- 3 Solution 2 (Complex numbers)
- 4 Solution 3 (Directly finding the quotient by using patterns)(Probably one for MSM peeps)
- 5 Solution 4 (Division Analysis Without Finding Q(z))
- 6 Video Solution by OmegaLearn (Using Modular Arithmetic and Meta-solving)
- 7 Video Solution using long division(not brutal)
- 8 See Also
Problem
Let and be the unique polynomials such thatand the degree of is less than What is
Solution 1
Solution 1.1
Note that so if is the remainder when dividing by , Now, So , and The answer is
Solution 1.2 (More Thorough Version of Solution 1.1)
Instead of dealing with a nasty , we can instead deal with the nice , as is a factor of . Then, we try to see what is. Of course, we will need a , getting . Then, we've gotta get rid of the term, so we add a , to get . This pattern continues, until we add a to get rid of , and end up with . We can't add anything more to get rid of the , so our factor is . Then, to get rid of the , we must have a remainder of , and to get the we have to also have a in the remainder. So, our product is Then, our remainder is . The remainder when dividing by must be the same when dividing by , modulo . So, we have that , or . This corresponds to answer choice . ~rocketsri
Solution 2 (Complex numbers)
One thing to note is that takes the form of for some constants A and B. 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 0. Using De Moivre's theorem, we get: Expanding into rectangular complex number form: Comparing the real and imaginary parts, we get: The answer is . ~Jamess2022(burntTacos;-;)
Solution 3 (Directly finding the quotient by using patterns)(Probably one for MSM peeps)
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 R(x) 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
Solution 4 (Division Analysis Without Finding Q(z))
By the difference of cubes or the short geometric series, we get We rewrite by the polynomial division algorithm: where and are unique polynomials such that Taking in modulo (in which ), we have Substituting back into gives which almost resembles to the original equation Since we require that the divisor goes into the remaining for one more time. Rewriting produces from which
~MRENTHUSIASM
Video Solution by OmegaLearn (Using Modular Arithmetic and Meta-solving)
Video Solution using long division(not brutal)
https://youtu.be/kxPDeQRGLEg ~hippopotamus1
~ pi_is_3.14
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.