Find the remainder when `(5)^(250)` is divided by 250.

Options

A. 1
B. 125
C. 150
D. 100

Answer

To find the remainder when \(5^{250}\) is divided by 250, we can use the Chinese Remainder Theorem (CRT) since 250 can be factored into prime factors.

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

### Step 2: Find \(5^{250} \mod 2\)
Now, we calculate \(5^{250} \mod 2\):
\[ 5 \equiv 1 \mod 2 \]
Thus,
\[ 5^{250} \equiv 1^{250} \equiv 1 \mod 2 \]

### Step 3: Find \(5^{250} \mod 125\)
Next, we calculate \(5^{250} \mod 125\):
Since \(125 = 5^3\), any power of 5 that is greater than or equal to 3 will be congruent to 0 modulo 125:
\[ 5^{250} \equiv 0 \mod 125 \]

### Step 4: Set up the system of congruences
Now we have the following system of congruences:
\[ x \equiv 1 \mod 2 \]
\[ x \equiv 0 \mod 125 \]

### Step 5: Solve the system of congruences
Let \(x = 125k\) for some integer \(k\) (from the second congruence). Substituting into the first congruence:
\[ 125k \equiv 1 \mod 2 \]
Since \(125 \equiv 1 \mod 2\), we have:
\[ 1k \equiv 1 \mod 2 \implies k \equiv 1 \mod 2 \]
This means \(k\) is odd. The smallest odd integer is 1. Thus, let \(k = 1\):
\[ x = 125 \times 1 = 125 \]

### Step 6: Conclusion
Therefore, the remainder when \(5^{250}\) is divided by 250 is:
\[ \boxed{125} \]