3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – AlephNull Mar 20 at 11:27
5
$\begingroup$

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}$.
$\endgroup$
  • 1
    $\begingroup$ may I suggest that you use $\times$ instead of the dot? $\endgroup$ – Ertxiem Mar 20 at 11:29
  • 1
    $\begingroup$ Yes, you are allowed to do that. :-) $\endgroup$ – José Carlos Santos Mar 20 at 11:30
  • 1
    $\begingroup$ Thank you very much. :) $\endgroup$ – Ertxiem Mar 20 at 11:35
  • 1
    $\begingroup$ 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. $\endgroup$ – Carl Mummert Mar 20 at 12:10
  • 1
    $\begingroup$ @Carl Do you know any way to formalize "proof without induction" at an elementary level? $\endgroup$ – Bill Dubuque Mar 21 at 2:49
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Very nice and simple.... +1 $\endgroup$ – Shailesh Mar 20 at 12:07
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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*}
$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.