Denote vp(k) as the exponent of prime p in the prime factorization of positive integer k. It is easy to see that vp(ab)=vp(a)+vp(b) for all positive integers a,b.
We have 2015=5⋅13⋅31, 2016=25⋅32⋅7.
Denote M=2015⋅2016 and
N={2,3,5,7,13,31}
Suppose there exist n positive integers x1,x2,x3,…,xn arranged on the circle satisfying the given condition and denote xn+1≡x1 and xn+2≡x2.
Since xixi+1 is not divisible by M for i=1,…,n, then there exists a prime pi∈N such that
vpi(xixi+1)<vpi(M)⇔vpi(xi)+vpi(xi+1)<vpi(M)(*)
These primes form a sequence p1,p2,…,pn and the elements can be repeated. We will prove that pi=pj with i,j two non-adjacent indices.
Indeed, if there are some non-adjacent indices i,j such that pi=pj=p. Denote a=vp(M) and from (*), we have vp(xi)+vp(xi+1)<a and vp(xj)+vp(xj+1)<a.
Hence, we have
vp(xi)+vp(xi+1)+vp(xj)+vp(xj+1)<2a.
On the other hand, since (i,j),(i+1,j+1) are pairs of non-adjacent indices then
vp(xi)+vp(xj)≥a,vp(xi+1)+vp(xj+1)≥a.
This implies that
vp(xi)+vp(xi+1)+vp(xj)+vp(xj+1)≥2a,
which is a contradiction.
Continue, suppose that there exists an index i such that pi=pi+1=p. If vp(M)=1, because xixi+1 and xi+1xi+2 are not divisible by M, we can conclude that xi,xi+1,xi+2 are not divisible by p. Hence xixi+2 is not divisible by M, contradiction because xi,xi+2 are not adjacent.
So if pi=pi+1=p, then we must have vp(M)≥2.
Now we can conclude that the sequence p1,p2,…,pn has the following properties:
- Each prime pi∈N appears at most 2 times.
- If some prime pi∈N appears 2 times, then pi2∣M.
Hence, we have
p1p2…pn∣M.
Since M=25⋅32⋅5⋅7⋅13⋅31, we can see that n≤8 (in the sequence (pi), prime 2 appears 2 times, prime 3 appears 2 times and the rest appear 1 time). It is easy to check that if we choose 8 numbers as follows:
25M,2⋅3M,32M,3⋅5M,5⋅7M,7⋅13M,13⋅31M,31⋅2M
and the corresponding sequence is
p1=2, p2=3, p3=3, p4=5, p5=7, p6=13, p7=31, p8=2.
Therefore, the maximum value of n is 8. □