First of all we will prove that the points $P_1, P_2, \dots, P_n$ are concyclic. Let $P_i$ have coordinates $(x_i, y_i)$ for $i = 1, 2, \dots, n$ and consider the point $O = (u, v)$ where $u = (x_1 + x_2 + \dots + x_n)/n$ and $v = (y_1 + y_2 + \dots + y_n)/n$. Then
$$\begin{aligned} OP_i^2 &= (u - x_i)^2 + (v - y_i)^2 = \left( \frac{x_1 + x_2 + \dots + x_n}{n} - x_i \right)^2 + \left( \frac{y_1 + y_2 + \dots + y_n}{n} - y_i \right)^2 \\ &= u^2 + v^2 + x_i^2 + y_i^2 - \frac{2}{n} \left( x_i(x_1 + x_2 + \dots + x_n) + y_i(y_1 + y_2 + \dots + y_n) \right) \end{aligned}$$
Since the sum $P_1P_i^2 + P_2P_i^2 + \dots + P_nP_i^2$ does not depend on $i$ and the sum
$$(x_i - x_1)^2 + (y_i - y_1)^2 + (x_i - x_2)^2 + (y_i - y_2)^2 + \dots + (x_i - x_n)^2 + (y_i - y_n)^2$$
also does not depend on $i$. Hence
$$n(x_i^2 + y_i^2) - 2x_i(x_1 + x_2 + \dots + x_n) - 2y_i((y_1 + y_2 + \dots + y_n) = n \cdot (OP_i^2 - u^2 - v^2)$$
does not depend on $i$. Thus $OP_i^2$ does not depend on $i$. Consequently $OP_1 = OP_2 = \dots = OP_n$ and hence the points $P_1, P_2, \dots, P_n$ lie on a circle with center $O$. W.l.o.g. we will assume that the points $P_1, P_2, \dots, P_n$ are placed on a circle in a clockwise order. Let the smallest positive integer in the sequence $P_1P_i, P_2P_i, \dots, P_nP_i$ be $a$ and let the second smallest one be $b$.

Now, consider three consecutive points on the circle $P_{i-1}, P_i, P_{i+1}$ and a point $P_k$ which is different from these three points. By Lemma 1, $\min\{P_{i-1}P_i, P_iP_{i+1}\} \le P_iP_k$ where $P_{n+1} = P_1$. Hence $\min\{P_{i-1}P_i, P_iP_{i+1}\} = a$ for all $i = 1, 2, \dots, n$. There are two cases: If $a = b$, then consider a point $P_i$. We know that either $P_{i-1}P_i = a$ or $P_iP_{i+1} = a$. W.l.o.g., assume that $P_{i-1}P_i = a$. Since $b = a$, there must be another point $P_k$ such that $P_iP_k = b = a$. We claim that $k = i + 1$. If not, consider the cyclic quadrilateral $P_{i-1}P_iP_{i+1}P_k$. Since $90^\circ > 90^\circ - \angle P_{i-1}P_iP_k/2 = \angle P_iP_{i-1}P_k = 180^\circ - \angle P_iP_{i+1}P_k$, we get that $\angle P_iP_{i+1}P_k > 90^\circ$ and hence $a = P_iP_k > P_iP_{i+1}$ which contradicts to the choice of $a$. Hence $k = i + 1$ and since this result is true for all $i$, we conclude that the $P_iP_{i+1} = a$ for all $i = 1, 2, \dots, n$ so these $n$ points form a regular $n$-gon.

If $a < b$, then exactly one of $P_{i-1}P_i$ and $P_iP_{i+1}$ is equal to $a$ and hence $n$ must be even and exactly $n/2$ of the sides of the $n$-gon $P_1P_2\dots P_n$ must be equal to $a$ and none of these sides are consecutive. We claim that all other $n/2$ sides must be equal to $b$. Consider the four consecutive points $P_{i-1}P_iP_{i+1}P_{i+2}$ such that $P_iP_{i+1} = a$. By Lemma 1 $\min\{P_{i-1}P_{i+1}, P_{i+1}P_{i+2}\} = b$ and similarly $\min\{P_{i-1}P_i, P_iP_{i+2}\} = b$. If $P_iP_{i-1} = P_{i-1}P_{i+1} = b$ or $P_iP_{i+2} = P_{i+2}P_{i+1} = b$ then we would obtain that $b < a$ which is a contradiction. Hence either $P_iP_{i-1} = P_{i+1}P_{i+2} = b$ or $P_iP_{i+2} = P_{i-1}P_{i+1} = b$ which shows that the quadrilateral $P_{i-1}P_iP_{i+1}P_{i+2}$ is a isosceles trapezoid and hence $P_{i-1}P_i = P_{i+1}P_{i+2}$. Thus, all other $n/2$ sides are equal to $b$.

greatest common divisor of all these distances is 1. Consider the cyclic quadrilaterals $A_1A_2A_{k+1}A_{k+2}$ and let $d_k = A_1A_{k+1}$. By Ptolemy Theorem, we have $d_k^2 = d_1^2 + d_{k-1}d_{k+1}$. If $d_1 > 1$ then let $p$ be a prime divisor of $d_1$. Since $d_2^2 = d_1^2 + d_1d_3$ we get that $p$ also divides $d_2$ and using the equations $d_k^2 = d_1^2 + d_{k-1}d_{k+1}$ we can inductively prove that $p$ divides all $d_i$'s which is a contradiction. Hence $d_1 = 1$ but in this case $A_1A_2 = A_2A_3 = 1$ and hence by triangle inequality, $d_2 = A_1A_3 < 1 + 1 = 2$ and hence $d_2 = 1$. On the other hand, $d_2^2 = d_1^2 + d_1d_3$ which is impossible since we would get that $d_3 = 0$. Done.

Now, if $a = b$, since we have a regular $n$-gon by Lemma 2 all possibilities are: $n = 1, 2, 3$. If $a < b$, since $n$ is even the side lengths are of the form $a, b, a, b, \dots, a, b$, the points with even (odd) indices form a regular $n/2$-gon and hence all possibilities are $n = 2, 4, 6$ again by Lemma 2. For $n = 4$, choose a rectangle with side lengths 3 and 4. For $n = 6$ choose a cyclic hexagon with consecutive side lengths 3, 5, 3, 5, 3, 5. In this case all diagonals are integers and for all $i$, the distances $P_iP_{i+1}, P_2P_{i+1}, \dots, P_6P_i$ forms the sequence 0, 3, 5, 7, 7, 8: