Maths Olympiad Prep

Library / /453 of 520

Number theory Difficulty 6.9 National olympiad Prove it

27. For integer points (x,y)(x, y) on the plane, if (x,y)=1(x, y)=1, then it is called "reduced". Prove: For any nNn \in \mathbf{N}^{*}, there exists an integer point on the plane such that its distance to any reduced integer point is greater than nn.

Solution

27. Let i,jZ,ni,jni, j \in \mathbf{Z}, -n \leqslant i, j \leqslant n, then pijp_{ij} represents (2n+1)2(2n+1)^2 different primes. By the Chinese Remainder Theorem, there exist a,ba, b that satisfy the congruence systems
ai(modpij),ni,jn,bj(modpij),ni,ina \equiv i \pmod{p_{ij}}, -n \leqslant i, j \leqslant n, b \equiv j \pmod{p_{ij}}, -n \leqslant i, i \leqslant n, then (a,b)(a, b) is an integer point that satisfies the conditions. Because if the distance between (x,y)(x, y) and (a,b)(a, b) is n\leqslant n, then
(ax)2+(by)2n\sqrt{(a-x)^2 + (b-y)^2} \leqslant n

which implies
(ax)2+(by)2n2(a-x)^2 + (b-y)^2 \leqslant n^2. This leads to
axn,byn|a-x| \leqslant n, |b-y| \leqslant n

Assume without loss of generality that ax=i,by=ja-x=i, b-y=j, i.e., x=ai,y=bj,ni,jnx=a-i, y=b-j, -n \leqslant i, j \leqslant n. By the choice of a,ba, b, it follows that x,yx, y are multiples of pijp_{ij}, hence (x,y)(x, y) is not a primitive integer point.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.