True or False? Is it a Multiple?

$2\equiv -1 \pmod{3}$

$\Rightarrow 2^{k}\equiv -1^{k} \pmod{3} \text{ so for odd values of k, } 2^{k}\equiv -1 \pmod{3}$

$\Rightarrow \text{ since } 2n-1 \text{ is always odd, } 2^{2n-1} \equiv -1 \pmod{3}$ $\forall n \in \mathbb N$

$\Rightarrow 3|2^{2n-1}+1$ $\forall n \in \mathbb N$

Let's try an induction approach here!

CASE I ( $n=1$ ): $2^{2(1) - 1} + 1 = 2 + 1 = 3 \Rightarrow$ TRUE.

CASE II ( $n = k$ ): $2^{2k-1} + 1 = 3\alpha (\alpha \in \mathbb{N}) \Rightarrow$ assume to be TRUE.

CASE III ( $n = k+1$ ): By multiplying both sides of CASE II by $2^2$ yields:

$2^2 \cdot (2^{2k-1} + 1) = 2^2 \cdot 3\alpha$ ;

or $2^{2k+1} + 4 = 4 \cdot 3\alpha$ ;

or $2^{2(k+1) -1} + 1 + 3 = 4 \cdot 3\alpha;$

or $2^{2(k+1) -1} + 1 = 3 \cdot (4\alpha -1) \Rightarrow$ TRUE.

Let us consider the following:

$\begin{aligned} 2^{2n-1}+ 1 & \equiv 2^{\color{#3D99F6}(2n-1)\ \bmod\ \phi (3)}+ 1 \text{ (mod 3)} & \small \color{#3D99F6} \text{Since }\gcd(2,3) = 1 \text{, Euler's theorem applies.} \\ & \equiv 2^{\color{#3D99F6}(2n-1)\ \bmod\ 2}+ 1 \text{ (mod 3)} & \small \color{#3D99F6} \text{Euler's totient function }\phi (3) = 3-1 = 2 \text{ since 3 is a prime.} \\ & \equiv 2^{\color{#3D99F6}1}+ 1 \equiv 3 \equiv \boxed 0 \text{ (mod 3)} \end{aligned}$

True , $2^{2n-1}+1$ is always a multiple of 3 for all natural number $n$ .

---

References:

• Euler's theorem
• Euler's totient function