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*12+4) \equiv \left(3^(12)\right)^(168) * 3^4 \equiv 1^(168) * 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.