Check whether $36^{36}+41^{41}$ a multiple of $77$

Hint: $36^{36}+41^{41} = 36^{36}+(77-36)^{41} = 77m+36^{36}-36^{41} = 77m-36^{36}(6^5+1)(6^5-1)$ and $6^5+1=(6+1)(6^3\cdot5+6\cdot5+1)$.

Let $n=36^{36}+41^{41}$. Three elementary steps:

• What happens modulo $7$: Note that $36\equiv 1\pmod{7}$ and that $41\equiv -1\pmod{7}$ hence $n \equiv 1^{36}+(-1)^{41}=1+(-1)=0\pmod{7}$.
• What happens modulo $11$: Note that $36\equiv 3\pmod{11}$ and that $41\equiv -3\pmod{11}$ hence $n\equiv 3^{36}+(-3)^{41}=3^{36}-3^{41}=3^{36}\cdot(1-3^5)\pmod{11}$.
  Since $3^5=9^2\cdot 3\equiv (-2)^2\cdot 3=12\equiv1\pmod{11}$, $n\equiv 0\pmod{11}$.
• And the Grand Finale: Since $\gcd(7,11)=1$, $n\equiv 0\pmod{7}$ and $n\equiv 0\pmod{11}$ together imply (actually, they are equivalent to the fact) that $n\equiv 0\pmod{7\cdot11}$, QED.