32
$\begingroup$

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

$\endgroup$
21
  • 7
    $\begingroup$ Do you know modular arithmetic (congruences)? $\endgroup$
    – Math Gems
    Commented Apr 25, 2013 at 23:00
  • 28
    $\begingroup$ 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.... $\endgroup$ Commented Apr 26, 2013 at 1:31
  • 10
    $\begingroup$ @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. $\endgroup$ Commented Apr 26, 2013 at 12:51
  • 8
    $\begingroup$ 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 $\endgroup$ Commented Apr 26, 2013 at 14:04
  • 9
    $\begingroup$ @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. $\endgroup$ Commented Apr 26, 2013 at 15:23

7 Answers 7

93
$\begingroup$

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.

$\endgroup$
1
  • 7
    $\begingroup$ Very elegant and understandable! $\endgroup$
    – iDivide
    Commented Apr 25, 2013 at 23:29
33
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ This is very beautiful, and is in some ways the 'real' reason why this works. It also generalizes better. $\endgroup$ Commented Apr 26, 2013 at 10:16
26
$\begingroup$

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

$\endgroup$
3
  • 4
    $\begingroup$ I would say this is a better answer since it gives reason for the factorization $\endgroup$
    – Enzo
    Commented Apr 26, 2013 at 0:58
  • $\begingroup$ 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... $\endgroup$ Commented Apr 26, 2013 at 13:50
  • $\begingroup$ 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$. $\endgroup$ Commented Apr 26, 2013 at 14:03
23
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Math Gems
    Commented Apr 26, 2013 at 4:27
  • $\begingroup$ 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). $\endgroup$ Commented Apr 26, 2013 at 12:04
19
$\begingroup$

Let's use induction to prove that:

\begin{equation} 5^k - 2^k \end{equation}

is divisible by 3

Let's check the proposition for k = 0 is divisible by 3 \begin{equation} 5^0 - 2^0 = 1 - 1 = 0 \end{equation} which is divisible by 3 Let's assume that for k = n the proposition

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

$\endgroup$
13
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Welcome to MSE! It really helps readability to format questions using MahtJax (see FAQ). Regards $\endgroup$
    – Amzoti
    Commented Apr 27, 2013 at 12:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .