Describe all natural numbers $n$ for which $3^{n}-2^{n}$ is divisible by $5$.

Question

I need to describe all natural numbers $n$ for which $3^{n}-2^{n}$ is divisible by $5$.

After testing out some $n \in \mathbb{N}$, I came to the conclusion that $3^{n} - 2^{n}$ is divisible by $5$ iff $n$ is even - i.e., if $n$ is of the form $2k$ for $k \in \mathbb{N}$.

Here is my attempt so far:

$(\implies)$:

To show that if $n$ is even, then $3^{n}-2^{n}$ is divisible by $5$, we prove that $\forall k \in N$, $3^{2k}-2^{2k} \equiv \,0 \mod 5$ by induction on $k$:

• Basis Step: For $k = 1$, $3^{2(1)}-2^{2(1)}=3^{2}-2^{2}=9-4=5 \equiv\, 0 \mod 5 $.

• Suppose true for $\mathbf{k=m}$: $3^{2m}-2^{2m}\equiv \, 0 \mod 5 \, \implies \, 3^{2m}-2^{2m}=5l$, $l \in \mathbb{Z}$.

• Show true for $\mathbf{k = m+1}$: Consider $3^{2(m+1)}-2^{2(m+1)}\\ = 3^{2m+2}-2^{2m+2}\\ = 3^{2m}\cdot 3^{2}- 2^{2m}\cdot 2^{2}\\ = 9\cdot 3^{2m}-4 \cdot 2^{2m} \\= 5 \cdot 3^{2m} + 4\cdot 3^{2m} - 4 \cdot 2^{2m} \\ = 5(3^{2m}) + 4(3^{2m}-2^{2m}) \\ = 5(3^{2m})+4(5l)\, \text{(by the induction hypothesis)} \\ = 5(3^{2m} + 4l) \, \text{which is divisible by}\, 5.$

So, by induction, then the statement $3^{2k}-2^{2k} \equiv \, 0 \mod 5$ holds $\forall k \geq 1 \, \implies \, $ the statement $3^{n}-2^{n} \equiv \, 0 \mod 5$ holds $\forall n = 2k$, $k \geq 1$.

$(\Longleftarrow)$:

To show that $3^{n}-2^{n}$ divisible by $5$ $\implies$ $n$ even, we will show that $n$ odd $\implies$ $3^{n}-2^{n}$ is not divisible by $5$. Now, suppose the proposition is false. I.e., assume $\exists n \in \mathbb{N}$ for which $n$ is odd, but $3^{n}-2^{n}$ is divisible by $5$.

Since $n$ is odd, it is of the form $2k+1$, $k \in \mathbb{N}$.

So, we have that $3^{2k+1}-2^{2k+1} \equiv \, 0 \mod 5 \, \implies \, 3^{2k+1} - 2^{2k+1} = 5l$, $l \in \mathbb{N}$.

So, $\displaystyle \frac{3^{2k+1}}{5} - \frac{2^{2k+1}}{5} = l$.

At this point, I got stuck. I think my $(\implies)$ direction is fine, but I definitely need help on my $(\Longleftarrow)$ direction.

Could somebody please help me complete this proof?

Thank you.

Answer 1

$$3^{2k+1}-2^{2k+1}= 3(9^k)-2(4^k) \equiv 3(-1)^k-2(-1)^k=(-1)^k \mod 5$$

$$3^{2k}-2^{2k}= (9^k)-(4^k) \equiv (-1)^k-(-1)^k=0 \mod 5$$

Answer 2

HINT: $$3^{2k+1} - 2^{2k+1} = 3\cdot 3^{2k} - 2 \cdot 2^{2k} = 3(3^{2k} - 2^{2k}) + 2^{2k}$$

Now can you see why the first summand is divisible by 5 and the second isn't?

Answer 3

I think this is a little easier to see using modular arithmetic. Note that $5$ divides $3^n - 2^n$ means $3^n \equiv 2^n \pmod{5}$. Since $3 \cdot 2 = 6 \equiv 1 \pmod{5}$, then $3 = 2^{-1}$ in $\mathbb{Z}/5\mathbb{Z}$. Then \begin{align*} 2^n \equiv 3^n \equiv (2^{-1})^n = 2^{-n} \pmod{5} \end{align*} and multiplying through by $2^n$ yields $2^{2n} \equiv 1 \pmod{5}$. This means that the order of $2$ in the unit group $(\mathbb{Z}/5\mathbb{Z})^\times$ divides $2n$. Since $2$ has order $4$ in $(\mathbb{Z}/5\mathbb{Z})^\times$, then $4$ divides $2n$, so $2$ divides $n$, i.e., $n$ is even. All the implications above are actually two-sided (iff), so we find that $5$ divides $3^n - 2^n$ iff $n$ is even.