To calculate $5^{123} \mod 33$ using Euler's theorem, follow these steps:

Step 1: Euler's Theorem Overview

Euler's theorem 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 of $n$.

Step 2: Check if 5 and 33 are Coprime

Since $\gcd(5, 33) = 1$ (they have no common factors), Euler's theorem can be applied.

Step 3: Compute $\phi(33)$

Euler’s totient function $\phi(n)$ is calculated as: $\phi(33) = \phi(3 \times 11) = \phi(3) \times \phi(11)$ where:

• $\phi(3) = 3 - 1 = 2$
• $\phi(11) = 11 - 1 = 10$

So, $\phi(33) = 2 \times 10 = 20$.

Step 4: Reduce Exponent Using Euler's Theorem

From Euler's theorem, we know: $5^{20} \equiv 1 \mod 33$ Now reduce the exponent $123 \mod 20$: $123 \div 20 = 6 \text{ remainder } 3$ Thus: $5^{123} \equiv 5^3 \mod 33$

Step 5: Calculate $5^3 \mod 33$

Now calculate $5^3$: $5^3 = 5 \times 5 \times 5 = 125$ Now reduce $125 \mod 33$: $125 \div 33 = 3 \text{ remainder } 26$ Thus: $125 \equiv 26 \mod 33$

Final Answer:

$5^{123} \equiv 26 \mod 33$

Would you like more details or have any questions?

Here are some related questions:

1. How do you compute $\phi(n)$ for larger numbers?
2. How does Euler's theorem relate to Fermat's Little Theorem?
3. Can Euler’s theorem be used if $a$ and $n$ are not coprime?
4. What are other applications of Euler’s theorem in cryptography?
5. How do you calculate powers efficiently using modular arithmetic?

Tip: Modular exponentiation can be computed efficiently using the method of "exponentiation by squaring," especially for large exponents.