When `11^77` is divided by 7, the remainder obtained is ?

Options

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

Answer

To find the remainder when \( 11^{77} \) is divided by 7, we can use modular arithmetic. Here’s a step-by-step solution:

### Step 1: Simplify \( 11 \mod 7 \)
First, we need to reduce \( 11 \) modulo \( 7 \):
\[ 11 \div 7 = 1 \quad \text{(quotient)} \]
\[ 11 - (1 \times 7) = 11 - 7 = 4 \]
So, \( 11 \equiv 4 \mod 7 \).

### Step 2: Rewrite the expression
Now we can rewrite \( 11^{77} \) in terms of \( 4 \):
\[ 11^{77} \equiv 4^{77} \mod 7 \]

### Step 3: Use Fermat's Little Theorem
According to Fermat's Little Theorem, if \( p \) is a prime and \( a \) is an integer not divisible by \( p \), then:
\[ a^{p-1} \equiv 1 \mod p \]
Here, \( p = 7 \) and \( a = 4 \), which is not divisible by \( 7 \). Therefore:
\[ 4^{6} \equiv 1 \mod 7 \]

### Step 4: Reduce the exponent modulo 6
Now we need to reduce the exponent \( 77 \) modulo \( 6 \):
\[ 77 \div 6 = 12 \quad \text{(quotient)} \]
\[ 77 - (12 \times 6) = 77 - 72 = 5 \]
Thus, \( 77 \equiv 5 \mod 6 \).

### Step 5: Calculate \( 4^{77} \mod 7 \)
Now we can simplify \( 4^{77} \) using the reduced exponent:
\[ 4^{77} \equiv 4^{5} \mod 7 \]

### Step 6: Calculate \( 4^{5} \mod 7 \)
Now we calculate \( 4^{5} \):
\[ 4^{2} = 16 \]
\[ 16 \mod 7 = 2 \quad \text{(since } 16 - 14 = 2\text{)} \]
Next, calculate \( 4^{4} \):
\[ 4^{4} = (4^{2})^{2} = 2^{2} = 4 \]
Now calculate \( 4^{5} \):
\[ 4^{5} = 4^{4} \times 4 = 4 \times 4 = 16 \]
\[ 16 \mod 7 = 2 \]

### Conclusion
Thus, the remainder when \( 11^{77} \) is divided by \( 7 \) is:
\[ \boxed{2} \]