# Prove by induction that $23^{2n} + 31^{2n}+46$ is divisible by 48 for all integers $n \ge 0$

The base case, $n = 0$: $$23^0+31^0+46=48$$ and $48 \bmod 48 = 0$.

Inductive Hypothesis: Let's assume it is true for $n = k$. Then $$p(k) = 23^{2k} + 31^{2k}+46$$ $$\Rightarrow p(k+1) = 23^{2\left(k+1\right)} + 31^{2\left(k+1\right)}+46 = 529\left(23^{2k}\right)+961\left(31^{2k}\right)+46$$

However, I am not sure how to proceed from here in order to get an expression that is divisible by $48$. Thanks in advance for any hints.

• Edited as pointed out below. Commented Aug 29, 2018 at 3:52

## 6 Answers

Note that your $p(k)$ is written wrongly.

\begin{align} 529(23^{2k}+ 31^{2k})+432(31^{2k})+46 &= 529(23^{2k}+ 31^{2k})+9(48)(31^{2k})+46 \\ &= 529(23^{2k}+ 31^{2k}+46)+9(48)(31^{2k})+46(1-529) \\ &= 529(23^{2k}+ 31^{2k}+46)+9(48)(31^{2k})-46(528) \\ &= 529(23^{2k}+ 31^{2k}+46)+9(48)(31^{2k})-46(48)(11) \\ \end{align}

If $48$ divides $23^{2k} + 31^{2k}+46$ then there exists an integer $m$ such that $48m= 23^{2k} + 31^{2k}+46$, solving for say $31^{2k}$ (you could have done $23^{2k}$) we get $31^{2k}=48m-23^{2k}-46$ and use that when showing the statement is true at $k+1$. All that is left to do is show that $p(k+1)=48r$ for some integer $r$ which will be in terms of $m$

Note that $529 \equiv 961 \equiv 1 \mod 48$.

\begin{align} p(k+ 1) &\equiv 23^{2(k+1)} + 31^{2(k+1)} + 46 &\mod 48\\ p(k+ 1) &\equiv 529 \cdot 23^{2k} + 961 \cdot 31^{2k} + 46 &\dots\\ p(k+ 1) &\equiv 23^{2k} +31^{2k} + 46 &\dots\\ p(k+ 1) &\equiv p(k) &\dots \end{align}

Now use $p(k+1)\equiv p(k) \mod 48$ as your inductive step to show that $p(k) \equiv 0 \mod 48$ for all $k$.

Note that $$529\left(23^{2k}\right)+961\left(31^{2k}\right)+46$$

$$=(11\times 48 +1)\left(23^{2k}\right)+(20\times 48 +1)\left(31^{2k}\right)+46$$

$$\equiv \left(23^{2k}\right)+\left(31^{2k}\right)+46 \text { mod (48)}$$

Now use the induction hypothesis and you will be done.

• Thanks, that is a better way to write it . Commented Aug 29, 2018 at 3:46
• Also a quick remark, it's $+46$, not $+48$.
– orlp
Commented Aug 29, 2018 at 3:46

Method$\#1:$ $$p(k+1)-23^2p(k)=31^{2k}(31^2-23^2)=31^{2k}\cdot9\cdot48$$

Or $$p(k+1)-31^2p(k)=-23^{2k}(31^2-23^2)=\cdots$$

In either case,$$48|p(k+1)\iff48|p(k)$$ as $(23,48)=(31,48)=1$

Method$\#2:$

W/O induction, $23^2=(24-1)^2\equiv1\pmod{48}\implies23^{2n}\equiv(1)^n$

and $31^2=961\equiv1\pmod{48}\implies31^{2n}\equiv(1)^n$

Here is another take: $$23^{2n} + 31^{2n}= (23^2)^n + (31^2)^n \equiv 1^n + 1^n = 2 \bmod 48$$