I found this question in a number theory book, I could not answer it, any help please;
Is it possible to place 1005 distinct positive integers around a circle so that for any two adjacent numbers, the ratio of the greater to the smaller is a prime number?
What if the integer 1005 is replaced with any other positive integer?
Best Answer
If the numbers $a_1,a_2,\ldots,a_n$ are placed in a circle, and if $r_i=a_{i+1}/a_i$, with $a_{n+1}=a_1$, then $r_1r_2\cdots r_n=1$. Now if each $r_i$ is either a prime or the reciprocal of a prime, then for each $r_i$ that is a prime there must be a corresponding $r_j$ that is the reciprocal of that prime. (More precisely, for each prime $p$, the number of indices for which $r_i=p$ must equal the number of indices for which $r_i=1/p$.) But this can only happen if $n$ is even. Since $1005$ is odd, it is not possible to place $1005$ integers in a circle so that for each pair of adjacent numbers the ratio of the larger to the smaller is prime.
Note, this argument is unconcerned with the condition that the $a_i$'s be distinct; that is, if $n$ is odd, there's no arrangement of numbers with prime ratios even if numbers are allowed to repeat. For $n=2m$, on the other hand, we can get distinct numbers by taking $p_1,p_2,\ldots,p_{m-1}$ to be distinct primes (say the first $m-1$ primes) and then letting
$$\begin{align} a_1&=1\\ a_{i+1}&=a_ip_i\quad\text{for }1\le i\le m-1\\ a_{i+1}&=a_i/p_{i-m+1}\quad\text{for }m\le i\le2m-1 \end{align}$$
e.g., $(a_1,\ldots,a_8)=(1,2,6,30,210,105,35,7)$.