When `5^507` is divided by 500, the remain- der will be?

Options

A. 125
B. 1
C. 121
D. 4

Answer

To find the remainder when \( 5^{507} \) is divided by 500, we can simplify the problem step by step.

### Step 1: Factor 500
First, we can factor 500:
\[ 500 = 5^3 \times 2^2 = 125 \times 4 \]

### Step 2: Rewrite the expression
We want to find \( 5^{507} \mod 500 \). We can express \( 5^{507} \) in terms of its factors:
\[ 5^{507} = 5^{504} \times 5^3 \]

### Step 3: Simplify using the factor of 500
Since \( 5^{504} \) contains \( 5^3 \), we can rewrite it as:
\[ 5^{507} = 5^{504} \times 125 \]
Now, we can express \( 5^{504} \) in terms of \( 500 \):
\[ 5^{507} = 125 \times 5^{504} \]

### Step 4: Calculate \( 5^{504} \mod 4 \)
Next, we need to find \( 5^{504} \mod 4 \). Since \( 5 \equiv 1 \mod 4 \):
\[ 5^{504} \equiv 1^{504} \equiv 1 \mod 4 \]

### Step 5: Calculate \( 5^{507} \mod 125 \)
Now, we calculate \( 5^{507} \mod 125 \):
\[ 5^{507} \equiv 0 \mod 125 \]
because \( 507 > 3 \).

### Step 6: Use the Chinese Remainder Theorem
Now we have two congruences:
1. \( 5^{507} \equiv 0 \mod 125 \)
2. \( 5^{507} \equiv 1 \mod 4 \)

Let \( x \) be the remainder we are looking for. We can set up the system:
\[ x \equiv 0 \mod 125 \]
\[ x \equiv 1 \mod 4 \]

### Step 7: Solve the system of congruences
From the first congruence, we can express \( x \) as:
\[ x = 125k \quad \text{for some integer } k \]

Substituting into the second congruence:
\[ 125k \equiv 1 \mod 4 \]
Calculating \( 125 \mod 4 \):
\[ 125 \equiv 1 \mod 4 \]
Thus:
\[ 1k \equiv 1 \mod 4 \implies k \equiv 1 \mod 4 \]
So, we can write:
\[ k = 4m + 1 \quad \text{for some integer } m \]
Substituting back:
\[ x = 125(4m + 1) = 500m + 125 \]

### Step 8: Find the remainder
Thus, the remainder when \( x \) is divided by 500 is:
\[ x \equiv 125 \mod 500 \]

### Final Answer
The remainder when \( 5^{507} \) is divided by 500 is \( \boxed{125} \).