Find how many integer values 3≤n≤99 satisfy that the polynomial x2+x+1 divides x2n+x+1.
Problem
Source:
Tags: algebra, polynomial
18.09.2021 22:16
Solution: we must have 2n=3k+2, because x3=1. So 2n=3k+2⇒(3−1)n=3k+2⇔M3+(−1)n=3k+2⇒n=2m+1⇒m∈{3,8,...,98} For example if n=3⇒23=8⇒x8+x+1=(x3)2x2+x+1=x2+x+1⋮x2+x+1
18.09.2021 22:32
Let ω be a 3rd root of unity that is not 1, we must have \omega^{2^{n}}+\omega+1=0 \implies x^2=x^{2^{n}} \implies 2 \equiv 2n \pmod{3} \implies n \equiv 1 \pmod{3}.So there are \boxed{32} ns that satisfy this, and namely they are 4, 7, 10, ..., 97. \blacksquare
19.09.2021 15:53
math31415926535 wrote: Let \omega be a 3rd root of unity that is not 1, we must have \omega^{2^{n}}+\omega+1=0 \implies x^2=x^{2^{n}} \implies 2 \equiv 2n \pmod{3} \implies n \equiv 1 \pmod{3}.So there are \boxed{32} ns that satisfy this, and namely they are 4, 7, 10, ..., 97. \blacksquare If n=4\Rightarrow {{2}^{4}}=16\Rightarrow {{x}^{16}}+x+1={{\left( {{x}^{3}} \right)}^{5}}x+x+1=2x+1 it is not divisible by {{x}^{2}}+x+1 , and the others too!
19.09.2021 18:25
The.survivor wrote: math31415926535 wrote: Let \omega be a 3rd root of unity that is not 1, we must have \omega^{2^{n}}+\omega+1=0 \implies x^2=x^{2^{n}} \implies 2 \equiv 2n \pmod{3} \implies n \equiv 1 \pmod{3}.So there are \boxed{32} ns that satisfy this, and namely they are 4, 7, 10, ..., 97. \blacksquare If n=4\Rightarrow {{2}^{4}}=16\Rightarrow {{x}^{16}}+x+1={{\left( {{x}^{3}} \right)}^{5}}x+x+1=2x+1 it is not divisible by {{x}^{2}}+x+1 , and the others too! I don't really get what you mean by that
19.09.2021 18:50
The 4, 7, 10, ..., 97. there are not solutions the solutions there are 3,8,...,98 and proved that your "solution" n=4 do not work.
19.09.2021 19:24
The.survivor wrote: The 4, 7, 10, ..., 97. there are not solutions the solutions there are 3,8,...,98 and proved that your "solution" n=4 do not work. then can you tell me where in my sol is flawed?
19.09.2021 19:27
If n=4\Rightarrow {{2}^{4}}=16\Rightarrow {{x}^{16}}+x+1={{\left( {{x}^{3}} \right)}^{5}}x+x+1=2x+1 it is not divisible by {{x}^{2}}+x+1 , and the others too!
19.09.2021 19:31
I know but can you say why my solution is incorrect? Like which step.
19.09.2021 19:38
\omega^{2^{n}}+\omega+1=0 \implies x^2=x^{2^{n}} \implies 2 \equiv 2n \pmod{3} \implies n \equiv 1 \pmod{3}. Correct: {{\omega }^{{{2}^{n}}}}+\omega +1=0\Rightarrow {{x}^{2}}={{x}^{{{2}^{n}}}}\Rightarrow {{2}^{n}}\equiv 2\quad \left( \bmod 3 \right)
19.09.2021 19:42
o thanks lol, I am pretty dumb
26.08.2024 23:02
Similar to OTIS Mock AIME 2024/7. All odd n work. The idea is to "mod out" by the polynomial x^2 + x + 1 by using x^3 \equiv 1 \pmod{x^2 + x + 1}, which shortcuts the polynomial division algorithm. In particular, if n is odd we have 2^n \equiv 2 \pmod 3 \implies x^{2^n} + x + 1 \equiv x^2 + x + 1 \equiv 0 \pmod{x^2 + x + 1},whereas n even gives 2^n \equiv 1 \pmod 3 \implies x^{2^n} + x + 1 \equiv 2x + 1 \not\equiv 0 \pmod{x^2 + x + 1}.So n works if and only if n is odd, which gives a total of \fbox{49} integers (3, 5, \dots, 99).