<s>[INST] 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
 [/INST] 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$
</s>