Let $a_n = \frac{10^n-1}{9}$. Define $d_n$ to be the greatest common divisor of $a_n$ and $a_{n+1}$. What is the maximum possible value that $d_n$ can take on?

Guest Aug 16, 2019

#1**+2 **

Let \(a_n = \dfrac{10^n-1}{9}\).

Define \(d_n\) to be the greatest common divisor of \(a_n\) and \(a_{n+1}\).

What is the maximum possible value that \(d_n\) can take on?

\(\begin{array}{|rcll|} \hline \mathbf{a_n} &=& \mathbf{\dfrac{10^n-1}{9}} \\ \hline \mathbf{a_{n+1}} &=& \mathbf{\dfrac{10^{n+1}-1}{9}} \\\\ &=& \dfrac{10^{n}10-1}{9} \\\\ &=& \dfrac{10^{n}10-(10-9)}{9} \\\\ &=& \dfrac{10^{n}10-10+9}{9} \\\\ &=& \dfrac{10\left( 10^{n} -1 \right) +9}{9} \\\\ &=& \dfrac{10\left( 10^{n} -1 \right)}{9} + 1 \\\\ &=& 10\cdot \left(\dfrac{ 10^{n} -1 }{9}\right) + 1 \quad | \quad \dfrac{10^n-1}{9} = a_n \\\\ \mathbf{a_{n+1}} &=& \mathbf{10a_n + 1} \\ \hline \end{array}\)

\(\begin{array}{|rcll|} \hline d_n &=& \gcd( a_n,\ a_{n+1} ) \\ &=& \gcd( a_{n+1},\ a_n ) \quad | \quad a_{n+1} =10a_n + 1 \\ &=& \gcd( 10a_n+1,\ a_n ) \\ && \boxed{\text{Formula: }\gcd(a,b)=\gcd(a-b,b),\ \text{if } a > b } \\ &=& \gcd( 10a_n+1 - 10a_n,\ a_n ) \\ &=& \gcd( 1 ,\ a_n ) \\ && \boxed{\text{Formula: }\gcd(1,a)=1} \\ &=& \mathbf{1} \\ \hline \end{array}\)

The maximum possible value that \(d_n\) can take on is **1**

heureka Aug 17, 2019