Show that $4^{3x+1} + 2^{3x+1}+ 1$ is divisible by 7

I want to show that $4^{3x+1} + 2^{3x+1} + 1$ is divisible by 7, I am trying to show this with modular arithmetic.

If I break up each part of the equation, I can see that

$4^{3x+1} = 4$ x $2^{6x}$

which implies that $4^{3x+1}mod(7) = 4$

I can't quite find a nice factorization of $2^{3x+1}$

Any help specifically on how to treat $2^{3x+1}$ would be appreciated.

• 2^(3x+1) mod(7) gives 2 – Chen Guo Dec 29 '17 at 2:23
• and 1mod(7) gives 1 so 4+2+1 = 7 – Chen Guo Dec 29 '17 at 2:24

Hint: $$2^{3x+1} = 8^x\times 2$$ $$8 \equiv 1\pmod{7} \implies 8^x \equiv 1 \pmod{7}\implies 8^x \times 2\equiv 2\pmod{7}.$$

$X:=2^{3x+1}=2\cdot (7+1)^x \equiv 2\pmod{7}$. Hence $$X^2+X+1 \equiv 2^2+2+1 \equiv 0\pmod{7}.$$

For natural $x$ we have $$4^{3x+1}+2^{3x+1}=4\cdot64^x+2\cdot8^x+1=4(64^x-1)+2(8^x-1)+7\equiv0\pmod{7}.$$

• $4\times 64^x$. – OmG Dec 29 '17 at 2:27
• It was typo. Thank you! I fixed. – Michael Rozenberg Dec 29 '17 at 2:28

Attempt at induction.

$\begin{array}\\ 4^{3(x+1)+1} + 2^{3(x+1)+1} &=4^{3x+1+3} + 2^{3x+1+3}\\ &=4^34^{3x+1} + 2^32^{3x+1}\\ &=64\cdot 4^{3x+1} + 8\cdot 2^{3x+1}\\ &=(63+1)\cdot 4^{3x+1} + (7+1)\cdot 2^{3x+1}\\ &=63\cdot 4^{3x+1} + 7\cdot 2^{3x+1}+4^{3x+1}+2^{3x+1}\\ &=7(9\cdot 4^{3x+1} + 2^{3x+1})+4^{3x+1}+2^{3x+1}\\ &\equiv 4^{3x+1}+2^{3x+1}\pmod{7}\\ \end{array}$

Therefore, if $4^{3x+1} + 2^{3x+1} + 1 \equiv 0 \pmod{7}$ then $4^{3(x+1)+1} + 2^{3(x+1)+1} + 1 \equiv 0 \pmod{7}$.

Since $4^{3x+1} + 2^{3x+1} + 1 \equiv 0 \pmod{7}$ for $x = 0$, it is true for all $x$.

If $x^2+x+1=0,x=w$ where $w$ is a complex cube root of unity.

$$x^{2m}+x^m+1=w^{2m}+w^m+1= \begin{cases}(w^3)^{2n}+(w^3)^n+1=3 &\mbox{if }m=3n\\ w^{2(3n+1)}+w^{3n+1}+1=w^2+w+1=0 & \mbox{if }m=3n+1\\=\cdot=0 & \mbox{if }m=3n+2 \end{cases}$$

$\implies x^2+x+1$ will divide $x^{2m}+x^m+1$ if $3\nmid m$

$$4^3\equiv 2^3\equiv 1\pmod{7} \tag{A}$$ $$4^{3x}\equiv 2^{3x}\equiv 1\pmod{7}\tag{B}$$ $$4^{3x+1}+2^{3x+1}+1\equiv 4+2+1 \equiv 0\pmod{7}.\tag{C}$$