# Prove without induction that $2×7^n+3×5^n-5$ is divisible by $24$.

I proved this by induction. But I want to show it using modular arithmetic. I tried for sometime as follows

$$2×7^n-2+3×5^n-3\\ 2(7^n-1)+3(5^n-1)\\ 2×6a+3×4b\\ 12(a+b)$$

In this way I just proved that it is divisible by 12 but it is not enough. Am I missing something or it will solved by some other method.

• If you want to use modular arithmetic to do it, perhaps it's useful to note that $7^2 \equiv 5^2 \equiv 1 \ (\text{mod} \ 24)$. – AlephNull Mar 20 at 11:27

Yes, it can be done by another method. Note that $$7^2=2\times24+1$$ and that $$5^2=24+1$$ and that therefore$$7^n\equiv\begin{cases}7\pmod{24}&\text{ if n is odd}\\1\pmod{24}&\text{ otherwise}\end{cases}$$and$$5^n\equiv\begin{cases}5\pmod{24}&\text{ if n is odd}\\1\pmod{24}&\text{ otherwise.}\end{cases}$$So:

• if $$n$$ is odd, then $$2\times7^n+3\times5^n-5\equiv2\times7+3\times5-5=24\equiv0\pmod{24}$$;
• otherwise, $$2\times7^n+3\times5^n-5\equiv2\times1+3\times1-5\equiv0\pmod{24}$$.
• may I suggest that you use $\times$ instead of the dot? – Ertxiem Mar 20 at 11:29
• Yes, you are allowed to do that. :-) – José Carlos Santos Mar 20 at 11:30
• Thank you very much. :) – Ertxiem Mar 20 at 11:35
• This is a correct method, but to prove the results stated would still require induction, for example to conclude that $7^{2k} \equiv 1 \pmod {24}$ from $7^2 \equiv 1 \pmod{24}$. Even proving that $1^n = 1$ will require induction. – Carl Mummert Mar 20 at 12:10
• @Carl Do you know any way to formalize "proof without induction" at an elementary level? – Bill Dubuque Mar 21 at 2:49

$$2(7^n-1)+3(5^n-1)$$

$$=2((1+6)^n-1)+3((1+4)^n-1)$$

$$\equiv2(6n+\text{ terms containing }6^2)+3(4n+\text{ terms containing }4^2)$$

$$\equiv 24n\pmod{24}$$

• Very nice and simple.... +1 – Shailesh Mar 20 at 12:07

Case 1 : $$n$$ is odd

In this case $$2×7^n+3×5^n-5{=2×7^n+2×5^n+5^n-5\\=2\times\underbrace{(7^n+5^n)}_{12k}+5(5^{n-1}-1)\\=24k+5(\underbrace{25^{n-1\over 2}-1}_{24k'})\\=24k''}$$

Case 2 : $$n$$ is even

In this case $$2×7^n+3×5^n-5{=14×7^{n-1}+15×5^{n-1}-5\\=14\times\underbrace{(7^{n-1}+5^{n-1})}_{12k}+5(5^{n-2}-1)\\=24k+5(\underbrace{25^{n-2\over 2}-1}_{24k'})\\=24k''}$$

Note that you have $$7^n - 1 = 6a\\ 5^n - 1 = 4b$$ Now we're interested in whether $$a$$ and $$b$$ are even or odd. Which is to say we want to know when $$7^n - 1$$ is divisible by $$4$$ (so that when you divide it by $$6$$ you get an even number), and when $$5^n-1$$ is divisible by $$8$$ (so that when you divide it by $$4$$, you get an even number).

The binomial theorem gives $$7^n - 1 = (8-1)^n - 1\\ = 8^n - \binom n18^{n-1} + \cdots + (-1)^{n-1}\binom{n}{n-1}8 + (-1)^n - 1$$ We see that this is divisible by $$4$$ exactly when $$(-1)^n - 1$$ is, which is to say when $$n$$ is even.

Then we have $$5^n - 1 = (4 + 1)^n - 1\\ = 4^n + \binom n14^{n-1} + \cdots + \binom{n}{n-1}4 + 1 - 1$$ and we see that this is divisible by $$8$$ precisely when $$\binom{n}{n-1} = n$$ is even.

So $$a$$ and $$b$$ are both even for even $$n$$, and both odd for odd $$n$$, proving that $$a+b$$ is always even, meaning $$12(a+b)$$ is divisible by $$24$$.

You may split it up by calculating $$\mod 8$$ and $$\mod 3$$:

• $$\mod 8$$: $$\begin{eqnarray*} 2×7^n+3×5^n-5 & \equiv_8 & 2\times (-1)^n + 3\times (-3)^n +3 \\ & \equiv_8 & 2\times (-1)^n + 3((-3)^n + 1)\\ & \stackrel{3^2 \equiv_8 1}{\equiv_8}& \begin{cases} 2+3\times (1+1) & n = 2k \\ -2 +3 (-3 + 1) & n= 2k+1\end{cases}\\ & \equiv_8 & 0 \end{eqnarray*}$$
• $$\mod 3$$: $$\begin{eqnarray*} 2×7^n+3×5^n-5 & \equiv_3 & 2\times 1^n + 3\times (-1)^n +1 \\ & \equiv_3 & 3\times (1 + (-1)^n)\\ & \equiv_3 & 0 \end{eqnarray*}$$

$$2×7^n-2+3×5^n-3\\ 2(7^n-1)+3(5^n-1)\\ 2×6a\ +\ 3×4b\\ 12(\color{#c00}{a+b})\ \$$ but it is not enough [to prove divisibility by $$24$$]

Finish simply with $$\ 2\mid \color{#c00}{a+b}\, =\, \dfrac{7^{\large n}\!-1}{7-1} + \dfrac{5^{\large n}\!-1}{5-1}\, =\, \overbrace{7^{\large n-1}\!+5^{\large n-1}}^{\rm even} +\cdots + \overbrace{7+5}^{\rm even}\, +\, \overbrace{1+1}^{\rm even}$$