Divisibility involving exponents

Question

How can one prove that $13$ divides $3^x - 16^x$ ?

I have tried to apply some exponent laws but those only work when multiplying with the same base, not subtraction.

Any helpful hints/advice would be appreciated :)

Answer 1

In general, if $n$ is a positive integer, then $a-b$ divides $a^n-b^n$. For $$a^n-b^n=(a-b)\left(a^{n-1}+a^{n-2}b+\cdots +b^{n-1}\right).$$

Answer 2

HINT : Suppose that $x$ is a non-negative integer.

You can prove it by induction.

$$3^{x+1}-16^{x+1}=3(3^x-16^x)-13\cdot 16^x$$

Answer 3

If you know anything about modular arithmetic, $16\equiv3\pmod{13}$, so $16^x\equiv3^x\pmod{13}$. Otherwise, you could rewrite $16^x$ as $(13+3)^x$ and use the binomial theorem. The only term that won't be a multiple of $13$ will be $3^x$.