uniolympiads English

IMC 2005, Ημέρα 2, Θέμα 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.
Πρωτότυπο από το επίσημο 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

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

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.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδες 3–4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;