How to prove that $53^{103}+ 103^{53}$ is divisible by 39?

As $39=13\cdot3$

For non-negative integers $m,n$

$\displaystyle53\equiv1\pmod{13}\implies53^n\equiv1$ and $\displaystyle103\equiv-1\pmod{13}\implies103^{53}\equiv(-1)^{53}$

$\displaystyle\implies53^{103}+103^{53}\equiv1+(-1)\pmod{13}$

and $\displaystyle53\equiv-1\pmod3\implies53^{103}\equiv(-1)^{103}$ and $\displaystyle103\equiv1\pmod3\implies103^m\equiv1$

$\displaystyle\implies53^{103}+103^{53}\equiv-1+(1)\pmod3$

$$53\equiv14\pmod{39},103\equiv-14\pmod{53}$$

$$53^{103}+103^{53}\equiv14^{103}+(-14)^{53}\pmod{39}\equiv14^{53}[(14)^{50}-1]$$

Now $\displaystyle14^1\equiv1\pmod{13},14^1\equiv-1\pmod3\implies14^2\equiv(-1)^2\equiv1$

$\displaystyle\implies14^{\text{lcm}(1,2)}\equiv1\pmod{3\cdot13}$

or directly by observation, $\displaystyle14^2=196\equiv1\pmod{195}\equiv1\pmod{39}$

$\implies14^{2n}\equiv1$ for non-negative integer $n$

---

Generalization :

We need $\displaystyle a\equiv1\pmod3,\equiv-1\pmod {13}$ and $\displaystyle b\equiv-1\pmod3,\equiv1\pmod {13}$ where $a,b$ are odd integers

So, $\displaystyle a=3A+1=13B-1$ for some integers $A,B$

$\iff\displaystyle3A=13B-2=13B-(2\cdot13-3\cdot8)\iff3(A-8)=13(B-2)$

$\displaystyle\implies\frac{3(A-8)}{13}=B-2$ which is an integer

$\displaystyle\implies13|3(A-8)\iff13|(A-8)$ as $(13,3)=1$

$\displaystyle\implies A=8+13C\implies a=3(8+13C)+1=39(C+1)-14\equiv-14\pmod{39}$

Similarly, we can derive $\displaystyle b\equiv14\pmod{39}$

But one condition, $a,b$ must be odd integers

We can further generalize this any two relative prime odd integers