The remainder when 2^340 is divided by 341 is:

The correct answer is Option (2) → 1

Use Fermat's little theorem: If $p$ is prime and "p" doesn't divide "a", then $a^{p-1} \equiv 1 \ (\text{mod } p)$

Check if 341 is prime: $341 = 11*31$, not prime

Use Chinese Remainder Theorem modulo 11 and 31

Modulo 11: $2^{10} \equiv 1 \ (\text{mod } 11)$

$340 \mod 10 = 0 \Rightarrow 2^{340} = (2^{10})^{34} \equiv 1^{34} \equiv 1 \ (\text{mod } 11)$

Modulo 31: $2^{30} \equiv 1 \ (\text{mod } 31)$

$340 \mod 30 = 10 \Rightarrow 2^{340} \equiv 2^{10} \ (\text{mod } 31)$

$2^{10} = 1024$, $1024 \mod 31 = 1024 - 31*33 = 1024-1023=1 \Rightarrow 2^{340} \equiv 1 \ (\text{mod } 31)$

Since $2^{340} \equiv 1 \ (\text{mod } 11)$ and $2^{340} \equiv 1 \ (\text{mod } 31)$

By Chinese Remainder Theorem, $2^{340} \equiv 1 \ (\text{mod } 341)$