Maths Olympiad Prep

Library / /36 of 43

Number theory Difficulty 8.2 Shortlist Find the answer

Does there exist an infinite set MM consisting of positive integers such that for any a,bMa, b \in M, with a<ba<b, the sum a+ba+b is square-free? (A positive integer is called square-free if no perfect square greater than 1 divides it.)

A number or a short expression. Spacing and $ signs are ignored.

Solution

The answer is yes. We construct an infinite sequence 1=n1<2=n2<n3<1=n_{1}<2=n_{2}<n_{3}<\ldots so that ni+njn_{i}+n_{j} is square-free for all i<ji<j. Suppose that we already have some numbers n1<<nk(k2)n_{1}<\ldots<n_{k}(k \geq 2), which satisfy this condition and find a suitable number nk+1n_{k+1} to be the next element of the sequence. We will choose nk+1n_{k+1} of the form nk+1=1+Mxn_{k+1}=1+M x, with M=((n1++nk+2k)!)2M=\left(\left(n_{1}+\ldots+n_{k}+2 k\right)!\right)^{2} and some positive integer xx. For i=1,2,,ki=1,2, \ldots, k we have ni+nk+1=1+Mx+ni=(1+ni)min_{i}+n_{k+1}=1+M x+n_{i}=\left(1+n_{i}\right) m_{i}, where mim_{i} and MM are co-prime, so any perfect square dividing 1+Mx+ni1+M x+n_{i} is co-prime with MM. In order to find a suitable xx, take a large NN and consider the values x=1,2,,Nx=1,2, \ldots, N. If a value 1xN1 \leq x \leq N is not suitable, this means that there is an index 1ik1 \leq i \leq k and some prime pp such that p21+Mx+nip^{2} \mid 1+M x+n_{i}. For p2kp \leq 2 k this is impossible because pMp \mid M. Moreover, we also have p21+Mx+ni<p^{2} \leq 1+M x+n_{i}< M(N+1)M(N+1), so 2k<p<M(N+1)2 k<p<\sqrt{M(N+1)}. For any fixed ii and pp, the values for xx for which p21+Mx+nip^{2} \mid 1+M x+n_{i} form an arithmetic progression with difference p2p^{2}. Therefore, there are at most Np2+1\frac{N}{p^{2}}+1 such values. In total, the number of unsuitable values xx is less than i=1k2k<p<M(N+1)(Np2+1)<k(Np>2k1p2+p<M(N+1)1)<<kNp>2k(1p11p)+kM(N+1)<N2+kM(N+1)\begin{aligned} & \sum_{i=1}^{k} \sum_{2 k<p<\sqrt{M(N+1)}}\left(\frac{N}{p^{2}}+1\right)<k \cdot\left(N \sum_{p>2 k} \frac{1}{p^{2}}+\sum_{p<\sqrt{M(N+1)}} 1\right)< \\ & <k N \sum_{p>2 k}\left(\frac{1}{p-1}-\frac{1}{p}\right)+k \sqrt{M(N+1)}<\frac{N}{2}+k \sqrt{M(N+1)} \end{aligned} If NN is big enough then this is less than NN, and there exist a suitable choice for xx.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.