Welcome to our community

Be a part of something great, join today!

Problem Of The Week # 293 - Dec 14, 2017

Status
Not open for further replies.
  • Thread starter
  • Admin
  • #1

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,198
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 POTW submission guidelines to find out how to submit your answers!
 
  • Thread starter
  • Admin
  • #2

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,198
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:


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$.
 
Status
Not open for further replies.