Question

What is the remainder when \( 13^{2013} \) is divided by 100?

Hint:

When dealing with large exponents, always reduce the exponent modulo \( \phi(n) \) if \( a \) and \( n \) are coprime. This allows you to compute the powers efficiently using smaller exponents.

Answer 1

Step 1: Using Modular Arithmetic.
We are asked to find the remainder when \( 13^{2013} \) is divided by 100. This can be done using modular arithmetic. A useful tool here is **Euler’s Theorem**, which states that if \( a \) and \( n \) are coprime (i.e., \( \gcd(a, n) = 1 \)), then: \[ a^{\phi(n)} \equiv 1 \mod n \] where \( \phi(n) \) is Euler’s totient function, which gives the number of integers less than \( n \) that are coprime with \( n \).
Step 2: Applying Euler’s Theorem.
First, we need to calculate \( \phi(100) \). Since \( 100 = 2^2 \times 5^2 \), we use the formula for Euler's totient function: \[ \phi(100) = 100 \left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{5} \right) = 100 \times \frac{1}{2} \times \frac{4}{5} = 40 \] Thus, Euler's theorem tells us that: \[ 13^{40} \equiv 1 \mod 100 \] This means that the powers of 13 repeat every 40 terms modulo 100. Therefore, to find \( 13^{2013} \mod 100 \), we can reduce the exponent \( 2013 \) modulo 40.
Step 3: Reducing the Exponent Modulo 40.
To reduce \( 2013 \mod 40 \), we divide 2013 by 40: \[ 2013 \div 40 = 50 \text{ remainder } 13 \] So, we have: \[ 13^{2013} \equiv 13^{13} \mod 100 \]
Step 4: Calculating \( 13^{13} \mod 100 \).
Now, we need to compute \( 13^{13} \mod 100 \). We can break this down by successive squaring and reducing modulo 100 at each step: \[ 13^2 = 169 \equiv 69 \mod 100 \] \[ 13^4 = (13^2)^2 = 69^2 = 4761 \equiv 61 \mod 100 \] \[ 13^8 = (13^4)^2 = 61^2 = 3721 \equiv 21 \mod 100 \] Now, calculate \( 13^{13} \): \[ 13^{13} = 13^8 \times 13^4 \times 13 = 21 \times 61 \times 13 \] First, calculate \( 21 \times 61 = 1281 \equiv 81 \mod 100 \), and then: \[ 81 \times 13 = 1053 \equiv 53 \mod 100 \]
Step 5: Conclusion.
Thus, \( 13^{2013} \equiv 13^{13} \equiv 53 \mod 100 \). Therefore, the remainder when \( 13^{2013} \) is divided by 100 is \( \boxed{53} \).