My question is as follows: find the number of values of the positive integers $n$ such that the fraction below is also a positive integer:
$$\frac{4^n+2^n+1}{n^2+n+1}$$
I have only been able to establish the bases cases for $n=2$ and $n=4$ which this statement is true for and have been unable to progress further.
Let's prove first that, if $k = 2^s$, then $x^k + x^{k/2} + 1$ is divisible by $x^2+x+1$ over the integers. This is because we can do this single trick, knowing that $(a+b)(a-b) = a^2-b^2$:
$$(x^2+x+1)(x^2-x+1) = (x^2+1)^2 - x^2 = x^4+x^2+1$$ We can apply it again: $$(x^4+x^2+1)(x^4-x^2+1) = (x^4+1)^2-x^4 = x^8+x^4+1$$ It's easy to make an induction proof of the previous statement replicating this process to obtain a factorization of $x^k + x^{k/2}+1$ that contains $x^2+x+1$.
Now, in your fraction $\frac{4^n+2^n+1}{n^2+n+1}$ we can make an hypothesis (seeing the first solutions) that $n = 2^{2^m}$ is always a solution, for each $m\in \mathbb{N}$.
Let's study $4^n$:
$$4^n = 4^{2^{2^m}} = 2^{2\cdot 2^{2^m}} = 2^{2^{2^m+1}} = 2^{2^m2^{2^m+1-m}} = \big(2^{2^m}\big)^{2^{2^m+1-m}}$$
This concludes the proof taking $s=2^m+1-m$, $k=2^s$ and applying the previous lemma, because we have: $$\frac{4^n+2^n+1}{n^2+n+1} = \frac{n^{k}+n^{k/2}+1}{n^2+n+1}$$
This expression can be written as a polynomial with integer coefficients on $n$, and because $n$ is an integer, the result is always an integer. So there is an infinite countable number of solutions.
Side note: These are not the only solutions, $n=215$ also works and it's not one of the mentioned above.
