Computing large modulus by hand I am having trouble computing $12^{15}$ mod $2016$ due to the large size of the modulus. I need to do this and list the steps out by hand
 A: Remember $a \equiv b \mod n$ means $\frac a{\gcd(a,n)} \equiv \frac b{\gcd(a,n)} \mod \frac n{\gcd(a,n)}$.
Proof:  $a \equiv b \mod n \implies a + nk = b \implies \gcd(a,n)(\frac a{\gcd(a,n)} + \frac n{\gcd(a,n)}k \implies \frac a{\gcd(a,n)} \equiv \frac b{\gcd(a,n)} \mod \frac n{\gcd(a,n)}$
$2016 = 7*2^53^2$ so $\gcd(2016, 12^{15}) = 2^53^2$
So $12^{15} \equiv x \mod 2016 \implies 2^{25}3^{13} \equiv x/288 \mod 7$
$2^6 \equiv 3^6 \equiv 1 \mod 7$ by Fermat's Little Theorem so
$2^{25}3^{13}\equiv 2*3 \equiv 6 \equiv -1 \mod 7$.
So $x = -288$.
So $12^{15} \equiv -288 \mod 2016$
A: Applying $\, ca \bmod cn\, =\,  c(a\bmod n)\,\, $  the mod Distributive Law, we get
$\,\ \ \ \begin{align} 12^{\large 15}\!\bmod {288\cdot 7}\, &=\, 288\,( 12^{\large 15}/288\,\bmod 7)\ \ {\rm by}\ \ 288 = 2^{\large 5}\cdot 3^{\large 2}\mid 12^{\large 15}\\
&=\, 288\,(\color{#c00}{(-2)^{\large 15}}/1\, \bmod 7)\\
&=\, 288\,(\ \color{#c00}6\, \bmod 7)\ \ {\rm by}\ \ 2^{\large 3}\equiv 1\,\Rightarrow\,\color{#c00}{(-2)^{\large 15}\!\equiv -1\equiv 6}\!\!\!\!\pmod{\! 7}\\
&=\, 1728
\end{align}$
