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