×

# 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
1 year, 4 months ago

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. · 1 year, 4 months ago

I'm getting $$671^{2}$$ polynomials. · 1 year, 4 months ago

Can you give proof? · 1 year, 4 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}$$ · 1 year, 4 months ago

Nice solution. Now list them all!!! (Mwa-ha-ha-ha-ha) :P · 1 year, 4 months ago

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