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.

  • 4
    $\begingroup$ The same question has been posted here, but deleted together with the comments. $\endgroup$ Jun 7 '19 at 8:02
  • $\begingroup$ 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?? $\endgroup$
    – user680303
    Jun 7 '19 at 8:04
  • $\begingroup$ or maybe a source with solution, i think i have seen that before. $\endgroup$
    – user680303
    Jun 7 '19 at 8:18
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 7 '19 at 8:37
  • 1
    $\begingroup$ 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. $\endgroup$ 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,
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
for k in [1..1000] do
    if (Modexp(4,b,qa)+Modexp(2,b,qa)+1) mod qa eq 0  and (k mod 3 eq 0) then
        print "bad1:", a,k;
    end if;
    if (Modexp(4,b,qa)+Modexp(2,b,qa)+1) mod qa ne 0  and (k mod 3 ne 0) then
        print "bad2:", a,k,k mod 3;
    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$.

  • $\begingroup$ First one is true $\endgroup$
    – JWL
    Jun 7 '19 at 9:28
  • $\begingroup$ what about the second one? and, how to prove the first? $\endgroup$
    – user680303
    Jun 7 '19 at 9:31
  • $\begingroup$ @math_here use $a^2 + a + 1 | a^4 + a^2 + 1$. $\endgroup$
    – JWL
    Jun 7 '19 at 10:08
  • $\begingroup$ @JWL I don't get it $\endgroup$
    – user680303
    Jun 7 '19 at 10:13
  • 2
    $\begingroup$ @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$. $\endgroup$ Jun 8 '19 at 3:02

gp-code for $n=2^k$

 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", "))


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

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


$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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy