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

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.

Thank you.

• Hint: $3^{2k+1}-2^{2k+1} = 3^{2k} + 2(3^{2k} - 2^{2k})$. – dxiv Oct 9 '16 at 23:13

$$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$$

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.

• is there a way to state the last part without referring to the concept of groups? – ALannister Oct 10 '16 at 0:49
• and $2$ has order $5$ in $\mathbb{Z}_{5}$ – ALannister Oct 10 '16 at 0:57
• @JessyCat $2$ has order $4$ in the group of units under multiplication since $2^4 = 16 \equiv 1 \pmod{5}$ and $4$ is the smallest such positive integer. You can certainly rephrase the last part without groups, but you will basically have to reprove a special case of Lagrange's Theorem to conclude that $4$ divides $2n$. – André 3000 Oct 10 '16 at 1:00
• at this point, we have not even defined what a group is. I'm also not sure I understand why the group of units under multiplication is relevant... – ALannister Oct 10 '16 at 1:08
• If you don't know Lagrange's Theorem, maybe you won't understand all of my answer right now (although I did include a link to the Wikipedia page describing the result). But maybe you will find the answer more useful once you've seen some more group theory. In any case, I usually find proofs by induction unenlightening, and I think my proof is more elegant. But you are of course free to disagree! :) Anyway, if you would like me to clarify a part of my answer, I'm happy to elaborate. – André 3000 Oct 10 '16 at 1:28

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?

• am I allowed to allude to the $(\implies)$ direction to say that $3(3^{2k}-2^{2k})$ is divisible by $5$? – ALannister Oct 10 '16 at 0:32
• @JessyCat Of course yes if it's been proven, which has been. – Stefan4024 Oct 10 '16 at 1:32