# Prove by induction that $7^{2n}-48n-1$ is divisible by 2304

$$P(n):2304\mid7^{2n}-48n-1$$ I've done the base case; $P(1)$ is true because the expression then evaluates to zero, which is divisible by 2304. Now I'm stuck on the inductive step: proving $P(m+1)$ true if $P(m)$ is true. I do know this though: $$7^{2m+2}-48(m+1)-1 =49\cdot7^{2m}-48m-49$$

• Now what have you tried, eh? – Parcly Taxel Nov 4 '16 at 2:21
• @ParclyTaxel it's how other sums are solved in my textbook.. please help if you can! – user385779 Nov 4 '16 at 2:21

$$7^{2(m+1)} - 48(m+1) - 1 = 49 \cdot 7^{2m} - 48m - 49 = 49\left(7^{2m} - 48m - 1\right) + 2304m$$

• But how can we remove common when it's only 48m and how does 2304 balance it out? Please explain really confused Sir. – user385779 Nov 4 '16 at 2:54
• You should verify the equalities I listed, namely that $2304 = 49\cdot 48 - 48$. Then you can continue your induction proof. – Michael Biro Nov 4 '16 at 2:58
• THANK YOU SO VERY MUCH! THANKS A LOT SIR. – user385779 Nov 4 '16 at 3:02

Hint $\$ Conceptually, the induction is simply the first two terms of the Binomial Theorem, namely put $\ a = 48\$ below and note $\,48^2 = 2304$

${\rm mod}\ a^2\!:\ (1\!+\!a)^n \equiv 1\! +\! na\$ is true for $\ n = 0\$ and the induction step is easy:

$\qquad\quad\ (1\!+\!a)^{n+1}\! = (1\!+\!a)(1\!+\!a)^n\overset{\rm induct}= (1\!+\!a)(1\!+\!na) \equiv 1\!+\!(n\!+\!1)a\$ by $\ a^2\equiv 0$

• Wow thanks so explaining so clearly, much appreciated – user385779 Nov 4 '16 at 3:51

Let $f(n)=7^{2n}-48n-1$.

By direct evaluation, we have $f(1)=0$.

We want to show $2304{\,\mid\,}f(n)$, for all positive integers $n$.

Proceed by induction on $n$ . . .

Since $f(1)=0$, the truth for the base case, $n=1$, is immediate.

Next, suppose $2304{\,\mid\,}f(n)$, for some positive integer $n$. \begin{align*} \text{Then}\;\;&2304{\,\mid\,}f(n)\\[4pt] \implies\;&f(n)\equiv 0\;(\text{mod}\;2304)\\[4pt] \implies\;&7^{2n}-48n-1\equiv 0\;(\text{mod}\;2304)\\[4pt] \implies\;&7^{2n}\equiv 48n+1\;(\text{mod}\;2304)\\[4pt] \implies\;&49\left(7^{2n}\right)\equiv 49(48n+1)\;(\text{mod}\;2304)\\[4pt] \implies\;&7^{2(n+1)}\equiv 2352n+49\;(\text{mod}\;2304)\\[4pt] \implies\;&7^{2(n+1)}\equiv 48n+49\;(\text{mod}\;2304)\\[4pt] \implies\;&7^{2(n+1)}-48n-49\equiv 0\;(\text{mod}\;2304)\\[4pt] \implies\;&7^{2(n+1)}-48(n+1)-1\equiv 0\;(\text{mod}\;2304)\\[4pt] \implies\;&f(n+1)\equiv 0\;(\text{mod}\;2304)\\[4pt] \implies\;&2304{\,\mid\,}f(n+1)\\[4pt] \end{align*} which completes the induction.