712 Number Theory
and
bn+n≡b+n≡b−a(modp).It follows thatpdividesan+nbut does not dividebn+n, a contradiction. Hencea=b,
as desired.
(short list of the 46th International Mathematical Olympiad, 2005)
793.The idea is to place(a, b)at the center of a square of size( 2 n+ 1 )×( 2 n+ 1 )having
the property that all lattice points in its interior and on its sides are not visible from the
origin. To this end, choose( 2 n+ 1 )^2 distinct primespij,−n≤i, j≤n. Apply the
Chinese Remainder Theorem to find anawitha+i≡ 0 (modpij)for alli, jand ab
withb+j≡ 0 (modpij)for alli, j. For anyiandj,a+iandb+jare both divisible
bypij. Hence none of the points(a+i, b+j)are visible from the origin. We conclude
that any point visible from the origin lies outside the square of size( 2 n+ 1 )×( 2 n+ 1 )
centered at(a, b), hence at distance greater thannfrom(a, b).
(American Mathematical Monthly, 1977, proposed by A.A. Mullin)
794.This problem tests whether you really understood our discussion of the procedure
of writing the elements of SL( 2 ,Z)in terms of the generators.
Call the first matrix from the statementS. This matrix is no longer in SL( 2 ,Z)! Let
us see again where the linear equation is. The determinant of the matrix
[
12 5
73
]
is equal to 12· 3 − 7 · 5 =1, so( 3 , 5 )is a solution to the linear equation 12x− 7 y=1.
Note that
S(
p
q)
=
(
q
p)
,Tn(
p
q)
=
(
p+nq
q)
.
SoSflips a fraction, andTkaddskto it. This time it is the continued fraction expansion
12
7= 1 +
1
1 +
1
2 +
1
2
(no negatives !). All we need to do is start withSand apply to itT^2 , thenS, then again
T^2 , and so on, following the continued fraction expansion from bottom to top. We thus
obtain
[
12 5
73