We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive pseudonymised information about your use of our website. cookie policy and privacy policy.
 
+0  
 
0
121
1
avatar

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
avatar+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

 

laugh

 Aug 17, 2019

30 Online Users

avatar
avatar
avatar