## Task $4 / 62$

What remainder does the number $2^{n}$ leave when divided by 3?
The number $2^{n}$ is not divisible by 3, as it only contains the prime factor 2. Therefore, $2^{n}$ cannot leave a remainder of 0 when divided by 3. The only possible remainders are 1 and 2.

$$
\begin{gathered}
n=0: 2^{n}=3=2^{0}: 3=1: 3=0 \text { remainder } 1 \\
n=1: 2^{n}=3=2^{1}: 3=2: 3=0 \text { remainder } 2 \\
n=2: 2^{n}=3=2^{2}: 3=4: 3=1 \text { remainder } 1 \\
n=3: 2^{n}=3=2^{3}: 3=8: 3=2 \text { remainder } 2 \\
n=4: 2^{n}=3=2^{4}: 3=16: 3=5 \text { remainder } 1
\end{gathered}
$$

The conjecture arises that $2^{n}$ leaves a remainder of 1 when divided by 3 if $n$ is even, and a remainder of 2 if $n$ is odd. This is at least true for $n=0$ to $n=4$.

To provide a general proof, we proceed as follows:

If $2^{n}$ leaves a remainder of 1 when divided by 3, then we can write $2^{n}=3k+1$. Then for $2^{n+1}$: $2^{n+1}=2 \cdot 2^{n}=2(3k+1)=6k+2$.

We see that $2^{n+1}$ leaves a remainder of 2 when divided by 3. On the other hand, if $2^{n}$ leaves a remainder of 2 when divided by 3, then we can write $2^{n}=3k+2$. Then for $2^{n+1}$: $2^{n+1}=2 \cdot 2^{n}=2(3k+2)=6k+4=6k+3+1$.

We see that in this case $2^{n+1}$ leaves a remainder of 1 when divided by 3. Thus, it is proven that the remainders 1 and 2 alternate regularly when the number $2^{n}$ is divided by 3 as $n$ runs through the sequence $0; 1; 2; 3; 4; \ldots$.

Therefore, for every $n$: The number $2^{n}$ leaves a remainder of 1 when divided by 3 if $n$ is even, and a remainder of 2 if $n$ is odd.

Using theorems from number theory or group theory, this claim can be proven more elegantly.