Remainder of $3^n$ modulo $15$ Let $n \in \mathbb{N}_{>0}$. Then we have $$\begin{align*} &3 \equiv 3 \bmod 15\\&3^2 \equiv 9 \bmod 15\\&3^3 \equiv 12 \bmod 15\\&3^4 \equiv 6 \bmod 15\\&3^5 \equiv 3 \bmod 15\end{align*}$$ Hence all remainders modulo $15$ of $3^n$ should be $3,9,12$ and $6$. Why is this the case? Also, How could I calculate $$3^{1291}\equiv ? \bmod 15$$
 A: As to why: there isn't a much better reason than "because you've just demonstrated that's what happened". But here's a little: $3^n$ is always a multiple of $3$. Since $15$ is also a multiple of $3$, the remainder of $3^n$ when divided by $15$ must always be a multiple of $3$ - so $3^n$ must be $0,3,6,9$, or $12$ mod $15$. But $15$ is also a multiple of $5$, and $3^n$ is not, so $3^n$ cannot be a multiple of $15$; so $3^n$ can't be $0$ mod $15$.
As for $3^{1291}$: you've established more than just that $3^n$ is $3,9,12$, or $6$ mod $15$; you've established that it takes those values in order. So, in other words, you know that $3^1$, $3^5$, $3^9$, $3^{13}$, and so on all come to $3$ mod $15$. In general, you know that every fourth power of three after the first - so $3^{4n+1}$ for any $n$ - is $3$ modulo $15$. That will get you close to $3^{1291}$.
A: The only choices are $3, 6, 9, 12$ because $15$ is divisible by $3$, so what you're really doing is calculating $3^{n-1} \bmod 5$ and multiplying by $3$.  That can't be $0$ (powers of $3$ can't be multiples of $5$ by unique factorization), so the only choices are $1, 2, 3, 4$ multiplied by $3$.
As for your second problem, notice that the pattern repeats: $3, 9, 12, 6, 3, 9, 12, 6, 3, 9, 12, 6, \ldots$  So take $u = 1291$ modulo ____ (fill in the blank) and then $3^u \equiv 3^{1291} \bmod 15$.

Oh, in case the reasoning isn't clear, we use the fact that
$$
ab \bmod 3 = (a \bmod 3)(b \bmod 3) \bmod 3
$$
In other words, we can take the modulo before we multiply, making things a lot less computationally intensive.
A: Note that: $3^{4n} \equiv 6 \bmod 15$
$3^{1291} \equiv 3^{4\cdot 322 +3} \equiv 3^{3} \equiv 12 \bmod 15$
A: Notice that :
$$3^{4k+r}\equiv 3^r\bmod 15$$
Therefore;
$$3^{1288+3}=3^{4\times{322}+3}\equiv 3^3\bmod 15\equiv 12\bmod 15$$
A: The reason here that values of $3^k$ are so restricted is because $15$ is a multiple of $3$. Taking values $\bmod 15$ will therefore not change the status of being a multiple of $3$. Also $3^k$ is never a multiple of $5$, so you won't get the value of $0\bmod 15$. This only leaves the four values you found.
As you can see, the sequence $3^k \bmod 15$ runs in a cycle of four, so you can discard a multiple of $4$ from the exponent to get back to a low value. Here you can discard $4\times322=1288$ to find that $3^{1291}\equiv 3^3 \bmod 15$ and look up your result.
