Finding the remainder of a big power

Question

Find the remainder when $3^{29}$ is divided by $12$.

Since $12=3•2^2$, this can be simplified to $3^{28}/4$. And the units digit of powers of 3 follows the pattern of $3,9,7,1$, so we know that $3^{28}$'s units digit is going to be $1$. However, that doesn't help much as $3^{28}$ divided by 4 can have a remainder of 1 or 3. How can I solve this without a calculator (I am not allowed to use one)? I feel like I could use a modulo, but since I'm not that familiar with it, I'm not sure.

Answer 1

we have $$3^5\equiv 3 \mod 12$$ thus by squaring $$3^{10}\equiv 9\mod 12$$ again by squaring $$3^{20}\equiv 81\equiv 9\mod 12$$ and since $$3^9\equiv 3 \mod 12$$ we get $$3^{29}\equiv 27\equiv 3 \mod 12$$

Answer 2

Since $12=3\times 4$ consider first $$3^{29}\equiv 0 \bmod 3$$ and $$3^{29}\equiv (-1)^{29}\equiv -1 \equiv 3\bmod 4$$

The Chinese Remainder Theorem guarantees a single common solution to these congriuences modulo $12$, and this is clearly $3$, though can be computed.

---

We find numbers $X$ and $Y$ with $X\equiv 1\bmod 3; 0\bmod 4$ and $Y\equiv 0\bmod 3; 1 \bmod 4$.

We have $X=3a+1=4b$ so we look for $4b-3a=1$. Also $Y=3c=4d+1$ so $3c-4d=1$. These are possible to solve by Bezout - we have in fact $4-3=1$ so $a=-c=1; b=-d=1$ will do. $X=4, Y=-3\equiv 9\bmod 12$.

If we then have $n\equiv r\bmod 3; s\bmod 4$ then $n\equiv Xr+Ys\equiv 4a+9b\bmod 12$ will work

Answer 3

Note $\ 3^{\large 1+2n}\!\bmod\, 12\, =\, 3(3^{\large 2n}\!\bmod 4)\, =\, 3((-1)^{\large 2n}\!\bmod 4)\, =\, 3$
using $\phantom{I^{I^I}}\, ca\bmod cn\, =\, c\ (\,a\,\bmod\, n)\, =\,$ mod Distributive Law.

Answer 4

Alternatively: $$3^3\equiv 3 (mod \ 12)$$ $$(3^3)^9\equiv (3^3)^3\equiv 3 (mod \ 12)$$ $$(3^3)^9\cdot 3^2\equiv 3^3\equiv 3 (mod \ 12).$$

Answer 5

$3^1\equiv3\mod12$, $3^2\equiv9\mod12$, and $3^3\equiv27\mod12\equiv3\mod12$.

If we try $3^4$, we already know that it will be $9\mod12$ because we've already tried multiplying $3\mod12$ by $3$ again, and building on top of that, we already know that $3^5\equiv3\mod12$. We can see that this pattern of alternating between $3$ and $9\mod12$ will continue forever.

We can come up with a general pattern. $3^k$ is $3\mod12$ for odd $k$ and $9\mod12$ for even $k$. Applying this to $3^{29}$, we know that it is $3\mod12$ becaue $29$ is odd. $\square$