What is the remainder when $12^{39} + 14^{39}$ is divided by $676$?

Question

I tried following but then I got stuck

$676 = 26*26$

$12^{39} + 14^{39}$ is divisible $26$ for sure since $a^n + b^n$ is divisible by $(a+b)$ when $n$ is odd. But what to do next?

Answer 1

Clearly, $$12^{39}+14^{39}$$ is divisible by $4$

Again, $$12^{39}=(13-1)^{39}\equiv-1+\binom{39}113\pmod{169}\equiv-1$$

$$14^{39}=(13+1)^{39}\equiv1+\binom{39}113\pmod{169}\equiv1$$

More generally if $\displaystyle a\equiv b\pmod p, a^p\equiv b^p\pmod{p^2}$

Here $\displaystyle p=13,12\equiv-1\pmod{13}\implies12^3\equiv(-1)^3\equiv-1$

Similarly, $\displaystyle14\equiv1\pmod{13}\implies14^3\equiv(1)^3$

Answer 2

$$\left((39-12)^{39}+(39-14)^{39}\right) \div 26 \times 26$$ so $$\left(27^{39}+25^{39}\right) \div 26$$ so $$1^{39}+(-1)^{39}$$