I need to prove $7|13^n-6^n$ for $n$ being any positive integer.

Using induction I have the following:

Base case:

$n=0$: $13^0-6^0 = 1-1 = 0, 7|0$

so, generally you could say:

$7|13^k-6^k , n = k \ge 1$

so, prove the $(k+1)$ situation:


$13 \cdot 13^k-6 \cdot 6^k$

And then I'm stuck....where do I go from here?

  • $\begingroup$ For the base case, you want use $n = 1$, since we are concerned with all positive integers. $\endgroup$
    – amWhy
    Mar 8, 2015 at 20:36

7 Answers 7



$$ 13\times 13^k -6 \times 6^k = 7\times 13^k +6(13^k-6^k) $$


There's always this:

$$\begin{split} x^2-y^2 &= (x-y)(x+y)\\ x^3-y^3 &= (x-y)(x^2+xy+y^2)\\ x^4-y^4 &= (x-y)(x^3 +x^2y+xy^2+y^3)\\ &\vdots\\ x^n-y^n &= (x-y)\left(\sum_{i=1}^{n}x^{n-i}y^{i-1}\right) \mid n\in \mathbb{N} \end{split}$$

In the above, let $x=13$ and $y=6$. Then you can visually see that no matter what $n\in \mathbb{N}$ is, $ 7\mid 13^n-6^n$. And more generally, $x-y \mid x^n-y^n$.


Hint: $$13\equiv 6\bmod 7$$ rise both sides to the power of $n$.


Write $13=6+7$ to expand $13*13^k-6*6^k$.


First, show that this is true for $n=1$:


Second, assume that this is true for $n$:


Third, prove that this is true for $n+1$:









Please note that the assumption is used only in the part marked red.

  • $\begingroup$ Okay! I knew I could replace one value but wasn't really sure what to do with it. Thank you! $\endgroup$
    – Rachel
    Mar 8, 2015 at 20:37
  • $\begingroup$ @Rachel: You're welcome :) $\endgroup$ Mar 8, 2015 at 20:39

Write $13^n-6^n=(14-1)^n-(7-1)^n$. Expand using the binomial theorem; the $1$'s cancel and you're left only with multiples of $7$.


We write $n=1$ and get $13 - 6 =7$( a multiple of $7$) Moving to the induction hypothesis, We assume that $n=k$, therefore $13^k - 6^k = 7b$($b$ shows that $7$ is a multiple of $13^k -6^k$ by $b$ times) Taking $k=1$ from above ($n=k=1$) then we get :

$13^1 - 6^1=13 - 6=7$.

Take one side of the equation and use the equivalent to its multiple in each in the form of $13-7$ or $7+6$ : $\pm$ the divisor($7$).

Either $13^k(7+6) - 6^k(6)$ or $13^k(13) - 6^k(13-7)$.

Taking $ 13^k(13) - 6^k(13 -7)$ gives $13^k(13) - 6^k(13) + 6^k(7)$.

Change the power $k$ on $6^k(13)$ to $13$ ;$13^k(6)$ $13^k(13) - 13^k(6) + 6^k(7)$

Factor out $13^k$ on the LHS $13^k(13-6) + 6^k(7)$ giving

$13^k(7) + 6^k(7)$. This can be compressed to:

$7(13^k + 6^k)$ Therefore now $b= 13^k + 6^k$ making it $7|(13^n - 6^n)$ valid for all positive integers values of $n$.

  • $\begingroup$ @jkuat. Hope this helped so much $\endgroup$ Jan 18, 2018 at 22:55
  • $\begingroup$ The answer is correct, but it adds nothing new to this two years old question. $\endgroup$
    – user99914
    Jan 18, 2018 at 23:00
  • $\begingroup$ Please make the "change the power" line clearer. $\endgroup$ Jan 18, 2018 at 23:15

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.