2
$\begingroup$

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.

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

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ is there a way to state the last part without referring to the concept of groups? $\endgroup$ – ALannister Oct 10 '16 at 0:49
  • $\begingroup$ and $2$ has order $5$ in $\mathbb{Z}_{5}$ $\endgroup$ – ALannister Oct 10 '16 at 0:57
  • $\begingroup$ @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$. $\endgroup$ – André 3000 Oct 10 '16 at 1:00
  • $\begingroup$ 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... $\endgroup$ – ALannister Oct 10 '16 at 1:08
  • 1
    $\begingroup$ 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. $\endgroup$ – André 3000 Oct 10 '16 at 1:28
3
$\begingroup$

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.