Find the remainder when `(3)^(2140)` is divided by 17.

Options

A. 13
B. 4
C. 10
D. 7

Answer

To find the remainder when \(3^{2140}\) 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\).

### Step 1: Identify the values
Here, \(a = 3\) and \(p = 17\). Since 3 is not divisible by 17, we can apply Fermat's Little Theorem.

### Step 2: Apply Fermat's Little Theorem
According to Fermat's theorem:
\[ 3^{16} \equiv 1 \mod 17 \]

### Step 3: Reduce the exponent modulo \(p-1\)
Next, we need to reduce the exponent 2140 modulo 16 (since \(p-1 = 16\)):
\[ 2140 \mod 16 \]
To calculate \(2140 \div 16\):
\[ 2140 \div 16 = 133.75 \quad \text{(take the integer part, which is 133)} \]
Now, calculate \(133 \times 16\):
\[ 133 \times 16 = 2128 \]
Now, subtract this from 2140 to find the remainder:
\[ 2140 - 2128 = 12 \]
So,
\[ 2140 \mod 16 = 12 \]

### Step 4: Substitute back into the expression
Now we can rewrite the original expression using this result:
\[ 3^{2140} \equiv 3^{12} \mod 17 \]

### Step 5: Calculate \(3^{12} \mod 17\)
To compute \(3^{12} \mod 17\), we can first find \(3^4\):
\[ 3^2 = 9 \]
\[ 3^4 = 9^2 = 81 \]
Now, find \(81 \mod 17\):
\[ 81 \div 17 = 4.764 \quad \text{(take the integer part, which is 4)} \]
Calculating \(4 \times 17\):
\[ 4 \times 17 = 68 \]
Now, subtract this from 81:
\[ 81 - 68 = 13 \]
So,
\[ 3^4 \equiv 13 \mod 17 \]

### Step 6: Calculate \(3^{12}\)
Now, we need \(3^{12}\):
\[ 3^{12} = (3^4)^3 \equiv 13^3 \mod 17 \]
Calculating \(13^3\):
\[ 13^2 = 169 \]
Now, find \(169 \mod 17\):
\[ 169 \div 17 = 9.941 \quad \text{(take the integer part, which is 9)} \]
Calculating \(9 \times 17\):
\[ 9 \times 17 = 153 \]
Now, subtract this from 169:
\[ 169 - 153 = 16 \]
So,
\[ 13^2 \equiv 16 \mod 17 \]
Now, calculate \(13^3\):
\[ 13^3 = 13 \times 13^2 \equiv 13 \times 16 \mod 17 \]
Calculating \(13 \times 16\):
\[ 13 \times 16 = 208 \]
Now, find \(208 \mod 17\):
\[ 208 \div 17 = 12.235 \quad \text{(take the integer part, which is 12)} \]
Calculating \(12 \times 17\):
\[ 12 \times 17 = 204 \]
Now, subtract this from 208:
\[ 208 - 204 = 4 \]
So,
\[ 13^3 \equiv 4 \mod 17 \]

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