# Why is every answer of $5^k - 2^k$ divisible by 3?

We have the formula $$5^k - 2^k$$

I have noticed that every answer you get from this formula is divisible by 3. At least, I think so. Why is this? Does it have to do with $5-2=3$?

-
Do you know modular arithmetic (congruences)? –  Math Gems Apr 25 '13 at 23:00
it is so sad that questions which are really easy and understandable are getting so many upvotes, but questions that really requires understanding are staying in a shadow. This is one of the examples.... –  Salvador Dali Apr 26 '13 at 1:31
@SalvadorDali that happens all over on SE; some simpler questions get lots of upvotes from people who understand the subject matter well enough to say "hey that's neat"; but who ignore questions that they don't understand well enough to vote on. Once a question gets voted onto the hot question dropdown it's going to be seen by a huge number of people most of whom don't know math beyond basic calculus and whose voting will swamp that of the mathematicians who frequent this site. –  Dan Neely Apr 26 '13 at 12:51
the thing is that a question which can be answered by any properly educated 8-class schoolchild and gives the possibility of getting huge number of points makes it reluctant for people to answer harder questions that requires some knowledge and can not be answered in 3 minutes. As @DanNeely correctly pointed, this is everywhere on SE and in my opinion this might hurt the site in the future –  Salvador Dali Apr 26 '13 at 14:04
@SalvadorDali I think you're worrying too much; the same happens everywhere and the huge numbers of upvotes for questions asking "something every programmer should know" certainly hasn't kept stackoverflow itself from becoming one of the top programming help sites. If you're really concerned though, I suggest taking the issue from here to Meta.SE since its a network wide phenomena. –  Dan Neely Apr 26 '13 at 15:23

Yes, it does!

It's because in general you have the factorization:

$$x^k-y^k = (x-y)(x^{k-1}+x^{k-2}y+\dots+y^{k-1})$$

Substituting in $x=5$ and $y=2$ should show you why that works.

-
Very elegant and understandable! –  iDivide Apr 25 '13 at 23:29

You say congruences are not familiar. Suppose you don't know the formulas in the other answers, but you do know the polynomial Division Algorithm. Dividing $\rm\:x^k\!-\!2^k$ by $\rm\:x\!-\!2\:$ yields

$\rm\qquad x^k-2^k =\ q(x)\, (x-2) + r\quad$ for an integer $\rm\:r\:$ and integer coefficient quotient $\rm\:q(x).$

Evaluating at $\rm\ x = 2\$ shows $\rm\ r = 0.\$ Evaluating at $\rm\: x = 5\:$ shows $\rm\,3\,$ divides $\rm\,5^k - 2^k$

Remark $\$ This is a special case of the Factor Theorem, as are the other answers.

-
This is very beautiful, and is in some ways the 'real' reason why this works. It also generalizes better. –  Donkey_2009 Apr 26 '13 at 10:16

Recall that $$a^k - b^k = (a-b)(a^{k-1} +a^{k-2} b + \cdots + a b^{k-2} + b^{k-1}) \tag{\star}$$ One way to see this is, to notice that $$(a^{k-1} +a^{k-2} b + \cdots + a b^{k-2} + b^{k-1})$$ is the sum of first $k$ terms of a geometric progression with first term $a^{k-1}$ and common ratio $\dfrac{b}a$. We hence get that $$a^{k-1} +a^{k-2} b + \cdots + a b^{k-2} + b^{k-1} = a^{k-1} \left(\dfrac{1-(b/a)^k}{1-b/a}\right) = \dfrac{a^k-b^k}{a-b}$$ Rearranging above gives you $(\star)$.

-
I would say this is a better answer since it gives reason for the factorization –  Enzo Apr 26 '13 at 0:58
If you view this as a polynomial in $a$ e.g., then the factorization is trivial because the left hand side is clearly zero when $a=b$; that is $b$ is a root, and a polynomial can be factored in terms of it's roots $(a-b_1)(a-b_2)...$ e.t.c... –  Graham Hesketh Apr 26 '13 at 13:50
Furthermore, if $k$ were even then $a+b$ is also a root and thus all answers would be divisible by $5+2=7$, and because $7$ and $3$ are co-prime, all answers would also be divisible by $7\times 3=21$. –  Graham Hesketh Apr 26 '13 at 14:03

Even a little knowledge of modular arithmetic makes this obvious:

$$5 \equiv 2 \pmod 3$$

and thus

$$5^k \equiv 2^k \pmod 3,$$

which is equivalent to

$$5^k - 2^k \equiv 0 \pmod 3.$$

-
The OP is not familiar with modular arithmetic (per comments under the question). That would have been my first choice too had the OP answered otherwise. –  Math Gems Apr 26 '13 at 4:27
I saw the comments, but really, the amount of modular arithmetic needed for this can be picked up just by looking at the Wikipedia article I linked to (even if it is rather horribly written). –  Ilmari Karonen Apr 26 '13 at 12:04

Let's use induction to prove that:

$$5^k - 2^k$$

is divisible by 3

Let's check the proposition for k = 0 is divisible by 3 $$5^0 - 2^0 = 1 - 1 = 0$$ which is divisible by 3 Let's assume that for k = n the proposition

$$5^n - 2^n$$ is divisible by 3 and let's prove that $$5^{(n+1)} - 2^{(n+1)}$$ is also true, so $$5^{(n+1)} - 2^{(n+1)} = 5{(5^n)} - 2{(2^n)}$$ $$= (3 + 2)(5^n) - 2(2^n)$$ $$= 3(5^n) + 2(5^n) - 2(2^n)$$ $$= 3(5^n) + 2(5^n - 2^n)$$ So in the above expression $$3(5^n)$$ is divisible by 3 $$2(5^n - 2^n)$$ is divisible by 3 as per our assumption, so the finale expression $$3(5^n) + 2(5^n - 2^n)$$ is also divisible by 3 So we can conclude that $$5^{(n+1)} - 2^{(n+1)}$$ is divisible by 3 Meaning $$5^n - 2^n$$ is divisible by 3 for $$n \in \mathbb{N}$$

-

Write $5^k= (2+3)^k= {k\choose 0}2^k+ {k \choose 1}2^{k-1}3 +\cdots +{k\choose 1}3^{k-1}2+ {k\choose k}3^k$

Therefore $$5^k-2^k= {k \choose 1}2^{k-1}3 +\cdots +{k\choose 1}3^{k-1}2+ {k\choose k}3^k= 3\left ({k \choose 1}2^{k-1} +\cdots +{k\choose 1}3^{k-2}2+ {k\choose k}3^{k-1}\right)$$

-

We know that $x^k −y^k$ is always divisible by $x-y$ due to formula $x^k −y^k =(x−y)(x^{k−1} +x^{k−2} y+⋯+y^{ k−1} )$

-
Welcome to MSE! It really helps readability to format questions using MahtJax (see FAQ). Regards –  Amzoti Apr 27 '13 at 12:22