Find the remainder when `(3)^(555)` is divided by 7.

Options

A. 2
B. 4
C. 5
D. 6

Answer

To find the remainder when \( 3^{555} \) 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 \mod p \]

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

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

\[ 3^{7-1} \equiv 1 \mod 7 \]

This simplifies to:

\[ 3^6 \equiv 1 \mod 7 \]

### Step 2: Reduce the exponent modulo 6
Now, we need to reduce the exponent 555 modulo 6 because \( 3^6 \equiv 1 \).

\[ 555 \mod 6 \]

Calculating \( 555 \div 6 \):

\[ 555 = 6 \times 92 + 3 \]

So, \( 555 \mod 6 = 3 \).

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

\[ 3^{555} \equiv 3^3 \mod 7 \]

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

\[ 3^3 = 27 \]

### Step 5: Find the remainder of 27 when divided by 7
Now we find the remainder of 27 when divided by 7:

\[ 27 \div 7 = 3 \quad \text{(which gives a quotient of 3)} \]
\[ 27 - (7 \times 3) = 27 - 21 = 6 \]

Thus, the remainder when \( 3^{555} \) is divided by 7 is:

\[ \boxed{6} \]

---