171k views
15 votes
Tìm số dư trong phép chia 3^{2020} chia cho 13

User DaveIdito
by
6.9k points

1 Answer

8 votes

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.

User Jake Zeitz
by
7.6k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.