×

# There's only 2023066 cases to check

How many polynomials are there of the form $$x^m + x^n + 1$$, where $$m$$ and $$n$$ are positive integers such that $$1 \leq m < n \leq 2012$$, that are divisible by $$x^2 + x + 1$$? Give proof.

Note by Sharky Kesa
2 years, 2 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

Very simply, substitute x=ω. This gives n=3k+1 and m=3k+2 and vice-versa. Now simply count the number of cases.

- 2 years, 2 months ago

I'm getting $$671^{2}$$ polynomials.

- 2 years, 2 months ago

Can you give proof?

- 2 years, 2 months ago

Ok.

If $$f(x)=x^{m} + x^{n} + 1$$is divisible by $$g(x)=x^{2} + x+1$$, then the roots of $$g(x)$$ must also be the roots of $$f(x)$$. Or that $$f(r_{1})=f(r_{2})=0$$ where $$r_{1}$$ and $$r_{2}$$ are the roots of $$g(x)$$.

Since in order for $$f(r_{1})=f(r_{2})=0$$, we must find some value of $$n$$ and $$m$$ to be such that $$r_1^n+r_1^m=-1$$ and $$r_2^n+r_2^m=-1$$

The roots of $$g(x)$$ are $r_1=-\left(-1\right)^{\frac{1}{3}}=-\frac{1}{2}-\frac{i\sqrt{3}}{2}$ $r_2=\left(-1\right)^{\frac{2}{3}}=-\frac{1}{2}+\frac{i\sqrt{3}}{2}$

It can be seen that $$r_1^n=r_1^{n+3k}$$ and $$r_2^n=r_2^{n+3k}$$ where $$n$$ and $$k$$ are some integers. And that $$r_1+r_1^2=r_2+r_2^2=-1$$

Hence, either $$m$$ or $$n$$ has to be of the form $$3k+1$$ while the other has to be of $$3k+2$$, where $$k$$ is an integer.

The number of possible values of $$m$$ and $$n$$ that satisfy the boundaries $$1\leq m < n \leq 2012$$ can be calculated to be $$671^{2}$$

- 2 years, 2 months ago

Nice solution. Now list them all!!! (Mwa-ha-ha-ha-ha) :P

- 2 years, 2 months ago

Well I did not understand a single thing please elaborate (from $$r_{1}^{n}$$ line, please!)

- 2 years, 2 months ago