Question

Tìm số dư trong phép chia 3^{2020} chia cho 13

Answer 1

Your question translates to computing $3^{2020} \pmod {13}$.

Recall Euler's theorem: if $\gcd(a,n)=1$ (that is, $a$ and $n$ are relatively prime), then $a^{\varphi(n)}\equiv1\pmod n$, where $\varphi(n)$ denotes Euler's totient function, which counts the number of positive integers relatively prime to $n$.

Since 13 is prime, we have $\phi(13)=12$. Then by Euler's theorem,

$3^{12} \equiv 1 \pmod{13}$

Now, observe that 2020 = 168×12 + 4, so that

$3^{2020} \equiv 3^{168\times12+4} \equiv \left(3^{12}\right)^{168} \times 3^4 \equiv 1^{168} \times 3^4 \equiv 3^4 \pmod{13}$

and since 3⁴ = 81 = 6×13 + 3, we end up with

$3^{2020} \equiv 81 \equiv 3 \pmod{13}$

so the remainder upon dividing 3²⁰²⁰ by 13 is 3.