Number theoryDifficulty 8.2ShortlistFind the answer
Does there exist an infinite set M consisting of positive integers such that for any a,b∈M, with a<b, the sum a+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<… so that ni+nj is square-free for all i<j. Suppose that we already have some numbers n1<…<nk(k≥2), which satisfy this condition and find a suitable number nk+1 to be the next element of the sequence. We will choose nk+1 of the form nk+1=1+Mx, with M=((n1+…+nk+2k)!)2 and some positive integer x. For i=1,2,…,k we have ni+nk+1=1+Mx+ni=(1+ni)mi, where mi and M are co-prime, so any perfect square dividing 1+Mx+ni is co-prime with M. In order to find a suitable x, take a large N and consider the values x=1,2,…,N. If a value 1≤x≤N is not suitable, this means that there is an index 1≤i≤k and some prime p such that p2∣1+Mx+ni. For p≤2k this is impossible because p∣M. Moreover, we also have p2≤1+Mx+ni<M(N+1), so 2k<p<M(N+1). For any fixed i and p, the values for x for which p2∣1+Mx+ni form an arithmetic progression with difference p2. Therefore, there are at most p2N+1 such values. In total, the number of unsuitable values x is less than i=1∑k2k<p<M(N+1)∑(p2N+1)<k⋅Np>2k∑p21+p<M(N+1)∑1<<kNp>2k∑(p−11−p1)+kM(N+1)<2N+kM(N+1) If N is big enough then this is less than N, and there exist a suitable choice for x.
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.