Find the remainder when `2^89` is divided by 89?

Options

A. 1
B. 2
C. 87
D. 88

Answer

To find the remainder when \( 2^{89} \) is divided by 89, 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 \ (\text{mod} \ p) \]

In this case, \( p = 89 \) (which is prime) and \( a = 2 \) (which is not divisible by 89). According to Fermat's Little Theorem:

\[ 2^{88} \equiv 1 \ (\text{mod} \ 89) \]

Now, we can express \( 2^{89} \) as:

\[ 2^{89} = 2^{88} \times 2^1 \]

Using the result from Fermat's theorem, we can substitute \( 2^{88} \):

\[ 2^{89} \equiv 1 \times 2 \ (\text{mod} \ 89) \]

Thus, we have:

\[ 2^{89} \equiv 2 \ (\text{mod} \ 89) \]

Therefore, the remainder when \( 2^{89} \) is divided by 89 is:

\[ \boxed{2} \]