Kvant Math Problem 309

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m32s
Source on kvant.digital

Problem

1. For which $n$ is the polynomial $x^{2n}+x^n+1$ divisible by $x^2+x+1$?
2. For which $n$ is the number $1\underbrace{0\ldots0}_n1\underbrace{0\ldots0}_n1$ divisible by 37?

V. G. Shleifer

Exploration

For the first question, divisibility by $x^2+x+1$ suggests evaluating the polynomial at the nonreal cube roots of unity. Let $\omega^3=1$ and $\omega\neq1$. Then $\omega^2+\omega+1=0$, and $x^2+x+1$ divides a polynomial $P(x)$ if and only if $P(\omega)=0$.

Compute

$$P(\omega)=\omega^{2n}+\omega^n+1.$$

Since $\omega^3=1$, only the residue class of $n$ modulo $3$ matters.

If $n\equiv0\pmod3$, then $\omega^n=1$ and

$$P(\omega)=1+1+1=3\neq0.$$

If $n\equiv1\pmod3$, then

$$P(\omega)=\omega^2+\omega+1=0.$$

If $n\equiv2\pmod3$, then

$$P(\omega)=\omega+\omega^2+1=0.$$

Small checks confirm this: for $n=1$ the polynomial itself is $x^2+x+1$; for $n=2$,

$$x^4+x^2+1=(x^2+x+1)(x^2-x+1);$$

for $n=3$,

$$x^6+x^3+1,$$

and substituting $\omega$ gives $3$.

For the second question, the number is

$$N=10^{2n+2}+10^{n+1}+1.$$

Since $37=3\cdot37/3$ is closely related to $10^3-1=999=27\cdot37$, powers of $10$ modulo $37$ should have period $3$. Indeed,

$$10^3\equiv1\pmod{37}.$$

Hence only $n+1$ modulo $3$ matters.

Let $k=n+1$. Then

$$N=10^{2k}+10^k+1.$$

If $k\equiv0\pmod3$, then $10^k\equiv1$, so

$$N\equiv3\not\equiv0\pmod{37}.$$

If $k\equiv1\pmod3$, then $10^k\equiv10$ and

$$N\equiv10^2+10+1=111=3\cdot37.$$

If $k\equiv2\pmod3$, then $10^k\equiv10^2\equiv26$,

$$N\equiv26^2+26+1=703=19\cdot37.$$

Thus divisibility occurs exactly when $k\not\equiv0\pmod3$, namely when $n\not\equiv2\pmod3$.

The only potentially delicate point is translating divisibility by $x^2+x+1$ into evaluation at a primitive cube root of unity and checking that no other condition is needed.

Problem Understanding

This is a Type A problem. We must determine all positive integers $n$ satisfying each divisibility condition and prove that no other values of $n$ work.

In the first part, the core difficulty is recognizing that $x^2+x+1$ is the minimal polynomial of the primitive cube roots of unity.

In the second part, the core difficulty is expressing the decimal number in algebraic form and exploiting the congruence $10^3\equiv1\pmod{37}$.

The answers are:

For part 1, all $n$ such that $n\not\equiv0\pmod3$.

For part 2, all $n$ such that $n\not\equiv2\pmod3$.

The reason is that in both problems the relevant expressions reduce to $t^2+t+1$, where $t$ has order $3$.

Proof Architecture

The first lemma is that $x^2+x+1$ divides a polynomial $P(x)$ if and only if $P(\omega)=0$, where $\omega$ is a primitive cube root of unity. This follows because $x^2+x+1$ is the minimal polynomial of $\omega$ over the rationals.

The second lemma is that

$$\omega^{2n}+\omega^n+1=0$$

if and only if $n\not\equiv0\pmod3$. This follows by checking the three residue classes modulo $3$.

The third lemma is that the number

$$1\underbrace{0\ldots0}_n1\underbrace{0\ldots0}_n1$$

equals

$$10^{2n+2}+10^{n+1}+1.$$

The fourth lemma is that

$$10^3\equiv1\pmod{37}.$$

Hence $10^k$ modulo $37$ depends only on $k$ modulo $3$.

The fifth lemma is that

$$10^{2k}+10^k+1\equiv0\pmod{37}$$

if and only if $k\not\equiv0\pmod3$. This is verified by checking the three residue classes.

The most delicate step is the first lemma, because it connects polynomial divisibility with evaluation at a primitive cube root of unity.

Solution

Part 1

Let

$$P(x)=x^{2n}+x^n+1.$$

Let $\omega$ be a primitive cube root of unity. Then

$$\omega^3=1,\qquad \omega\neq1,$$

and

$$\omega^2+\omega+1=0.$$

Since $x^2+x+1$ is the minimal polynomial of $\omega$, the polynomial $x^2+x+1$ divides $P(x)$ if and only if

$$P(\omega)=0.$$

Now

$$P(\omega)=\omega^{2n}+\omega^n+1.$$

There are three possible residue classes of $n$ modulo $3$.

If $n\equiv0\pmod3$, then $\omega^n=1$, hence

$$P(\omega)=1+1+1=3\neq0.$$

If $n\equiv1\pmod3$, then

$$P(\omega)=\omega^2+\omega+1=0.$$

If $n\equiv2\pmod3$, then

$$P(\omega)=\omega+\omega^2+1=0.$$

Thus

$$x^2+x+1\mid x^{2n}+x^n+1$$

exactly when

$$n\not\equiv0\pmod3.$$

Part 2

Let

$$N=1\underbrace{0\ldots0}_n1\underbrace{0\ldots0}_n1.$$

The rightmost digit $1$ contributes $1$, the middle digit $1$ contributes $10^{n+1}$, and the leftmost digit $1$ contributes $10^{2n+2}$. Therefore

$$N=10^{2n+2}+10^{n+1}+1.$$

Put

$$k=n+1.$$

Then

$$N=10^{2k}+10^k+1.$$

Since

$$10^3=1000=37\cdot27+1,$$

we have

$$10^3\equiv1\pmod{37}.$$

Hence the value of $10^k$ modulo $37$ depends only on $k$ modulo $3$.

If $k\equiv0\pmod3$, then $10^k\equiv1$, and

$$N\equiv1+1+1=3\not\equiv0\pmod{37}.$$

If $k\equiv1\pmod3$, then $10^k\equiv10$, and

$$N\equiv10^2+10+1=111=3\cdot37\equiv0\pmod{37}.$$

If $k\equiv2\pmod3$, then

$$10^k\equiv10^2\equiv100\equiv26\pmod{37},$$

and

$$N\equiv26^2+26+1=703=19\cdot37\equiv0\pmod{37}.$$

Thus $N$ is divisible by $37$ exactly when

$$k\not\equiv0\pmod3.$$

Since $k=n+1$, this is equivalent to

$$n+1\not\equiv0\pmod3,$$

or

$$n\not\equiv2\pmod3.$$

Hence the answers are

$$\boxed{\text{Part 1: }n\not\equiv0\pmod3,\qquad \text{Part 2: }n\not\equiv2\pmod3.}$$

Verification of Key Steps

For the first part, the crucial fact is that $x^2+x+1$ is the minimal polynomial of a primitive cube root of unity $\omega$. Since $\omega$ is a root of $x^2+x+1$ and the polynomial is irreducible over $\mathbb Q$, a polynomial with rational coefficients is divisible by $x^2+x+1$ precisely when it vanishes at $\omega$. Without this justification, evaluating at $\omega$ would establish only a necessary condition.

For the residue computation, the three cases $n\equiv0,1,2\pmod3$ exhaust all possibilities. When $n\equiv0\pmod3$, substituting $\omega^n=1$ gives $3$, not $0$. When $n\equiv1$ or $2$, the expression becomes $\omega^2+\omega+1$, which is $0$. No other cases exist.

For the second part, the decimal representation must be converted correctly. The number has a $1$ in positions $0$, $n+1$, and $2n+2$, counted from the units place. Hence

$$N=10^{2n+2}+10^{n+1}+1.$$

An incorrect exponent shift by $1$ would change the final congruence condition.

Alternative Approaches

For the first part, one may divide $x^{3n}-1$ by $x^n-1$:

$$x^{2n}+x^n+1=\frac{x^{3n}-1}{x^n-1}.$$

Since $x^2+x+1$ divides $x^3-1$, it divides $x^{3n}-1$ for every $n$. The question becomes whether it also divides $x^n-1$. This happens exactly when $3\mid n$. Hence the quotient is divisible by $x^2+x+1$ precisely when $3\nmid n$.

For the second part, write

$$N=10^{2k}+10^k+1.$$

Since $10^3\equiv1\pmod{37}$, the residue $t=10^k$ satisfies $t^3\equiv1$. Then

$$t^3-1=(t-1)(t^2+t+1).$$

If $k\not\equiv0\pmod3$, then $t\not\equiv1\pmod{37}$ and therefore $t^2+t+1\equiv0\pmod{37}$. This yields the same criterion with a closer analogy to the first part.