uniolympiads Ελληνικά

IMC 2005, Day 2, Problem 6

Prove that if pp and qq are rational numbers and r=p+q7r = p + q\sqrt{7}, then there exists a matrix (abcd)≠±(1001)\begin{pmatrix} a & b \\ c & d \end{pmatrix} \ne \pm\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} with integer entries and with ad−bc=1ad - bc = 1 such that

ar+bcr+d=r.\frac{ar + b}{cr + d} = r.
Original from the official PDF√ Problem 6. Prove and q are rational numbers and r = p + q 7, then there exists that if p a b 1 0 a matrix 6 = ± with integer entries and with ad − bc = 1 such that c d 0 1 ar + b = r. cr + d

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. First consider the case when q=0q=0 and rr is rational. Choose a positive integer tt such that r2tr^2t is an integer and set

(abcd)=(1+rt−r2tt1−rt).\begin{pmatrix} a & b\\ c & d \end{pmatrix}=\begin{pmatrix} 1+rt & -r^2t\\ t & 1-rt \end{pmatrix}.
Then
det⁡(abcd)=1andar+bcr+d=(1+rt)r−r2ttr+(1−rt)=r.\det\begin{pmatrix} a & b\\ c & d \end{pmatrix}=1\quad\text{and}\quad\frac{ar+b}{cr+d}=\frac{(1+rt)r-r^2t}{tr+(1-rt)}=r.

Now assume q≠0q\ne0. Let the minimal polynomial of rr in Z[x]\mathbb{Z}[x] be ux2+vx+wux^2+vx+w. The other root of this polynomial is r‾=p−q7\overline{r}=p-q\sqrt7, so v=−u(r+r‾)=−2upv=-u(r+\overline{r})=-2up and w=urr‾=u(p2−7q2)w=ur\overline{r}=u(p^2-7q^2). The discriminant is v2−4uw=7⋅(2uq)2v^2-4uw=7\cdot(2uq)^2. The left-hand side is an integer, implying that also Δ=2uq\Delta=2uq is an integer.

The equation ar+bcr+d=r\frac{ar+b}{cr+d}=r is equivalent to cr2+(d−a)r−b=0cr^2+(d-a)r-b=0. This must be a multiple of the minimal polynomial, so we need

c=ut,d−a=vt,−b=wtc=ut,\quad d-a=vt,\quad -b=wt
for some integer t≠0t\ne0. Putting together these equalities with ad−bc=1ad-bc=1 we obtain that
(a+d)2=(a−d)2+4ad=4+(v2−4uw)t2=4+7Δ2t2.(a+d)^2=(a-d)^2+4ad=4+(v^2-4uw)t^2=4+7\Delta^2t^2.
Therefore 4+7Δ2t24+7\Delta^2t^2 must be a perfect square. Introducing s=a+ds=a+d, we need an integer solution (s,t)(s,t) for the Diophantine equation
s2−7Δ2t2=4(1)s^2-7\Delta^2t^2=4\tag{1}
such that t≠0t\ne0.

The numbers ss and tt will be even. Then a+d=sa+d=s and d−a=vtd-a=vt will be even as well and aa and dd will be really integers.

Let (8±37)n=kn±ln7(8\pm3\sqrt7)^n=k_n\pm l_n\sqrt7 for each integer nn. Then kn2−7ln2=(kn+ln7)(kn−ln7)=((8+37)n(8−37))n=1k_n^2-7l_n^2=(k_n+l_n\sqrt7)(k_n-l_n\sqrt7)=((8+3\sqrt7)^n(8-3\sqrt7))^n=1 and the sequence (ln)(l_n) also satisfies the linear recurrence ln+1=16ln−ln−1l_{n+1}=16l_n-l_{n-1}. Consider the residue of lnl_n modulo Δ\Delta. There are Δ2\Delta^2 possible residue pairs for (ln,ln+1)(l_n,l_{n+1}) so some are the same. Starting from such two positions, the recurrence shows that the sequence of residues is periodic in both directions. Then there are infinitely many indices such that ln≡l0=0(modΔ)l_n\equiv l_0=0\pmod\Delta.

Taking such an index nn, we can set s=2kns=2k_n and t=2ln/Δt=2l_n/\Delta.

Remarks. 1. It is well-known that if D>0D>0 is not a perfect square then the Pell-like Diophantine equation

x2−Dy2=1x^2-Dy^2=1
has infinitely many solutions. Using this fact the solution can be generalized to all quadratic algebraic numbers.

  1. It is also known that the continued fraction of a real number rr is periodic from a certain point if and only if rr is a root of a quadratic equation. This fact can lead to another solution.

Transcribed from the official solutions, pages 3–4. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?