Prove $3^x+9^x+1$ is divisible by 13 if $x=3n+1$

Question

I don't know how to start thinking about this problem, I was going to try to prove it by induction, but I think I'm on the wrong path. Any hints?

Answer 1

Note that $3^{3n}\equiv 1 \bmod 13$, and that $9^{3n}\equiv 1 \bmod 13$.

Edit: Typo!

Answer 2

Proposition $$y^{2n}+y^n+1$$ is divisible by $y^2+y+1$ if integer $n$ is not divisible by $3$

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

Consider $n=3m+1,3m+2$

Answer 3

Below put $\,x = 3,\,\ \{A,B,C\} = \{2n,n,0\}\ $ for any $\,n\not\equiv 0\pmod{\!3}$

Lemma $\ x^{2}\!+\!x\!+\!1\mid x^A\! +\! x^B\! +\! x^C\ $ if $ \ \{A,B,C\}\equiv \{2,1,0\}\pmod{\!3}.\ $

Proof $ $ Special case of a simple proof in this answer.