Maths Olympiad Prep

Library / /11 of 31

Algebra Difficulty 5.9 AIME, harder Prove it South Africa

Let AA be a set of real numbers satisfying the following:
(a) n2+1A\sqrt{n^2+1} \in A for all positive integers nn;
(b) if xAx \in A and yAy \in A, then xyAx - y \in A.
Prove that every integer can be written as a product of two different elements in AA.

Solution

We first observe some natural consequences of property (b):
(i) 0A0 \in A, since if xAx \in A is arbitrary, then 0=xxA0 = x - x \in A.
(ii) If xAx \in A, then x=0xA-x = 0 - x \in A.
(iii) If x,yAx, y \in A, then x+y=x(y)Ax + y = x - (-y) \in A.
(iv) If xAx \in A, then kxAkx \in A for any integer kk. This follows easily by induction on kk (for positive kk), using (iii). For negative kk, apply (ii). For k=0k = 0, use (i).

So now we know that km2+1+ln2+1Ak\sqrt{m^2+1} + l\sqrt{n^2+1} \in A for all integers kk and ll, and all positive integers mm and nn.
Let us first try to write the integer 1 as a product of two different elements in AA: We can find (by inspection) positive integers k,l,m,nk, l, m, n such that 1=k2(m2+1)l2(n2+1)1 = k^2(m^2+1) - l^2(n^2+1), for example, k=3,m=1,l=1,n=4k=3, m=1, l=1, n=4. (There are many other possibilities as well.) Hence,
1=32(12+1)12(42+1)=(312+1142+1)(312+1+142+1), \begin{aligned} 1 &= 3^2(1^2 + 1) - 1^2(4^2 + 1) \\ &= (3\sqrt{1^2 + 1} - 1\sqrt{4^2 + 1})(3\sqrt{1^2 + 1} + 1\sqrt{4^2 + 1}), \end{aligned}
a product of two different elements of AA.
If pp is an arbitrary integer, then we have
p=p1=p(312+1142+1)(312+1+142+1)=(3p12+1p42+1)(312+1+142+1), \begin{aligned} p = p \cdot 1 &= p \cdot (3\sqrt{1^2+1} - 1\sqrt{4^2+1})(3\sqrt{1^2+1} + 1\sqrt{4^2+1}) \\ &= (3p\sqrt{1^2+1} - p\sqrt{4^2+1})(3\sqrt{1^2+1} + 1\sqrt{4^2+1}), \end{aligned}
again a product of two elements of AA. These two elements of AA are indeed different, since if 3p12+1p42+1=312+1+142+13p\sqrt{1^2+1} - p\sqrt{4^2+1} = 3\sqrt{1^2+1} + 1\sqrt{4^2+1}, then we would have p=35+634p = 35 + 6\sqrt{34}, which is not an integer.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.