When `54^124` is divided by 17, the remainder obtained is ?

Options

A. 4
B. 5
C. 3
D. 15

Answer

To find the remainder when \( 54^{124} \) is divided by \( 17 \), we can follow these steps:

### Step 1: Reduce the base modulo 17
First, we need to reduce \( 54 \) modulo \( 17 \):
\[ 54 \div 17 = 3 \quad \text{(since } 17 \times 3 = 51\text{)} \]
\[ 54 - 51 = 3 \]
So, \( 54 \equiv 3 \mod 17 \).

### Step 2: Rewrite the expression
Now, we can rewrite the original expression using this result:
\[ 54^{124} \equiv 3^{124} \mod 17 \]

### Step 3: Apply Fermat's Little Theorem
Fermat's Little Theorem 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 our case, \( p = 17 \) and \( a = 3 \). Since \( 3 \) is not divisible by \( 17 \):
\[ 3^{16} \equiv 1 \mod 17 \]

### Step 4: Reduce the exponent modulo \( 16 \)
Now we need to reduce \( 124 \) modulo \( 16 \):
\[ 124 \div 16 = 7 \quad \text{(since } 16 \times 7 = 112\text{)} \]
\[ 124 - 112 = 12 \]
So, \( 124 \equiv 12 \mod 16 \).

### Step 5: Substitute back into the expression
Now we can substitute back into our expression:
\[ 3^{124} \equiv 3^{12} \mod 17 \]

### Step 6: Calculate \( 3^{12} \mod 17 \)
To find \( 3^{12} \mod 17 \), we can calculate it step by step:
1. \( 3^2 = 9 \)
2. \( 3^4 = 9^2 = 81 \equiv 13 \mod 17 \) (since \( 81 - 68 = 13 \))
3. \( 3^8 = 13^2 = 169 \equiv 16 \mod 17 \) (since \( 169 - 153 = 16 \))
4. Now calculate \( 3^{12} = 3^8 \cdot 3^4 \equiv 16 \cdot 13 \mod 17 \)

### Step 7: Calculate \( 16 \cdot 13 \mod 17 \)
Now calculate:
\[ 16 \cdot 13 = 208 \]
Now reduce \( 208 \) modulo \( 17 \):
\[ 208 \div 17 = 12 \quad \text{(since } 17 \times 12 = 204\text{)} \]
\[ 208 - 204 = 4 \]
So, \( 3^{12} \equiv 4 \mod 17 \).

### Final Result
Thus, the remainder when \( 54^{124} \) is divided by \( 17 \) is:
\[ \boxed{4} \]