When `7^99` is divided by 2400, the remain- der obtained is ?

Options

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

Answer

To find the remainder when \( 7^{99} \) is divided by 2400, we can use modular arithmetic. Let's break it down step by step.

### Step 1: Factor 2400
First, we need to factor 2400 into its prime factors:
\[ 2400 = 24 \times 100 = (2^3 \times 3) \times (10^2) = (2^3 \times 3) \times (2 \times 5)^2 = 2^5 \times 3^1 \times 5^2 \]

### Step 2: Use the Chinese Remainder Theorem
To find \( 7^{99} \mod 2400 \), we can find \( 7^{99} \mod 32 \), \( 7^{99} \mod 3 \), and \( 7^{99} \mod 25 \) separately, and then combine the results using the Chinese Remainder Theorem.

### Step 3: Calculate \( 7^{99} \mod 32 \)
Using Euler's theorem, we first find \( \phi(32) \):
\[ \phi(32) = 32 \left(1 - \frac{1}{2}\right) = 16 \]
Since \( 7 \) and \( 32 \) are coprime, we have:
\[ 7^{16} \equiv 1 \mod 32 \]
Now, we calculate \( 99 \mod 16 \):
\[ 99 \div 16 = 6 \quad \text{(remainder 3)} \]
Thus, \( 99 \mod 16 = 3 \), and we compute:
\[ 7^{99} \equiv 7^3 \mod 32 \]
Calculating \( 7^3 \):
\[ 7^3 = 343 \]
Now find \( 343 \mod 32 \):
\[ 343 \div 32 = 10 \quad \text{(remainder 23)} \]
So, \( 7^{99} \equiv 23 \mod 32 \).

### Step 4: Calculate \( 7^{99} \mod 3 \)
Since \( 7 \equiv 1 \mod 3 \):
\[ 7^{99} \equiv 1^{99} \equiv 1 \mod 3 \]

### Step 5: Calculate \( 7^{99} \mod 25 \)
Using Euler's theorem again, we find \( \phi(25) \):
\[ \phi(25) = 25 \left(1 - \frac{1}{5}\right) = 20 \]
Since \( 7 \) and \( 25 \) are coprime, we have:
\[ 7^{20} \equiv 1 \mod 25 \]
Now, we calculate \( 99 \mod 20 \):
\[ 99 \div 20 = 4 \quad \text{(remainder 19)} \]
Thus, \( 99 \mod 20 = 19 \), and we compute:
\[ 7^{99} \equiv 7^{19} \mod 25 \]
Calculating \( 7^{19} \mod 25 \) can be done using successive squaring:
\[ 7^1 \equiv 7 \mod 25 \]
\[ 7^2 \equiv 49 \equiv 24 \mod 25 \]
\[ 7^4 \equiv 24^2 = 576 \equiv 1 \mod 25 \]
Thus, \( 7^8 \equiv 1 \) and \( 7^{16} \equiv 1 \). Therefore:
\[ 7^{19} = 7^{16} \cdot 7^3 \equiv 1 \cdot 343 \equiv 18 \mod 25 \]

### Step 6: Solve the system of congruences
Now we have the following system of congruences:
\[ x \equiv 23 \mod 32 \]
\[ x \equiv 1 \mod 3 \]
\[ x \equiv 18 \mod 25 \]

Using the method of successive substitutions or the Chinese Remainder Theorem, we can solve these congruences step by step.

1. Start with \( x \equiv 18 \mod 25 \).
2. Substitute into \( x \equiv 23 \mod 32 \):
- Let \( x = 25k + 18 \).
- Substitute into \( 25k + 18 \equiv 23 \mod 32 \):
- This simplifies to \( 25k \equiv 5 \mod 32 \).
- The inverse of \( 25 \mod 32 \) is \( 29 \) (since \( 25 \cdot 29 \equiv 1 \mod 32 \)).
- Thus, \( k \equiv 29 \cdot 5 \mod 32 \equiv 145 \mod 32 \equiv 17 \mod 32 \).
- Therefore, \( k = 32m + 17 \).
3. Substitute back to find \( x \):
- \( x = 25(32m + 17) + 18 = 800m + 425 + 18 = 800m + 443 \).
- Thus, \( x \equiv 443 \mod 800 \).

4. Now solve \( 443 \equiv 1 \mod 3 \):
- \( 443 \mod 3 \equiv 1 \), which is already satisfied.

### Final Step: Conclusion
Thus, the remainder when \( 7^{99} \) is divided by 2400 is:
\[ \boxed{443} \]