When `7^40` is divided by 400, the remainder obtained is ?

Options

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

Answer

To find the remainder when \( 7^{40} \) is divided by 400, we can use the properties of modular arithmetic and the Chinese Remainder Theorem.

### Step 1: Factor 400
First, we factor 400 into its prime factors:
\[ 400 = 16 \times 25 = 2^4 \times 5^2 \]

### Step 2: Calculate \( 7^{40} \mod 16 \)
Now, we will calculate \( 7^{40} \mod 16 \):
\[ 7^1 \equiv 7 \mod 16 \]
\[ 7^2 \equiv 49 \equiv 1 \mod 16 \]
Since \( 7^2 \equiv 1 \mod 16 \), we can use this to simplify \( 7^{40} \):
\[ 7^{40} = (7^2)^{20} \equiv 1^{20} \equiv 1 \mod 16 \]

### Step 3: Calculate \( 7^{40} \mod 25 \)
Next, we calculate \( 7^{40} \mod 25 \):
Using Euler's theorem, we first find \( \phi(25) \):
\[ \phi(25) = 25 \left(1 - \frac{1}{5}\right) = 25 \times \frac{4}{5} = 20 \]
According to Euler's theorem:
\[ 7^{20} \equiv 1 \mod 25 \]
Thus,
\[ 7^{40} = (7^{20})^2 \equiv 1^2 \equiv 1 \mod 25 \]

### Step 4: Combine results using the Chinese Remainder Theorem
Now we have:
\[ 7^{40} \equiv 1 \mod 16 \]
\[ 7^{40} \equiv 1 \mod 25 \]
Since both congruences yield the same result, we can conclude:
\[ 7^{40} \equiv 1 \mod 400 \]

### Final Result
Thus, the remainder when \( 7^{40} \) is divided by 400 is:
\[ \boxed{1} \]