When `41^77` is divided by 17, the remainder obtained is ?

Options

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

Answer

To find the remainder when \( 41^{77} \) is divided by 17, 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, \( p = 17 \) and \( a = 41 \).

### Step 1: Reduce \( 41 \) modulo \( 17 \)
First, we need to find \( 41 \mod 17 \):

\[ 41 \div 17 = 2 \quad \text{(quotient)} \]
\[ 41 - (17 \times 2) = 41 - 34 = 7 \]

So, \( 41 \equiv 7 \mod 17 \).

### Step 2: Rewrite the expression
Now we can rewrite \( 41^{77} \) as:

\[ 41^{77} \equiv 7^{77} \mod 17 \]

### Step 3: Apply Fermat's Little Theorem
According to Fermat's Little Theorem, since \( 7 \) is not divisible by \( 17 \):

\[ 7^{16} \equiv 1 \mod 17 \]

### Step 4: Reduce the exponent modulo \( 16 \)
Next, we need to reduce \( 77 \) modulo \( 16 \):

\[ 77 \div 16 = 4 \quad \text{(quotient)} \]
\[ 77 - (16 \times 4) = 77 - 64 = 13 \]

So, \( 77 \equiv 13 \mod 16 \).

### Step 5: Calculate \( 7^{13} \mod 17 \)
Now we need to compute \( 7^{13} \mod 17 \). We can do this by calculating powers of \( 7 \):

\[ 7^1 \equiv 7 \mod 17 \]
\[ 7^2 \equiv 49 \mod 17 \equiv 15 \mod 17 \]
\[ 7^3 \equiv 7 \times 15 = 105 \mod 17 \equiv 3 \mod 17 \]
\[ 7^4 \equiv 7 \times 3 = 21 \mod 17 \equiv 4 \mod 17 \]
\[ 7^5 \equiv 7 \times 4 = 28 \mod 17 \equiv 11 \mod 17 \]
\[ 7^6 \equiv 7 \times 11 = 77 \mod 17 \equiv 13 \mod 17 \]
\[ 7^7 \equiv 7 \times 13 = 91 \mod 17 \equiv 6 \mod 17 \]
\[ 7^8 \equiv 7 \times 6 = 42 \mod 17 \equiv 8 \mod 17 \]
\[ 7^9 \equiv 7 \times 8 = 56 \mod 17 \equiv 5 \mod 17 \]
\[ 7^{10} \equiv 7 \times 5 = 35 \mod 17 \equiv 1 \mod 17 \]
\[ 7^{11} \equiv 7 \times 1 = 7 \mod 17 \]
\[ 7^{12} \equiv 7 \times 7 = 49 \mod 17 \equiv 15 \mod 17 \]
\[ 7^{13} \equiv 7 \times 15 = 105 \mod 17 \equiv 3 \mod 17 \]

### Step 6: Conclusion
Thus, the remainder when \( 41^{77} \) is divided by \( 17 \) is:

\[ \boxed{3} \]