Check whether $36^{36}+41^{41}$ a multiple of $77$ Let $$a=\frac{36^{36}+41^{41}}{77}.$$
Is $a$ an integer?
I know that:


*

*The last digit ofr $41^{41}$ is $1$.

*The last digit of $36^{36}=6^{72}$ is $6$.
How can I use this information to answer my question, or do I need another thing to help me? 

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.

