# Prove that there are infinitely many integers $n>0$ such that $n^2+n+1$ divides $4^n+2^n+1$

Prove that there are infinitely many integers $$n>0$$ such that $$n^2+n+1$$ divides $$4^n+2^n+1$$.

I have tried for a long time to prove that possibly $$n=2^m$$ works and this gives with some manipulations and etc $$m=2^k$$, so $$n=2^{2^k}$$ and then in order the assertion to hold, $$2^{2^k}+1$$ must be prime, i.e. a Fermat one, but we don't know if they are infinite or not ... I did not have any more ideas ... possibly setting $$n=k^m$$ with appropriate $$k, m$$ don't know.

• The same question has been posted here, but deleted together with the comments. Jun 7 '19 at 8:02
• yeah i know, cause my first pos t there had been on-hold since i hadn't written my proccess, so i wrote it here again. any solutions??
– user680303
Jun 7 '19 at 8:04
• or maybe a source with solution, i think i have seen that before.
– user680303
Jun 7 '19 at 8:18
• Why do you need a Fermat Prime? Perhaps if you would explain more of your argument you might get more help. Also it would be nice to know where this problem comes from. Jun 7 '19 at 8:37
• Why did you not EDIT the first version into shape!!!!!??? Now we have an orphaned question. The question is interesting but I downvote simply because reposting a question is against the site rules. Jun 8 '19 at 4:30

ans:=[n: n in [2^(2^k):k in [0..11]] | (Modexp(4,n,n^2+n+1)+Modexp(2,n,n^2+n+1)+1) mod (n^2+n+1)  eq 0 ]; print #ans, ans;


After running the above magma script, it outputs

12 [ 2, 4, 16, 256, 65536, 4294967296, 18446744073709551616,
340282366920938463463374607431768211456,
115792089237316195423570985008687907853269984665640564039457584007913129639936,
13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096,
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216,
32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656 ]


So, I would like to conjecture that it holds from $$n=2^{2^k}$$, $$k\ge 1$$. In fact, we have the following result.

Theorem 1: $${4^{2^{k}}}+2^{2^k}+1 \mid 4^{2^{2^k}}+2^{2^{2^k}}+1$$ for every $$k\ge 1$$.

for a in [1..1000] do
qa:=4^a+2^a+1;
for k in [1..1000] do
b:=a*k;
if (Modexp(4,b,qa)+Modexp(2,b,qa)+1) mod qa eq 0  and (k mod 3 eq 0) then
end if;
if (Modexp(4,b,qa)+Modexp(2,b,qa)+1) mod qa ne 0  and (k mod 3 ne 0) then
end if;
end for;
end for;


Moreover, by running the above magma script, I would like to give a more generic conjecture.

Conjecture 2: $$4^a+2^a+1\mid 4^b+2^b+1$$ if and only if $$b=ar$$ where $$r\not\equiv 0\pmod{3}$$.

Proposition 3: $$2^{2^k-k}\not\equiv 0 \pmod{3}$$ for every $$k\ge 1$$.

Althought we have proved Theorem 1 which answers the question in OP, but we think Conjecture 2 is more interesting. If Conjecutre 2 is true, then let $$a=2^k$$ and $$b=2^{2^k}$$. We have $$r=\frac{b}{a}=2^{2^k-k}$$. Then Theorem 1 will hold for every $$k\ge 1$$. Therefore, this will answer the question if Conjecture 2 is true. Howver, we cannot prove Conjecture 2 at this moments.

==============================================

@John Omielan gave some hints. So I will try to proof Theorem 1. Proof of Theorem 1: Obviously, $$a^4+a^2+1=(a^2+a+1)(a^2-a+1)$$ for any $$a\in \mathbb{Z}$$. Thus $$a^2+a+1 \mid a^4+a^2+1.$$ Replace $$a$$ with $$a^2$$ and we have $$a^4+a^2+1 \mid a^8+a^4+1.$$ Generally, by repeating $$j\ge 0$$ times, we have $$a^{2^{j+1}}+a^{2^{j}}+1 \mid a^{2^{j+2}}+a^{2^{j+1}}+1.$$ Therefore for any $$j\ge 0$$, we have $$a^2+a+1 \mid a^{2^{j+2}}+a^{2^{j+1}}+1.$$ Let $$a=2^{2^{k}}$$. We have $$a^2+a+1=(2^{2^{k}})^2+2^{2^{k}}+1={4^{2^{k}}}+2^{2^k}+1$$ and $$a^{2^{j+2}}+a^{2^{j+1}}+1=(2^{2^k})^{2^{j+2}}+(2^{2^{k}})^{2^{j+1}}+1=4^{2^{k+j+1}}+2^{2^{k+j+1}}+1.$$ Due to the arbitrariness of $$j\ge 0$$, there exists a $$j$$ such that $$j=2^k-k-1$$ for any $$k\ge 1$$. So $$k+j+1=2^k$$. Consequently, it becomes $${4^{2^{k}}}+2^{2^k}+1 \mid 4^{2^{2^k}}+2^{2^{2^k}}+1$$.

• First one is true
– JWL
Jun 7 '19 at 9:28
• what about the second one? and, how to prove the first?
– user680303
Jun 7 '19 at 9:31
• @math_here use $a^2 + a + 1 | a^4 + a^2 + 1$.
– JWL
Jun 7 '19 at 10:08
• @JWL I don't get it
– user680303
Jun 7 '19 at 10:13
• @math_here As JWL stated, $a^2 + a + 1 \mid a^4 + a^2 + 1$. You can repeat this with $a$ replaced with $a^2$ to get $a^4 + a^2 + 1 \mid a^8 + a^4 + 1$, so $a^2 + a + 1 \mid a^8 + a^4 + 1$. Doing this $j$ times in total gives that $a^2 + a + 1 \mid a^{2m} + a^m + 1$ where $m = 2^{j+2}$. Consider now what happens at some point when $a$ is an appropriate power of $2$ as stated in Conjecture $1$. Jun 8 '19 at 3:02

gp-code for $$n=2^k$$

znl()=
{
for(k=1, 10^4,
n= 2^k; m= n^2+n+1;
a= Mod(2,m)^n; b= a^2;
if(a+b==m-1, print1(n", "))
)
};


Output:

? \r znl.gp
? znl()
2, 4, 16, 256, 65536, 4294967296, 18446744073709551616, 34028236692093846346337460743176
8211456, 115792089237316195423570985008687907853269984665640564039457584007913129639936,
134078079299425970995740249982058461274793658205923933777235614437217640300735469768018
74298166903427690031858186486050853753882811946569946433649006084096,


But how find sequence $$n\neq2^k$$, aka $$215$$?

215,3692374808,...


$$m(3692374808)$$ also is prime.

Interesting fact for $$n=3692374808$$: $$\quad 2^{\frac{n(n+1)}{3}}\equiv3^{\frac{n(n+1)}{3}}\equiv n^2\pmod{n^2+n+1}$$.