Find the remainder when `7^(99)` is divisible by 2400.

Options

A. 1
B. 343
C. 49
D. 7

Answer

To find the remainder when \( 7^{99} \) is divided by \( 2400 \), we can use modular arithmetic and properties of powers.

### Step-by-Step Solution:

1. **Factor 2400**:
\[ 2400 = 2^4 \times 3 \times 5^2 \]
This will help us apply the Chinese Remainder Theorem later.

2. **Find \( 7^{99} \mod 16 \)** (since \( 2^4 = 16 \)):
- Calculate \( 7^2 \mod 16 \):
\[ 7^2 = 49 \quad \Rightarrow \quad 49 \mod 16 = 1 \]
- Thus, \( 7^{99} = (7^2)^{49} \times 7^1 \equiv 1^{49} \times 7 \mod 16 \):
\[ 7^{99} \mod 16 \equiv 7 \]

3. **Find \( 7^{99} \mod 3 \)**:
- Calculate \( 7 \mod 3 \):
\[ 7 \equiv 1 \mod 3 \]
- Therefore, \( 7^{99} \mod 3 \equiv 1^{99} \equiv 1 \mod 3 \).

4. **Find \( 7^{99} \mod 25 \)** (since \( 5^2 = 25 \)):
- Use Euler's theorem. First, calculate \( \phi(25) \):
\[ \phi(25) = 25 \left(1 - \frac{1}{5}\right) = 20 \]
- Since \( 99 \mod 20 = 19 \), we need to compute \( 7^{19} \mod 25 \).
- Calculate powers of 7 modulo 25:
\[ 7^1 \equiv 7 \mod 25 \]
\[ 7^2 \equiv 49 \mod 25 \equiv 24 \]
\[ 7^3 \equiv 7 \times 24 = 168 \mod 25 \equiv 18 \]
\[ 7^4 \equiv 7 \times 18 = 126 \mod 25 \equiv 1 \]
- Since \( 7^4 \equiv 1 \mod 25 \), we can reduce \( 7^{19} \):
\[ 7^{19} = (7^4)^4 \times 7^3 \equiv 1^4 \times 18 \equiv 18 \mod 25 \]

5. **Set up the system of congruences**:
- We have:
\[ x \equiv 7 \mod 16 \]
\[ x \equiv 1 \mod 3 \]
\[ x \equiv 18 \mod 25 \]

6. **Solve the system using the method of successive substitutions**:
- Start with \( x \equiv 18 \mod 25 \):
\[ x = 25k + 18 \]
- Substitute into \( x \equiv 7 \mod 16 \):
\[ 25k + 18 \equiv 7 \mod 16 \quad \Rightarrow \quad 9k + 2 \equiv 7 \mod 16 \quad \Rightarrow \quad 9k \equiv 5 \mod 16 \]
- The multiplicative inverse of 9 modulo 16 is 9 (since \( 9 \times 9 \equiv 1 \mod 16 \)):
\[ k \equiv 9 \times 5 \mod 16 \equiv 45 \mod 16 \equiv 13 \mod 16 \]
- Thus, \( k = 16m + 13 \) for some integer \( m \):
\[ x = 25(16m + 13) + 18 = 400m + 325 + 18 = 400m + 343 \]
- Therefore:
\[ x \equiv 343 \mod 400 \]

7. **Now solve \( x \equiv 1 \mod 3 \)**:
- Substitute \( x = 400m + 343 \):
\[ 400m + 343 \equiv 1 \mod 3 \quad \Rightarrow \quad 1m + 1 \equiv 1 \mod 3 \]
- This is satisfied for any integer \( m \).

8. **Final result**:
- The remainder when \( 7^{99} \) is divided by \( 2400 \) is:
\[ \boxed{343} \]