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

Options

A. 3
B. 15
C. 16
D. 19

Explanation

To find the remainder when \(3^{19}\) is divided by 19, we can use Fermat's Little Theorem. This 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, \(a = 3\) and \(p = 19\). Since 3 is not divisible by 19, we can apply the theorem.

### Step-by-Step Solution:

1. **Identify the values**: We have \(a = 3\) and \(p = 19\).

2. **Apply Fermat's Little Theorem**: According to the theorem, we can say:
\[ 3^{19-1} \equiv 1 \mod 19 \]
This simplifies to:
\[ 3^{18} \equiv 1 \mod 19 \]

3. **Express \(3^{19}\)**: We can express \(3^{19}\) as:
\[ 3^{19} = 3^{18} \cdot 3 \]

4. **Use the result from Fermat's theorem**: From step 2, we know that \(3^{18} \equiv 1 \mod 19\). Therefore:
\[ 3^{19} \equiv 1 \cdot 3 \mod 19 \]

5. **Final computation**: This simplifies to:
\[ 3^{19} \equiv 3 \mod 19 \]

Thus, the remainder when \(3^{19}\) is divided by 19 is **3**.