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? 
 A: 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)$.
A: 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.

A: 
$\displaystyle{\large%
a = {36^{36} + 41^{41} \over 77}.\quad
\mbox{Is}\quad a\quad \mbox{an integer ?}\\[3mm]}$

$\large\mbox{Hint: Try these tests}$


*

*$$
7\ |\ 7777\ \mbox{because}\
777 - 14=763\,,\quad 76 - 6 = 70\,,\quad 7 - 0 = 7\quad\mbox{and}\quad 7\ |\ 7
$$



*$$
11\ |\ 8096\ \mbox{because}\
809 - 6=803\,,\quad 80 - 3 = 77\,,\quad 7 - 7 = 0\quad\mbox{and}\quad 11\ |\ 0
$$



WA yields

$a = 17284125074533757891391113841182593918679814596127517531883081101$
