Compute the remainder of $3^{2021}$ mod $15$
Problem
Source:
Tags: number theory
30.12.2021 13:02
we know $3^1\equiv 3(mod15)$ $3^2 \equiv 9(mod 15)$ $3^3 \equiv 12 (mod 15)$ $3^4 \equiv 6(mod 15)$ $3^5 \equiv 3(mod 15). \rightarrow$ therefore, for every $3^{4k+1} \equiv 3(mod15)$ $3^{4k+2} \equiv 9(mod 15)$ $3^{4k+3} \equiv 12 (mod 15)$ $3^{4k} \equiv 6(mod 15)$ since $2021 \equiv 1 (mod 4) \rightarrow 3^{2021} \equiv 3^1 \equiv 3 (mod 15)$
31.12.2021 10:02
$3^{2021}\equiv 0\pmod{3}$ $3^{2021}\equiv 3\pmod{5}$ $3^{2021}\equiv 3\times 6-0\times 5\equiv 3\pmod{15}$
31.12.2021 16:05
Obviously $3^{2021}\equiv 0\pmod 3$. Now we will find $3^{2021}\pmod 5$. Note by Euler's Totient Theorem, $3^4\equiv 1\pmod 5$, so $3^{2020}\equiv 1\pmod 5$. Thus, $3^{2021}\equiv 3\pmod 5$. We can test all possible values $\pmod {15}$ and find that $3^{2021}\equiv \boxed{3}\pmod {15}$.
12.09.2023 13:54
Note, that $3^{2021} \equiv 0\pmod{3},$ and $3^4 \equiv 1\pmod{5},$ so $3^{2021} \equiv (3^4)^{505}\cdot 3 \equiv 1^{505} \cdot 3\equiv \boxed{3}\pmod{5}.$ I boxed $3,$ because if it is 3 mod 5 and 0 mod 3 it is 3 mod 15
13.09.2023 02:32
2021=1 ( mod 4) 3^1(mod 15)=3(mod 15)
13.09.2023 14:29
Well find the repeating cycle mod $15,$ then we get $3 \mod 5.$