What is the remainder of $6^{17}$ divided by $17^6$? What is the general method to solve such questions ?
 A: Well, let's have a go by hand. We note that $6^2=36=2(17+1)$ so that $$6^{17}=6\cdot(6^2)^8=6\cdot 2^8 \cdot(17+1)^8$$
Now we use $2^4=17-1$ to give $$6\cdot(17-1)^2\cdot(17+1)^8=6\cdot(17^2-1)^2\cdot(17+1)^6$$
Let's put $x=17$ and reduce modulo $x^6=17x^5$ as we go (I prefer to keep the powers and $x$ works better for me than $17$).
$(x+1)^6=6x^5+15x^4+20x^3+15x^2+6x+1$
$(x^2-1)^2=x^4-2x^2+1$
So that $(x^2-1)^2(x+1)^6=$ (dropping $x^6$ and higher powers, all equalities now are modulo $17^6$)
$6x^5+x^4-40x^5-30x^4-12x^3-2x^2+6x^5+15x^4+20x^3+15x^2+6x+1 =$
$-28x^5-14x^4+8x^3+13x^2+6x+1 =$
$6x^5-14x^4+8x^3+13x^2+6x+1$
We now need to multiply this by 6 to obtain
$36x^5-84x^4+48x^3+78x^2+36x+6$
and using $x=17$ this becomes
$2x^5-5x^5+x^4+3x^4-3x^3+5x^3-7x^2+2x^2+2x+6$
$=14x^5+4x^4+2x^3-5x^2+2x+6$
The value of this expression with $x=17$ is $20220503$ - see Dan Shved's comment. It doesn't look like there is any much simpler way to do it.
A: Hint
$$\frac{6^{17}}{17^6}=\left(\frac{6^3}{17}\right)^5*\left(\frac{6^2}{17}\right)=\left(\frac{216}{17}\right)^5*\left(\frac{36}{17}\right)$$
... then modular calculation.
