When `3^55` is divided by 82, the remainder obtained is ?

Options

A. 27
B. 55
C. 65
D. 17

Answer

To find the remainder when \( 3^{55} \) is divided by 82, we can use properties of modular arithmetic and the concept of powers.

### Step-by-Step Solution:

1. **Identify the Base and Modulus**: We need to find \( 3^{55} \mod 82 \).

2. **Use Fermat's Little Theorem**: Since 82 is not a prime number, we can factor it into \( 82 = 2 \times 41 \). We can apply Fermat's Little Theorem separately for each prime factor.

3. **Calculate \( 3^{55} \mod 2 \)**:
- Since \( 3 \equiv 1 \mod 2 \), we have:
\[ 3^{55} \mod 2 \equiv 1^{55} \mod 2 \equiv 1 \]

4. **Calculate \( 3^{55} \mod 41 \)**:
- Since 41 is a prime, we can apply Fermat's theorem:
\[ 3^{40} \equiv 1 \mod 41 \]
- Now, we need to reduce \( 55 \mod 40 \):
\[ 55 \mod 40 = 15 \]
- Therefore:
\[ 3^{55} \mod 41 \equiv 3^{15} \mod 41 \]

5. **Calculate \( 3^{15} \mod 41 \)**:
- We can calculate \( 3^{15} \) using successive squaring:
\[ 3^1 = 3 \]
\[ 3^2 = 9 \]
\[ 3^4 = 9^2 = 81 \equiv 40 \mod 41 \]
\[ 3^8 = 40^2 = 1600 \equiv 39 \mod 41 \]
- Now combine \( 3^8 \), \( 3^4 \), and \( 3^2 \):
\[ 3^{15} = 3^8 \cdot 3^4 \cdot 3^2 \cdot 3^1 \equiv 39 \cdot 40 \cdot 9 \cdot 3 \mod 41 \]
- Calculate \( 39 \cdot 40 \mod 41 \):
\[ 39 \cdot 40 = 1560 \equiv 1 \mod 41 \]
- Now multiply by \( 9 \):
\[ 1 \cdot 9 \equiv 9 \mod 41 \]
- Finally multiply by \( 3 \):
\[ 9 \cdot 3 = 27 \mod 41 \]

6. **Combine Results Using the Chinese Remainder Theorem**:
- We have:
\[ 3^{55} \equiv 1 \mod 2 \]
\[ 3^{55} \equiv 27 \mod 41 \]
- We need a number \( x \) such that:
\[ x \equiv 1 \mod 2 \]
\[ x \equiv 27 \mod 41 \]
- The solution to these congruences can be found. Since \( 27 \) is odd, it satisfies \( x \equiv 1 \mod 2 \).

7. **Final Result**: Therefore, the remainder when \( 3^{55} \) is divided by 82 is:
\[ \boxed{27} \]