What is the remainder when `4^(1000)`, is divisible by 7?

Options

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

Answer

To find the remainder when \( 4^{1000} \) is divided by 7, we can use Fermat's Little Theorem, which states that if \( p \) is a prime number and \( a \) is an integer not divisible by \( p \), then:

\[ a^{p-1} \equiv 1 \ (\text{mod} \ p) \]

In this case, \( a = 4 \) and \( p = 7 \). Since 4 is not divisible by 7, we can apply the theorem.

### Step 1: Apply Fermat's Little Theorem
According to Fermat's Little Theorem:

\[ 4^{7-1} \equiv 1 \ (\text{mod} \ 7) \]

This simplifies to:

\[ 4^6 \equiv 1 \ (\text{mod} \ 7) \]

### Step 2: Reduce the exponent modulo 6
Now we need to reduce the exponent 1000 modulo 6 (since \( 4^6 \equiv 1 \)):

\[ 1000 \mod 6 \]

Calculating \( 1000 \div 6 \):

\[ 1000 = 6 \times 166 + 4 \]

Thus,

\[ 1000 \mod 6 = 4 \]

### Step 3: Substitute back into the equation
Now we can substitute back into our original expression:

\[ 4^{1000} \equiv 4^4 \ (\text{mod} \ 7) \]

### Step 4: Calculate \( 4^4 \)
Now we calculate \( 4^4 \):

\[ 4^4 = 256 \]

### Step 5: Find the remainder of 256 when divided by 7
Now we need to find \( 256 \mod 7 \):

Calculating \( 256 \div 7 \):

\[ 256 = 7 \times 36 + 4 \]

Thus,

\[ 256 \mod 7 = 4 \]

### Conclusion
The remainder when \( 4^{1000} \) is divided by 7 is:

\[ \boxed{4} \]