The remainder when `2^(39)` is divided by 39 is :

Options

A. 0
B. 2
C. 8
D. 1

Answer

To find the remainder when \( 2^{39} \) is divided by 39, we can use modular arithmetic and properties of exponents. Here’s a step-by-step solution:

### Step 1: Break down the exponent
We can express \( 39 \) as \( 36 + 3 \), which allows us to write:
\[ 2^{39} = 2^{36} \cdot 2^3 \]

### Step 2: Calculate \( 2^{36} \mod 39 \)
To simplify \( 2^{36} \mod 39 \), we can use Euler's theorem. First, we need to find \( \phi(39) \), where \( \phi \) is the Euler's totient function.

### Step 3: Calculate \( \phi(39) \)
The prime factorization of \( 39 \) is \( 3 \times 13 \). Thus,
\[ \phi(39) = \phi(3) \cdot \phi(13) = (3-1)(13-1) = 2 \cdot 12 = 24 \]

### Step 4: Apply Euler's theorem
According to Euler's theorem, since \( 2 \) and \( 39 \) are coprime,
\[ 2^{\phi(39)} \equiv 1 \mod 39 \]
This means:
\[ 2^{24} \equiv 1 \mod 39 \]

### Step 5: Reduce the exponent modulo \( \phi(39) \)
Now, we can reduce \( 36 \) modulo \( 24 \):
\[ 36 \mod 24 = 12 \]
Thus,
\[ 2^{36} \equiv 2^{12} \mod 39 \]

### Step 6: Calculate \( 2^{12} \mod 39 \)
Now we need to calculate \( 2^{12} \):
\[ 2^1 = 2 \]
\[ 2^2 = 4 \]
\[ 2^3 = 8 \]
\[ 2^4 = 16 \]
\[ 2^5 = 32 \]
\[ 2^6 = 64 \equiv 25 \mod 39 \]
\[ 2^7 = 2 \cdot 25 = 50 \equiv 11 \mod 39 \]
\[ 2^8 = 2 \cdot 11 = 22 \]
\[ 2^9 = 2 \cdot 22 = 44 \equiv 5 \mod 39 \]
\[ 2^{10} = 2 \cdot 5 = 10 \]
\[ 2^{11} = 2 \cdot 10 = 20 \]
\[ 2^{12} = 2 \cdot 20 = 40 \equiv 1 \mod 39 \]

### Step 7: Combine results
Now we have:
\[ 2^{39} = 2^{36} \cdot 2^3 \equiv 1 \cdot 8 \mod 39 \]

### Final Step: Conclusion
Thus, the remainder when \( 2^{39} \) is divided by \( 39 \) is:
\[ \boxed{8} \]