MHB Problem Of The Week # 293 - Dec 14, 2017

[Ackbach]

Here is this week's POTW:

-----

What is the greatest common divisor of the set of numbers $\left\{16^n+10n-1 \;|\; n=1, 2, 3, \dots\right\}?$

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Congratulations to kaliprasad, kiwi, johng, and castor28 for their correct solutions to this week's POTW, which was the MAA Challenges Problem 174. castor28's solution follows:

[sp]
Let us write $f(n)=16^n+10n-1$ and $d$ for the GCD of $\{f(n)\mid n \ge 1\}$.

Since $f(1)=25$, $d$ can only be 1, 5, or 25. To prove that $d=25$, we only need to prove that $25\mid f(n)$ for all $n\ge 1$.

We prove this by induction on $n$.

We obviously have $25\mid f(1)=25$. Assume now that $n>1$. We have:

$$\begin{align*}
f(n+1) - f(n) &= 15\cdot16^{n-1} + 10\\
&= 5(3\cdot16^{n-1} + 2)
\end{align*}$$
​

Since $3\cdot16^{n-1} + 2\equiv 3\cdot1^{n-1}+2\equiv0\pmod5$, we conclude that $f(n+1)\equiv f(n)\equiv0\pmod{25}$ (using the induction hypothesis), and $d=25$.
[/sp]