For every pair $(m, n)$ of positive integers, a positive real number $a_{m, n}$ is given. Assume that \[a_{m+1, n+1} = \frac{a_{m, n+1} a_{m+1, n} + 1}{a_{m, n}}\]for all positive integers $m$ and $n$. Suppose further that $a_{m, n}$ is an integer whenever $\min(m, n) \le 2$. Prove that $a_{m, n}$ is an integer for all positive integers $m$ and $n$.
Problem
Source: USA TST for EGMO 2019, Problem 4 (adapted from IMO TST Problem 4)
Tags: algebra, number theory
21.01.2019 21:55
Assume that $a_{m,n}, a_{m+1,n}, a_{m, n+1}, a_{m-1, n}, a_{m, n-1}, a_{m-1, n-1}$ are integers. Note that $a_{m-1, n}a_{m, n-1}\equiv -1 \mod a_{m,n}$. Also, we have $a_{m-1, n}a_{m, n+1}\equiv 1\mod a_{m,n}$, so we have $$a_{m, n+1}a_{m+1, n}\equiv\frac{1}{a_{m-1, n}}\cdot\frac{1}{a_{m, n-1}}\equiv\frac{1}{-1}=-1\mod a_{m, n}$$ which means we can find an integer $k=a_{m+1, n+1}$ such that $ka_{m, n}=a_{m, n+1}a_{m+1, n}+1$. Now, we can just use this algorithm and strong induction on $m+n$ to solve the problem; the base case is given by the problem and the algorithm means we can show that $a_{m,n}$ is an integer for $m, n>2$, and we know by the problem statement that if either $m, n \le 2$ then $a_{m, n}$ is an integer, so we're done.
22.01.2019 12:11
lifeisgood03 wrote: Note that $a_{m-1, n}a_{m, n-1}\equiv -1 \mod a_{m,n}$. In this problem, the $a_{m,n}$ are real numbers. What's your intended meaning of congruences over the reals?
23.01.2019 02:42
test20 wrote: lifeisgood03 wrote: Note that $a_{m-1, n}a_{m, n-1}\equiv -1 \mod a_{m,n}$. In this problem, the $a_{m,n}$ are real numbers. What's your intended meaning of congruences over the reals? Hi, good point! This definitely should be fixed. However, it doesn't really matter because for the purposes of our induction, we're assuming all numbers used in the equation are integers to prove that $a_{m+1,n+1}$ must be an integer.
18.03.2020 06:55
We induct on $m+n$. The base case of $m+n\le 5$ is clear. Assume $a_{m',n'}$ is an integer for all $m'+n'\le m+n+1$. We will show $a_{m+1,n+1}$ is an integer. We can rewrite the condition as $a_{m,n} = \frac{a_{m,n+1}a_{m+1,n}+1}{a_{m+1,n+1}}$. Shifting indices, $a_{m-1,n-1} = \frac{a_{m,n-1}a_{m-1,n}+1}{a_{m,n}}$. This is an integer by induction, hence, $a_{m,n-1}a_{m-1,n}\equiv -1\pmod{a_{m,n}}$. Also, $a_{m+1,n} = \frac{a_{m,n}a_{m+1,n+1}-1}{a_{m,n+1}}$. Shifting indices, $a_{m+1,n-1} = \frac{a_{m,n-1}a_{m+1,n}-1}{a_{m,n}}$. This means $a_{m,n-1}a_{m+1,n} \equiv 1 \pmod{a_{m,n}}$. Similarly, $a_{m-1,n}a_{m+1,n} \equiv 1\pmod{a_{m,n}}$. Now, \[ a_{m,n+1}a_{m+1,n} \equiv \frac{1}{a_{m,n-1}} \cdot \frac{1}{a_{m-1,n}} \equiv \frac{1}{-1} \equiv -1 \pmod{a_{m,n}}. \]Therefore, $a_{m+1,n+1}$ is an integer, completing the induction.
21.01.2022 00:50
Rewrite the condition as \[a_{m,n} a_{m+1,n+1} - a_{m,n+1} a_{m+1,n}=1.\] Consider the infinite matrix \[\begin{bmatrix} \vdots & \vdots & \vdots & \vdots \\ a_{1,3} & a_{2,3} & a_{3,3} & \ldots \\ a_{1,2} & a_{2,2} & a_{3,2} & \ldots \\ a_{1,1} & a_{2,1} & a_{3,1} & \ldots \\ \end{bmatrix}\] Note that each $2\times 2$ sub-matrix of this must have determinant $-1$. By simple induction, it suffices to prove the following lemma. Lemma: If we have the $3\times 3$ matrix, \[\begin{bmatrix} a & b & i\\ c & d & e \\ f & g & h \\ \end{bmatrix},\]where $a,b,c,d,e,f,g,h$ are all integers, and each $2\times 2$ sub-matrix has determinant $-1$, then $i$ is also an integer. Proof: It suffices to show that $eb\equiv -1\pmod d$. We have $cg\equiv -1\pmod d$ and $bc\equiv eg\equiv 1\pmod d$. Thus, $c^2g^2eb=(cg)^2eb\equiv -1\pmod d\implies eb\equiv -1\pmod d$. $\blacksquare$