# How to find $m$ if $(x^2 + x + 1) | ((x + 1)^m - x^m - 1)$ [duplicate]

This question already has an answer here:

How to find $m$ if $(x^2 + x + 1) | ((x + 1)^m - x^m - 1)$ I tryed to use eyler theorem, but nothing happens. Sorry for bad english.

## marked as duplicate by Sil, Lord Shark the Unknown abstract-algebra StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Mar 17 at 6:03

• since $x^{2}+x+1=(x-e^{2i\pi /3})(x-e^{i\pi /3})$, maybe you can find $m$ such that $(x+1)^{m}-x^{m}-1=0$, for $x=e^{2i\pi /3}, e^{i\pi /3}$ – Veridian Dynamics Jan 30 '17 at 1:44

If $w=\frac{-1+\sqrt{-3}}{2}$ then $w,\overline w$ are the roots of $x^2+x+1=0$.

Also, $(1+w)^2=w$ and $(1+\overline w)^2=\overline w$, and thus $(1+w)^6=(1+\overline w)^6=1$.

You will get that $x^2+x+1$ is a factor of $(x+1)^m-x^m-1$ exactly when $m\equiv \pm 1\pmod{6}$.

This is because $(1+w)^m-w^m-1=(1+w)^m-(1+w)^{2m}-1$ so $z=(1+w)^{m}$ must be a root of $z-z^2-1$ - that is, $z=\frac{1\pm \sqrt{-3}}{2}=1+w,1+\overline w$.

More directly, since $1+x\equiv -x^2\pmod {x^2+x+1}$, we have:

$$(1+x)^m-x^m-1\equiv (-1)^mx^{2m}-x^m-1\pmod{x^2+x+1}$$

Since $x^3\equiv 1\pmod{x^2+x+1}$, we get:

$$(-1)^mx^{2m} - x^m - 1\equiv \begin{cases}(-1)^m-2&m\equiv 0\pmod{3}\\ (-1)^mx^2-x-1&m\equiv 1\pmod{3}\\ (-1)^mx-x^2-1&m\equiv 2\pmod{3} \end{cases}$$

We see that the divisibility condition is be true, if and only if $m$ is odd and not divisible by $3$.

• Can you please explain two lines after "this is because". Thank you! – Eugene Korotkov Jan 30 '17 at 2:07
• Because $w=(1+w)^2$, $w^m=(1+w)^{2m}$. – Thomas Andrews Jan 30 '17 at 3:08

For readability let's write $p_m(x) = (x+1)^m - x^m -1$. It's easy to show that the polynomials $p_m$ and $p_{m+6}$ have the same remainder when divided by $x^2 + x + 1$. Indeed $p_{m+6}(x)-p_m(x) = (x+1)^m\left( (x+1)^6-1\right) - x^m(x^6-1)$. But we have that $$(x+1)^6-1 = (x^2+x+1)(x^2+3x+3)(x+2)x$$ and $$x^6-1 = (x^2+x+1)(x^2-x+1)(x+1)(x-1)$$ So we only have to check divisibility for $p_5$ and $p_7$.