# Prove divisibility: $6\mid 13^n+7^n-2$

We have the following proposition: $$P(n): 13^n+7^n-2\vdots 6$$.

• Prove $P(n)$ in two ways. I know that one of them is mathematical induction. I don't know many things about the other one, I know it's something from modular arithmetic.
• If we had $p_n = 13^n+7^n-2$ with $n\in\Bbb N^*$, how should we calculate the rest of $p_n:6$?

use the following facts $13\equiv 1 \mod 6$ and $7\equiv 1 \mod 6$ yes you can write $13=2\cdot 6+1$ this means the remainder is $1$ and the same for $7$, $7=6+1$ see here http://en.wikipedia.org/wiki/Modulo_operation we use this in our math circle in Leipzig

• This proof is amazing Nov 14, 2014 at 19:39
• I am 9th grade, so, please, give more explanation about the signs and everything you used. I found this exercise on the internet and I am very curious about clever ways to solve it. Nov 14, 2014 at 19:41
• What should I search on Google to find more about this $13\equiv1\mod6$? Nov 14, 2014 at 19:46
• @Victor en.wikipedia.org/wiki/Modular_arithmetic This basically says that $13$ and $1$ have the same remainder when divided by six, because $13 = 2*6+1$ and $1 = 0*6+1$. This means any power of $13$ will also have a remainder of $1$ mod $6$. So the problem reduces to $1^n+1^n-2$, which is $0$, thus the expression won't have any remainder mod $6$. Nov 15, 2014 at 9:39

Non-induction approach: write $13=6\times 2+1$ and $7=6+1$ then use the binomial theorem.

Edit: Look up the Statement of the Theorem part here. Then, apply it to your case, which gives $$13^n=(1+12)^n=1+12\times A,\quad 7^n=(1+6)^n=1+6B$$ for some integers $A$ and $B$. It follows that $13^n+7^n-2=12A+6B$, which of course is divisible by $6$.

• I am 9th grade, so, please, give more explanation about the binomial theorem Nov 14, 2014 at 19:40
• No need to know the binomial theorem Nov 14, 2014 at 19:41
• @fvel It's a standard result that is useful to know and easy to prove. Why stifle knowledge while you can easily gain it? Nov 14, 2014 at 19:44
• The binomial theorem: $\left(a+b\right)^n = \sum_{i=0}^n\left(\binom{n}{k}a^kb^{n-k}\right) = \sum_{i=0}^n\left(\frac{n!}{k!(n-k)!}a^kb^{n-k}\right)$ Nov 14, 2014 at 19:47
• @KimJongUn Dear President of Best Korea, while I agree knowledge is power, I don't see a reason to make things more complicated than they need be. Nov 14, 2014 at 19:50