MHB What is the Limit of the Greatest Common Divisor in a Matrix Sequence?

[Ackbach]

Here is this week's POTW:

-----

For $n\ge 1$, let $d_n$ be the greatest common divisor of the entries of $A^n-I$, where
$$A=\begin{bmatrix}3&2\\4&3\end{bmatrix} \qquad \text{and} \qquad
I=\begin{bmatrix}1&0\\0&1\end{bmatrix}.$$
Show that $\displaystyle \lim_{n\to\infty}d_n=\infty$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Congratulations to Opalg for his correct solution, which follows:

Spoiler

Two facts about the greatest common divisor $d(a,b)$ of two positive integers $a$ and $b$. Firstly, if $k$ is a positive integer then $d(ka,kb) = kd(a,b)$. Secondly, $d(a^2,b^2) = (d(a,b))^2.$

let $A = \begin{bmatrix}3&2 \\ 4&3 \end{bmatrix}$. Then $A^n - I = \begin{bmatrix}x_n&y_n \\ 2y_n&x_n \end{bmatrix}$ for some positive integers $x_n,y_n.$ This is easily proved by induction. The base case $n=1$ holds, with $x_1=y_1=2.$ If the result holds for $n$ then $A^n = \begin{bmatrix}x_n+1&y_n \\ 2y_n&x_n+1 \end{bmatrix}$ and so $$A^{n+1} = A^nA = \begin{bmatrix}x_n+1&y_n \\ 2y_n&x_n+1 \end{bmatrix} \begin{bmatrix}3&2 \\ 4&3 \end{bmatrix} = \begin{bmatrix}3x_n + 4y_n +3&2x_n + 3y_n + 2 \\ 4x_n + 6y_n + 4&3x_n + 4y_n +3 \end{bmatrix},$$ so that $A^{n+1} - I$ is of the required form, with $x_{n+1} = 3x_n + 4y_n + 2$ and $y_{n+1} = 2x_n + 3y_n + 2.$

That completes the inductive step. The formula for $x_{n+1}$ shows that $x_{n+1} >3x_n$, which means that $x_n \to\infty$ as $n\to \infty$. Notice also that the greatest common divisor of the entries of $A^n - I$ is $d(x_n,y_n).$

Next, $\det(A^n) = (\det A)^n = 1$, so that $(x_n+1)^2 - 2y_n^2 = 1$. Therefore $x_n(x_n+2) = 2y_n^{\,2}$, so that $x_n$ divides $2y_n^{\,2}$. Also, $x_n$ divides $2x_n^{\,2}$ (obviously). It follows that $d(2x_n^{\,2}, 2y_n^{\,2}) \geqslant x_n$. The two facts at the beginning of the solution then tell us that $d(x_n,y_n) \geqslant \sqrt{x_n/2},$ and therefore $d(x_n,y_n) \to\infty$ as $n\to\infty.$