+0

# Euclidian Algorithm Problem

0
121
1

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?

Aug 16, 2019

#1
+23273
+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

Aug 17, 2019