A solução é dada usando
congruência linear:
\(109617 \; \equiv \; 6 \; \text{mod(9)}\)
então o nosso problema se resume a achar o resto da divisão de \(6^{291}\) por \(9\) .
veja que \(6^{2} \; \equiv \; 36 \; \equiv 0 \; \text{mod(9)}\)
segue que :
\(6^{291} \; \equiv \; (6^2)^{145}*6 \; \equiv \; 0^{145}*6 \; \equiv 0 \; \text{mod(9)}\)
como percebemos o resto da divisão de \(109617^{291}\) por \(9\) é zero.