If `29^(41)+37^(41)` is divided by 33 then the remainder is:

Options

A. 3
B. 0
C. 2
D. 1

Answer

To solve the problem of finding the remainder when \( 29^{41} + 37^{41} \) is divided by 33, we can use properties of modular arithmetic.

### Step-by-Step Solution:

1. **Identify the Expression**: We need to find \( 29^{41} + 37^{41} \mod 33 \).

2. **Use the Property of Exponents**: We can use the property that states if \( x \equiv a \mod m \) and \( y \equiv b \mod m \), then \( x^n + y^n \equiv a^n + b^n \mod m \).

3. **Calculate \( 29 \mod 33 \) and \( 37 \mod 33 \)**:
- \( 29 \mod 33 = 29 \)
- \( 37 \mod 33 = 4 \) (since \( 37 - 33 = 4 \))

4. **Rewrite the Expression**: Now we can rewrite the expression as:
\[ 29^{41} + 37^{41} \equiv 29^{41} + 4^{41} \mod 33 \]

5. **Use Fermat's Little Theorem**: Since 33 is not prime, we can apply the Chinese Remainder Theorem. We will find the result modulo 3 and modulo 11 (since \( 33 = 3 \times 11 \)).

- **Modulo 3**:
- \( 29 \mod 3 = 2 \)
- \( 4 \mod 3 = 1 \)
- Therefore, \( 29^{41} + 37^{41} \equiv 2^{41} + 1^{41} \mod 3 \)
- \( 2^{41} \mod 3 \equiv 2 \) (since \( 2 \equiv -1 \mod 3 \) and \( (-1)^{41} = -1 \equiv 2 \mod 3 \))
- Thus, \( 2^{41} + 1^{41} \equiv 2 + 1 \equiv 0 \mod 3 \)

- **Modulo 11**:
- \( 29 \mod 11 = 7 \)
- \( 4 \mod 11 = 4 \)
- Therefore, \( 29^{41} + 37^{41} \equiv 7^{41} + 4^{41} \mod 11 \)
- By Fermat's Little Theorem, \( a^{p-1} \equiv 1 \mod p \) for \( p = 11 \):
- \( 7^{10} \equiv 1 \mod 11 \) and \( 4^{10} \equiv 1 \mod 11 \)
- Thus, \( 7^{41} \equiv 7^{1} \equiv 7 \mod 11 \) and \( 4^{41} \equiv 4^{1} \equiv 4 \mod 11 \)
- Therefore, \( 7 + 4 \equiv 11 \equiv 0 \mod 11 \)

6. **Combine Results Using the Chinese Remainder Theorem**:
- We have:
- \( 29^{41} + 37^{41} \equiv 0 \mod 3 \)
- \( 29^{41} + 37^{41} \equiv 0 \mod 11 \)
- Since both results are 0, we conclude:
\[ 29^{41} + 37^{41} \equiv 0 \mod 33 \]

7. **Final Answer**: The remainder when \( 29^{41} + 37^{41} \) is divided by 33 is **0**.