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

Question

This is a problem in my number theory textbook. It is based on modular arithmetic but im not getting how to start off to prove this. Please give me some hints on how to solve it.

Answer 1

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$

Answer 2

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

Answer 3

${\rm mod}\ \ \ 3\!:\ n = 53^{\large j}\! + 103^{\large k}\equiv (\color{#0a0}{-1})^{\large j}\ \ +\,\ \ \color{#c00}1^{\large k} \equiv\, \color{#0a0}{-1}\color{#c00}{+1}\equiv 0,\ $ assuming $\,j\,$ is odd.

${\rm mod}\ 13\!:\ n = 53^{\large j}\! + 103^{\large k}\equiv \ \ \ \ \color{#c00}1^{\large j}\, +\,(\color{#0a0}{-1})^{\large k} \equiv\, \color{#c00}{{+}1}\color{#0a0}{-1}\equiv 0,\ $ assuming $\,k\,$ is odd.

So $\ 3,13\mid n\,\Rightarrow\, 39\mid n\ $ by $\ {\rm lcm}(3,13) = 3\cdot 13\ $ (or by CCRT) $\ $ QED

Remark $\ $ The above innate $\rm\color{#c00}{sym}\color{#0a0}{metry}$ above can be brought to the fore as in this answer, i.e.

$$\{a,b\} \equiv \{\color{#c00}{+c},\,\color{#0a0}{-c}\,\}\,\ {\rm mod}\,\ m\,\&\,n\ \Rightarrow\ {\rm lcm}(m,n)\mid a\!+\!b\qquad\qquad$$

The congruence arithmetic above employs the basic Congruence Sum and Power Rules.