Lemma: $x^2+x+1 \mid x^{2k}+x^k+1$ if $3 \nmid k$.

Proof.

Now let $n=2^{2^t}$. We have $x=2^{2^t}$ and $k=2^{2^t-t}$ in the Lemma. The result follows.

Let $f(n)=n^2+n+1$. Hence $f(n^2)=n^4+n^2+1=(n^2+n+1)(n^2–n+1)$ is divisible by $f(n)$ and using induction $f(n)| f (n^{2^k})$. Now let $n=2^{2^m}$ and for $k=2^m-m$ we have $f(n)| f(2^n)$. Therefore, $4^n+2^n+1/n^2+n+1$ is a positive integer for infinitely many positive integers n.

Let $n = {2^{2^t}}$ from @pablock Then This equation simplifies to $\frac{{4^{2^{2^t}}}+2^{2^{2^{t}}}+1}{{4^{2^{2^t}}}+2^{2^{2^{t}}}+1}$ $\iff$ $\frac{256^t+16t+1}{256^t+16t+1}$ $= 1$. Therefore $\frac{4^n+2^n+1}{n^2+n+1}$ is always an integer. MathGenius_ and I contributed to this problem and based our solution off of pablock's idea. Please verify if this is correct.

Someone please check if @above is correct.

VicKmath7 wrote: Let f(n)=n2+n+1. Hence f(n^2)=n^4+n^2+1=(n^2+n+1)(n^2–n+1) is divisible by f(n) and using induction f(n)| f (n^2^k). Now let n=2^2^m and for k=2^m-m we have f(n)| f(2^n). Therefore, 4^n+2^n+1/n^2+n+1 is a positive integer for infinitely many positive integers n. Please use $\LaTeX$ next time.

Rikki123 wrote: Let $n = {2^{2^t}}$ from @pablock Then This equation simplifies to $\frac{{4^{2^{2^t}}}+2^{2^{2^{t}}}+1}{{4^{2^{2^t}}}+2^{2^{2^{t}}}+1}$ $\iff$ $\frac{256^t+16t+1}{256^t+16t+1}$ $= 1$. Therefore $\frac{4^n+2^n+1}{n^2+n+1}$ is always an integer. MathGenius_ and I contributed to this problem and based our solution off of pablock's idea. Please verify if this is correct. Correct

This is also Kosovo TST 2019 P3

Rikki123 wrote: Let $n = {2^{2^t}}$ from @pablock Then This equation simplifies to $\frac{{4^{2^{2^t}}}+2^{2^{2^{t}}}+1}{{4^{2^{2^t}}}+2^{2^{2^{t}}}+1}$ $\iff$ $\frac{256^t+16t+1}{256^t+16t+1}$ $= 1$. Therefore $\frac{4^n+2^n+1}{n^2+n+1}$ is always an integer. MathGenius_ and I contributed to this problem and based our solution off of pablock's idea. Please verify if this is correct. hey guys i think @pablock is having some little mistakes here

when you look the solution seems so easy but how were you motivated to solve in this way.

The idea is just letting $n=2^{2^k},$ motivated by the fact that $x^2+x+1\mid x^{2p}+x^{p}+1$ for $3\nmid p$ by roots of unity. Now note that $4^n+2^n+1=(2^{2^{2^k}})^2+2^{2^{2^k}}+1.$ Note that for obvious reasons, $2^k\mid 2^{2^k},$ so we are done.

dchenmathcounts wrote: The idea is just letting $n=2^{2^k},$ motivated by the fact that $x^2+x+1\mid x^{2p}+x^{p}+1$ for $3\nmid p$ by roots of unity. Now note that $4^n+2^n+1=(2^{2^{2^k}})^2+2^{2^{2^k}}+1.$ Note that for obvious reasons, $2^k\mid 2^{2^k},$ so we are done. $ x^2+x+1|x^{2p}+x^p+1 $, I did not know that That is why we need to study Number Theory

Take $n =2^{2^{\alpha}}$ motivated when you see $n^3 - 1 \mid 2^{3n} - 1$ and proved using roots of unity like above posts.

A perhaps slightly motivated solution (probably just the same thing). The form of $n$ which works is highly motivated by looking at small examples, and trying constructive ideas. We claim that all integers of the form $n=2^{2^r}$ satisfy the given condition. We first make the observation that for all positive integers $m$, \[m^3 - 1 = (m-1)(m^2+m+1)\]Thus, the given fraction can be rewritten as, \[\frac{2^{3n}-1}{2^{n-1}}\cdot \frac{n-1}{n^3-1}\]Thus we wish to show that for all positive integers $r$, \[\frac{2^{3\cdot 2^{2^r}}-1}{2^{2^{2^r}}-1}\cdot \frac{2^{2^r}-1}{2^{3\cdot 2^r}-1}\]is an integer. Now, we consider prime divisors $p$ of the denominator. Note that since the denominator is clearly odd, $p\ne 2$. We have two cases. Case 1 : For a prime $p$ divisor of the denominator, $p$ divides exactly one of $2^{2^{2^r}}-1$ and $2^{3\cdot 2^r}-1$. We sort out the case where $p\mid 2^{2^{2^r}}-1$. The argument can be copied to the other case. Note that, since $2^{2^r} \mid 3 \cdot 2^{2^r}$ $p\mid 2^{3\cdot 2^{2^r}}-1$ as well. Further by the Lifting the Exponent Lemma we have, \[\nu_p(2^{3\cdot 2^{2^r}}-1)=\nu_p(2^{2^{2^r}}-1)+\nu_p(3) \ge \nu_p(2^{2^{2^r}}-1)\] Case 2 : For a prime $p$ divisor of the denominator, $p$ divides both $2^{2^{2^r}}-1$ and $2^{3\cdot 2^r}-1$. Then, \[\text{ord}_p(2) \mid 2^{2^r} \text{ and } \text{ord}_p(2) \mid 3\cdot 2^r\]from which it is not hard to see that, \[\text{ord}_p(2) \mid 2^r\]But then, $p\mid 2^{2^r}-1$ as well. We now repeat the argument using the Lifting the Exponent Lemma. Note, \[\nu_p(2^{3\cdot 2^{2^r}}-1)=\nu_p(2^{2^r}-1)+\nu_p(3\cdot 2^{2^{2^r-r}}) =\nu_p(2^{2^r}-1)+\nu_p(3) + \nu_p(2^{2^{2^r-r}}) \]\[\nu_p(2^{2^{2^r}}-1)=\nu_p(2^{2^r}-1)+\nu_p(2^{{2^{2^r}-r}})\]and \[\nu_p(2^{3\cdot 2^r}-1) = \nu_p(2^{2^r}-1)+\nu_p(3)\]From which we have that \[\nu_p\left((2^{3\cdot 2^{2^r}}-1)(2^{2^r}-1)\right) \ge \nu_p\left((2^{2^{2^r}}-1)(2^{3\cdot 2^r}-1)\right)\]which finishes the proof.