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

Status
Not open for further replies.

#### Ackbach

##### Indicium Physicus
Staff member
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\}?$

-----

#### Ackbach

##### Indicium Physicus
Staff member
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.