very beautiful problem (I couldn't solve it).

Okay, some thoughts I guess? So my current idea is strong induction on $k$. I don't know if this will work (probably there's going to be a counterexample..) For $k=3$, the solution is not very difficult. WLOG $A_1=(0,0)$, and set $A_2(x_1,y_1)$ and $A_3(x_2,y_2)$. Then we have $x^2_1+y^2_1, x^2_2+y^2_2, 2(x_1x_2+y_1y_2)$ as a multiple of $n$, so $x_1x_2+y_1y_2$ is a multiple of $n$ as well. Now since $(x^2_1+y^2_1)(x^2_2+y^2_2)=(x_1x_2+y_1y_2)^2+(x_1y_2-x_2y_1)^2$, we now see that $n^2|(x_1y_2-x_2y_1)^2$. This gives us $n|(x_1y_2-x_2y_1)= \pm 2S$. This concludes the proof for $k=3$. Now my idea for induction is this. Assume that the statement for $3 \le k \le t$. We show this for $k=t+1$. Start with a $t+1$-gon on a circle. If one of the main diagonals of this polygon has square of its length as a multiple of $n$, we can slice the polygon by that diagonal. Then we are left with two polygon with squares of all of its side lengths as a multiple of $n$, and the polygons have no more than $t$ vertices each. So if we denote the areas as $S_1, S_2$, we have $n|2S_1$ and $n|2S_2$, so $n|2S$ and we are happy. So for this induction to work, we need to prove that for every polygon that satisfies the condition, there is at least one main diagonal which has the square of its length as a multiple of $n$. Got any ideas? EDIT: Also, Ptolemy gives the solution when $n$ is a prime, or $n$ is square-free!

Can I ask one question? What do you mean by saying that Quote: An odd positive integer $n$ is given such that the squares of the side lengths of $P$ are integers divisible by $n$ Why are the squares integers?

mathprince2000 wrote: Can I ask one question? What do you mean by saying that Quote: An odd positive integer $n$ is given such that the squares of the side lengths of $P$ are integers divisible by $n$ Why are the squares integers? The side lengths of $P$ squared are integers divisible by $n$.

mathprince2000 wrote: Can I ask one question? What do you mean by saying that Quote: An odd positive integer $n$ is given such that the squares of the side lengths of $P$ are integers divisible by $n$ Why are the squares integers? Those points ($A_1,...,A_k$) have integer coordinates(look at the hypothesis) and you just have to apply the "distance between 2 points" formula: $\sqrt{(x-x')^2+(y-y')^2}$. After squaring this you'll get that it is an integer.

Here's an idea that seems to work (let me know if something goes wrong, it was hastily written in <10 mins) Step 0. Suffices to prove claim for $n = p^t$ where $p$ is an odd prime (for obvious reasons). Use induction on $k$, the number of vertices. Step 1 (Base case). Claim holds for a triangle. Proof: Put one of the vertices in $(0,0)$ and notice that $(x_1^2 + y_1^2)(x_2^2 + y_2^2) = (x_1 y_1 + x_2 y_2)^2 + (x_1 y_2 - x_2 y_1)^2$; the first two terms are divisible by $n^2$ and so is the last term, which is precisely $(2S)^2$. Step 2. We have that the circumcenter's coordinates are rational. (Trivial since the perpendicular bisectors can be written $ax+by+c=0$ where $a,b,c$ are integers). Step 2-2. We have either - $R^2$ is a rational number whose numerator is divisible by $n$ when written in lowest terms. - We can "cut" one vertex off and use induction. Proof: Let $x_1^2 + y_1^2 = A$, $x_2^2 + y_2^2 = B$, both of which are divisible by $n$. Also write $(x_1 - x_2)^2 + (y_1 - y_2)^2 = C$. Since $abc/4R = S$ for a triangle, we have $R^2 = \frac{ABC}{(x_1 y_2 - x_2 y_1)^2}$ Note that $(x_1 y_1 + x_2 y_2)^2 + (x_1 y_2 - x_2 y_1)^2 = AB$; play around with exponents (I think general claim holds for any odd $n$, but easier to use $p^k$) to see either - $v_p(x_1 y_2 - x_2 y_1) < t$ $\Rightarrow$ $R^2$ numerator is divisible by $n = p^k$ - $v_p(x_1 y_2 - x_2 y_1) \geq t$ $\Rightarrow$ $x_1 y_1 + x_2 y_2$ divisible by $n$, whence $C$ divisible by $n$, so we can cut $(0,0)$ off and apply induction (since both the cut off triangle area and the diagonal are divisible by $n$). Step 3. If $R^2$ numerator divisible by $n=p^t$, divide polygon into $n$ triangles using circumcircle and conquer. By step 1 (base case) after some scaling, each triangle has area whose numerator is divisible by $n$. Then the sum of $2S$ is also a fraction whose numerator is divisible by $n$, but it's an integer, so its an integer divisible by $n$.

The "vertex cutoff" part exists to work out the case where $p^k || A,B$ but $p^{k+1} | x_1 y_2 - x_2 y_1$. Not sure if this is actually possible..

Here's a solution. It's a bit technical, and I hope to see something better.

The correct thing to do is as done in this paper: http://arxiv.org/pdf/math/0407300v1.pdf . It shows a generalization of Brahmagupta + Heron's formula, i.e. the quantities $(16K^2, a_1^2, \dots, a_k^2)$ are related by a monic polynomial in $16K^2$, which is enough to finish as I described in lemma 2. I expected this to be true, but couldn't clear out the $r$ term.

Let us work in $\mathbb{Z}[i]$. Let the coordinates of the points $A_i$ be $z_i$ for $1 \le i \le k$. We note that it suffices to prove for odd prime power $n = p^e$ with $p \ge 3$. If $p = 4t+3$, then $p^e \mid \lvert z_i - z_{i+1} \rvert^2$ implies $p^f \mid z_i - z_{i+1}$ in $\mathbb{Z}[i]$ where $f = \lceil e/2 \rceil$. Then all the points $A_1, \dots, A_k$ are contained in a coset of $p^f \mathbb{Z}[i]$ and hence $2S$ is divisible by $p^{2f}$, which is again divisible by $p^e$. If $p = 4t+1$, let the factorization of $p$ in $\mathbb{Z}[i]$ be $p = q \bar{q}$. Note that for any $z \in \mathbb{Z}[i]$, its absolute value squared $\lvert z \rvert^2$ is divisible by $p^n$ if and only if there exists an $s$ such that $q^s \bar{q}^{n-s}$ divides $z$. We now claim the following: "There exists a triangulation of the polygon such that for each triangle, there is some $0 \le s \le e$ for which $q^s \bar{q}^{e-s}$ divides all the side vectors." To prove this, we use induction on $e$. Let us first look at the case where $e = 1$. Then every side is either a multiple of $q$ or a multiple of $\bar{q}$. If there exist two consecutive sides that are both multiples of $q$, then the triangle formed by those two sides will have sides that are all multiples of $q$. Hence we can cut out that triangle and obtain a smaller polygon whose sides are either multiples of $q$ or $\bar{q}$. This smaller polygon will be triangulated, because it is small. (We are implicitly using induction again on the number of sides.) Likewise, if two consecutive sides are both multiples of $\bar{q}$, then we are also done. Now suppose that there exist no pairs of consecutive sides that are both multiples of $q$ or both multiples of $\bar{q}$. Then multiples of $q$ and multiples of $\bar{q}$ will alternate, and hence the number of sides must be even. Let $k = 2l$, and suppose without loss of generality that $q \mid z_1 - z_2$. Because $z_1, \dots, z_{k} = z_{2l}$ lie on a circle, \[ \frac{(z_1 - z_2) (z_3 - z_4) \cdots (z_{2l-1} - z_{2l})}{(z_2 - z_3) \cdots (z_{2l} - z_1)} \]must be a real number, and hence \[ (z_1 - z_2) (z_3 - z_4) \cdots (z_{2l-1} - z_{2l}) (\bar{z}_2 - \bar{z}_3) \cdots (\bar{z}_{2l} - \bar{z}_1) = (\bar{z}_1 - \bar{z}_2) (\bar{z}_3 - \bar{z}_4) \cdots (\bar{z}_{2l-1} - \bar{z}_{2l}) (z_2 - z_3) … (z_{2l} - z_1) .\]The left hand side is a multiple of $q^{2l}$, while there right hand side is not a multiple of $q$, a contradiction. Let us now get to $e \ge 2$, assuming that the statement is true for $e-1$. Using the inductive hypothesis directly for $e - 1$, we see that there exists a triangulation such that all sides are multiples of some $q^s \bar{q}^{e-1-s}$. Suppose that the $s$’s are different for two triangles. We may assume that these two triangles share a side, because there is a path of triangles from one to the other. Let one triangle be a multiple of $q^{s_1} \bar{q}^{e-1-s_1}$ and the other triangle be a multiple of $q^{s_1} \bar{q}^{e-1-s_2}$, and let $s_1 < s_2$. The shared side must then be a multiple of $q^{s_2} \bar{q}^{e - 1 - s_1}$, and hence the square of its length must be a multiple of $p^{e - 1 - s_1 + s_2}$, which is divisible by $p^e$. This side must be a diagonal, and thus we can divide the whole polygon by this diagonal and obtain two smaller polygons. The “inductive hypothesis” for smaller polygons will then take care of these. On the other hand, what if all triangles have the same $s$? Then the whole polygon is a multiple of $q^s \bar{q}^{e-1-s}$ and thus we can divide the polygon $P$ by $q^s \bar{q}^{e-1-s}$ and get a polygon $P^\prime$ whose squares of sides are multiples of $p$. We can apply the statement for $e = 1$ and see that $P^\prime$ can be triangulated. After that, we can multiple the whole thing back to get a triangulation of $P$ such that each triangle is either a multiple of $q^s \bar{q}^{e-s}$ or a multiple of $q^{s+1} \bar{q}^{e-1-s}$. Hence this case is also covered. This finishes the proof of our claim. Going back to the problem, the polygon is partitioned into triangles that are multiples of $q^s \bar{q}^{e-s}$ for some $s$. The area of each of these triangles must be a multiple of $\lvert q^s \bar{q}^{e-s} \rvert^2 / 2 = p^e / 2$. Therefore $2S$ is a multiple of $p^e = n$.

mathocean97 wrote: Lemma 1: $n | r^2.$ Unless I'm asleep (likely considering the hour here), this lemma is not true. As a counterexample, the triangle with vertices $(19, 178)$, $(67, 166)$, $(109, 142)$ lies on the circle $x^2+y^2 = r^2 := 32045$, but all squares of side lengths are divisible by $9$ (because all the pairs are $(1,1)$ modulo $3$). Maybe it becomes true if you add the constraint that all pairs are distinct modulo $p^e$? This takes no cost anyways, since if two pairs coincide mod $p^e$ then the area is certainly $0$ mod that.

v_Enhance wrote: mathocean97 wrote: Lemma 1: $n | r^2.$ Unless I'm asleep (likely considering the hour here), this lemma is not true. As a counterexample, the triangle with vertices $(19, 178)$, $(67, 166)$, $(109, 142)$ lies on the circle $x^2+y^2 = r^2 := 32045$, but all squares of side lengths are divisible by $9$ (because all the pairs are $(1,1)$ modulo $3$). Maybe it becomes true if you add the constraint that all pairs are distinct modulo $p^e$? This takes no cost anyways, since if two pairs coincide mod $p^e$ then the area is certainly $0$ mod that. I think my calculations above imply that the only cases where things go wrong are $p=4k+3$ and pairs coincide mod $p^i$, and $x_i y_j - y_i x_j$ have a big factor of $p$. But if you want to deal with these nuances in this direction, it seemed like things do get messy when only some pairs coincide modulo $p^t (t \neq i)$.

drkim wrote: Let us work in $\mathbb{Z}[i]$. Let the coordinates of the points $A_i$ be $z_i$ for $1 \le i \le k$. We note that it suffices to prove for odd prime power $n = p^e$ with $p \ge 3$. If $p = 4t+3$, then $p^e \mid \lvert z_i - z_{i+1} \rvert^2$ implies $p^f \mid z_i - z_{i+1}$ in $\mathbb{Z}[i]$ where $f = \lceil e/2 \rceil$. Then all the points $A_1, \dots, A_k$ are contained in a coset of $p^f \mathbb{Z}[i]$ and hence $2S$ is divisible by $p^{2f}$, which is again divisible by $p^e$. If $p = 4t+1$, let the factorization of $p$ in $\mathbb{Z}[i]$ be $p = q \bar{q}$. Denote by $\nu_q(x)$ and $\nu_{\bar{q}}(x)$ the exponent of $q$ and $\bar{q}$ in the prime factorization of $x$ respectively. Since $p^e \mid \lvert z_i - z_{i+1} \rvert^2$, we have $\nu_q( z_i - z_{i+1}) + \nu_{\bar{q}}(z_i - z_{i+1}) \ge e$ for all $1 \le i \le k$. We now claim the following: “There is a triangulation of the polygon such that for each triangle, there is some $0 \le s \le e$ for which $q^s \bar{q}^{e-s}$ divides all the side vectors.” To prove this, we use induction on $e$. Let us first look at the case where $e = 1$. Then every side is either a multiple of $q$ or a multiple of $\bar{q}$. If there exist two consecutive sides that are both multiples of $q$, then the triangle formed by those two sides will have sides that are all multiples of $q$. Hence we can cut out that triangle and obtain a smaller polygon whose sides are either multiples of $q$ or $\bar{q}$. This smaller polygon will be triangulated, because it is small. (We are implicitly using induction again on the number of sides.) Likewise, if two consecutive sides are both multiples of $\bar{q}$, then we are also done. Now suppose that there exist no pairs of consecutive sides that are both multiples of $q$ or both multiples of $\bar{q}$. Then multiples of $q$ and multiples of $\bar{q}$ will alternate, and hence the number of sides must be even. Let $k = 2l$, and suppose without loss of generality that $q \mid z_1 - z_2$. Because $z_1, \dots, z_{k} = z_{2l}$ lie on a circle, we see that \[ \frac{(z_1 - z_2) (z_3 - z_4) \cdots (z_{2l-1} - z_{2l})}{(z_2 - z_3) \cdots (z_{2l} - z_1)} \]must be a real number, and hence \[ (z_1 - z_2) (z_3 - z_4) \cdots (z_{2l-1} - z_{2l}) (\bar{z}_2 - \bar{z}_3) \cdots (\bar{z}_{2l} - \bar{z}_1) = (\bar{z}_1 - \bar{z}_2) (\bar{z}_3 - \bar{z}_4) \cdots (\bar{z}_{2l-1} - \bar{z}_{2l}) (z_2 - z_3) … (z_{2l} - z_1) .\]The left hand side is a multiple of $q^{2l}$, while there right hand side is not a multiple of $q$. A contradiction. Let us now get to $e \ge 2$, assuming that the statement is true for $e-1$. Using the inductive hypothesis directly for $e - 1$, we see that there exists a triangulation such that all sides are multiples of some $q^s \bar{q}^{e-1-s}$. Suppose that the $s$’s are different for two triangles. We may assume that these two triangles share a side, because there is a path of triangles from one to the other. Let one triangle be a multiple of $q^{s_1} \bar{q}^{e-1-s_1}$ and the other triangle be a multiple of $q^{s_1} \bar{q}^{e-1-s_2}$, and let $s_1 < s_2$. The shared side must then be a multiple of $q^{s_2} \bar{q}^{e - 1 - s_1}$, and hence the square of its length must be a multiple of $p^{e - 1 - s_1 + s_2}$, which is divisible by $p^e$. This side must be a diagonal, and thus we can divide the whole polygon by this diagonal and obtain two smaller polygons. The “inductive hypothesis” for smaller polygons will then take care of these. On the other hand, what if all triangles have the same $s$? Then the whole polygon is a multiple of $q^s \bar{q}^{e-1-s}$ and thus we can divide the polygon $P$ by $q^s \bar{q}^{e-1-s}$ and get a polygon $P^\prime$ whose squares of sides are multiples of $p$. We can apply the statement for $e = 1$ and see that $P^\prime$ can be triangulated. After that, we can multiple the whole thing back to get a triangulation of $P$ such that each triangle is either a multiple of $q^s \bar{q}^{e-s}$ or a multiple of $q^{s+1} \bar{q}^{e-1-s}$. Hence this case is also covered. This finishes the proof of our claim. Going back to the problem, we see that the polygon is partitioned into triangles that are multiples of $q^s \bar{q}^{e-s}$ for some $s$. The area of each of these triangles must be a multiple of $\lvert q^s \bar{q}^{e-s} \rvert^2 / 2 = p^e / 2$. Therefore $2S$ is a multiple of $p^e = n$. Fantastic solution!

qwerty414 wrote: I think my calculations above imply that the only cases where things go wrong are $p=4k+3$ and pairs coincide mod $p^i$, and $x_i y_j - y_i x_j$ have a big factor of $p$. But if you want to deal with these nuances in this direction, it seemed like things do get messy when only some pairs coincide modulo $p^t (t \neq i)$. For a counterexample with $n=5$ there is also $(93, 478)$, $(258, 413)$, $(413, 258)$, which lies on $x^2+y^2=237133$. EDIT: Right, so let me write up what I have for the case where $n = p$ a prime (and thus for $n$ square-free). I don't know how to extend it to prime powers, and I suspect that it's not easy. First, the circumcenter $O$ has rational coordinates, so by scaling and translation assume its the origin. Let $A_i = (x_i, y_i)$ and $R$ the circumradius. From the fact that $n$ divides $(x_i-y_i)^2 + (x_{i+1}-y_{i+1})^2$ we derive \[ R^2 \equiv x_i^2 + y_i^2 \equiv x_ix_{i+1} + y_iy_{i+1} \pmod p \qquad \forall i. \] For convenience, call a pair $(x,y)$ nonzero if $x \neq 0$ or $y \neq 0$. Now, we consider two cases. First $R^2 \not\equiv 0 \pmod p$. Suppose $(a,b)$ and $(x,y)$ are adjacent vertices. We claim they're equal mod $p$. Check that \[ a^2R^2 \equiv (R^2-by)^2 + a^2y^2 \implies R^2(y-b)^2 \equiv 0; \]hence $y \equiv b$ and similarly $x \equiv a$. Thus all vertices coincide modulo $p$ in this case and we're done. If $R^2 \equiv 0 \pmod p$, we can assume $p \equiv 1 \pmod 4$ since otherwise all vertices are zero. So assert $p \equiv 1 \pmod 4$ and fix $c = \sqrt{-1} \pmod p$. Then every nonzero vertex has $x = \pm cy$, so call it positive or negative for signs $+$ and $-$ respectively. It's easy to see adjacent nonzero vertices are either both positive or both negative. Thus the original polygon can be triangulated into triangles such that no triangle has both positive and negative vertices; in each case the area of the triangle vanishes modulo $p$.

v_Enhance wrote: For a counterexample with $n=5$ there is also $(93, 478)$, $(258, 413)$, $(413, 258)$, which lies on $x^2+y^2=237133$. I guess things just generally go badly wrong when the area has large factors of $p$..which should have been obvious in light of $abc/4S = R$ :/

Firstly, the square of any side lengths and diagonals is an integer. We only need to show when $n=p^e$ for some natural $e$ and odd prime $p$. The case $k=3$ can be easily done by Heron's. We shall induct on $k$. It suffices to show there exists a diagonal whose square is divisible by $n$, since we can divide $P$ into 2 smaller polygons by cutting along that diagonal and we are done by induction. We shall make use of the following "well-known" fact: If $a_1,\ldots,a_n$ are integers such that $\sum \sqrt{a_i}\in\mathbb{Z}$, then $\sqrt{a_i}\in\mathbb{Z}$ for all $i$. (See https://qchu.wordpress.com/2009/07/02/square-roots-have-no-unexpected-linear-relationships/) Lemma 1: If $a_1,\ldots,a_n,b\in\mathbb{Q}$ such that $\sum\sqrt{a_i}=\sqrt{b}$, then $v_p(b)\geq k=\min\{v_p(a_i)\}$ for any odd prime $p$. ($v_p(x)$ is the integer $k$ such that $xp^{-k}=\frac{u}{v}$ where $u,v$ are integers coprime to $p$) Proof: We can multiply their denominators so WLOG assume $a_1,\ldots,b\in\mathbb{Z}$. Then squaring both sides gives $\sum{a_i}+2\sum{\sqrt{a_ia_j}}=b$. Since $2\sum{\sqrt{a_ia_j}}$ is an integer, we must have $\sqrt{a_ia_j}\in\mathbb{Z}$ so $v_p(\sqrt{a_ia_j})\geq k$ for all $i\neq j$. Thus $v_p(b)=v_p(LHS)\geq k$. Now back to the question. As per IMO tradition, we shall invert this Q3. Inverting at $A_1$ with radius 1, we get $A_2',\ldots,A_k'$ are collinear. So by triangle (polygon?) equality $A_2'A_3'+A_3'A_4'+\cdots+A_{k-1}'A_k'=A_2'A_k'$. Let $a_i=A_iA_{i+1}^2, b_i=A_1A_i^2, c=A_2A_k^2$. Then our triangle equality becomes $\sqrt{\frac{a_2}{a_1b_3}}+\sqrt{\frac{a_3}{b_3b_4}}+\cdots+\sqrt{\frac{a_{k-2}}{b_{k-2}b_{k-1}}}+\sqrt{\frac{a_{k-1}}{b_{k-1}a_k}}=\sqrt{\frac{c}{a_1a_k}}$. Assuming $v_p(b_i),v_p(c)<e$, note that the $v_p$ of every term on the LHS is strictly greater than the RHS, a contradiction. Hence we are done.

Is the condition that $n$ is odd essential? It looks that if all squares of sides are divisible by $2^k$, then $2S$ is also divisible by $2^k$, and we do not even need for this that the polygon is cyclic. Proof: consider the smallest $k$ for which a counterexample exists, of course $k>0$. Since all squares of side lengths are even, all vertices belong to a white or black sublattice, if we consider the chess color of all integer points. Considering only this sublattice and scaling we get a counterexample for $k-1$. A contradiction.

Yay my first post The following is a solution from one of my friends Chiang Hung, and I will post my own solution later. Let $P=A_1...A_k$ be a convex polygon in the plane. The vertices $A_1,...,A_k$ have integral coordinates and lie on a circle. Let $S$ be the area $P$. An odd integer $n$ is giver such that the squares of side lengths of $P$ are integers divisible by $n$. Prove that $2S$ is an integer divisible by $n$. Let The vertices $A_1,...,A_k$ lie on circle $O$ with radius $r$, we may assume 1. $O=0.$ Since the vertices of $\triangle A_1A_2A_3$ have integral coordinates, $O$ has rational coordinates. Suppose $O=O'/2^rT$ for some $r\in\mathbb{N}_0$, odd $T$, and integral point $O'$. It suffices to prove the case $A_i'=2^rT(A_i-O)$, $n'=T^2n$. 2. The plane is $\mathbb{C}$, and $n=gcd(|w_i|^2)$. Denote $A_{k+1}=A_1$, $A_{i+1}-A_i=w_i$. By surveyor formula, $2S$ is a integer. Suppose $v_p(n)=a>0$. 1. $p=4k+3$. Then $a$ is even and $p^b|w_i$ for all $i$ where $2b=a$. So all $P's$ diagonal have length divisible by $p^b$. Heron's formula gives $p^a|2S$. 2. $p=4k+1$. Choose a prime number in $\mathbb{Z}[i]$, $\zeta$, such that $\zeta\bar{\zeta}=p$. 1) Not all $w_i's$ are divisible by $p$. WLOG $\zeta^a|w_1$ but $w_1$ is not divisible by $\bar{\zeta}$. The equation $|A_1|=|A_2|$ gives $w_1\bar{w_1}+A_1\bar{w_1}+\bar{A_1}w_1=0$. That is, $\zeta^a|A_1$. We have $p^a|r^2$. This case is easy. 2) All $w_i's$ are divisible by $p$. i. All $w_i^2$'s are divisible by $p^a$, so $a=2b$ and $p^b|w_i$ for all $i$. This case is done by Heron's formula. ii/ There exists $w_i$ such that $w_i^2$ is not divisible by $p^a$. Then WLOG $i=1$ and $w_1=p^c\zeta^d\eta$ where $\eta\in\mathbb{Z}[i]$ and $(p,\eta)=1$. The equation $w_1\bar{w_1}+A_1\bar{w_1}+\bar{A_1}w_1=0$ gives $\zeta|A_1$, and hence $\zeta|A_i$ for all $i$. It reduces to the case $A_i'=A_i/\zeta$, $n'=n/p$. Either The process can be continued or this case is done. The process can be repeated at most $a$ times. And here is mine, I wish it was correct OwO: We abandon the restriction that $A_i$ is on the lattice, and we claim that the problem remains true if $2S(A_iA_jA_k)\in \mathbb{Z}$ and $\overline{A_iA_j}^2\in \mathbb{Z}$ for all $i,j,k$. k=3 is just Heron's formula, and it suffices to prove the case $n=p^r$. For $n=p$, we consider the quadrilateral $A_{i-1}A_iA_{i+1}A_j$, by using Ptolemy, $\overline{A_{i-1}A_{i+1}}^2\times \overline{A_iA_j}^2=(\overline{A_{i-1}A_j}\times \overline{A_iA_{i+1}}+\overline{A_{i+1}A_j}\times \overline{A_iA_{i-1}})^2=p\times$ (an algebraic integer)$\in \mathbb{Z}$, so we have either $\overline{A_{i-1}A_{i+1}}^2$ or $\overline{A_iA_j}^2$ is divisible by $p$ , so we can do induction. For $n=p^r$, similarly we have either $\overline{A_{i-1}A_{i+1}}^2$ is divisible by $p^r$ or $\overline{A_iA_j}^2$ is divisible by $p$, the former case is by induction too, so if $\overline{A_{i-1}A_{i+1}}^2$ is not a multiplier of $p^r$ for all $i$, then $\overline{A_iA_j}^2$ is divisible by $p$ for all $i,j$. So we can scale the polygon by $1/\sqrt{p}$ times to get a new polygon, it reduces to the case $n_{now}=p^{r-1}, 2S(A_iA_jA_k)_{now}=2S(A_iA_jA_k)/p$ (which is an integer, by using the case $n=p$).

Using Pick's theorem to prove that $2S$ is an integer won't be worth any points, or will it? If there is a prime of the form $p=4k+3$ that divides $n$, we can translate one of the vertices to $(0,0)$ and that divide everything by $p$. I don't know about the other case though.

Here's a solution for $n=p$ where $p$ is a prime. Assume that the centre of the circle is the origin. Let $A_j=(x_j,y_j)$ and $r$ be the radius of the circle. By the Shoelace Theorem we have \begin{align*} 2S &=\sum\left(x_iy_{i+1}-x_{i+1}y_i\right). \end{align*}Notice that $(x_{i+1}-x_i)^2+(y_{i+1}-y_{i})^2\equiv r^2-x_ix_{i+1}-y_iy_{i+1}\equiv{0}\pmod{n}$. By Lagrange's identity we have \begin{align*} (x_i^2+y_i^2)(x_{i+1}^2+y_{i+1}^2) &=(x_ix_{i+1}+y_iy_{i+1})^2+(x_iy_{i+1}-x_{i+1}y_i)^2 \\ \Leftrightarrow (r^2-x_ix_{i+1}-y_iy_{i+1})(r^2+x_ix_{i+1}+y_iy_{i+1}) &=(x_iy_{i+1}-x_{i+1}y_i)^2. \end{align*}Hence we have $(x_iy_{i+1}-x_{i+1}y_i)^2\equiv{0}\pmod{n}$ and since $n$ is prime, the result follows. Also if $r^2\equiv{0}\pmod{n}$ then it is true for any given $n$. So it only remains to show for the case $r^2\not\equiv{0}\pmod{n}$.

Clearly $2S$ is an integer by Shoelace. The center of the circle is a rational $(x,y)/d$. Translate so that this is the origin and scale up by $d$. This scales up the squares of the side lengths by $d^2$ (and so replace $n$ with $ne^2$ where $e$ is the odd part of $d$) and the area by $d^2$ too, so the problem is true originally if and only if it is true now. By Chinese Remainder, it suffices to check the case where $n$ is a prime power, say $n = p^\ell$. The $k = 3$ case is trivial since $K^2 = 2a^2b^2 + 2b^2c^2 + 2c^2a^2 - a^4 - b^4 - c^4$ so $p^{2\ell}\mid K^2$ and $p^\ell\mid K$. Now assume that $A_i$ is $(x_i, y_i)$, and $x_i^2 + y_i^2 = R$ for all $i$. Let $m = \nu_p(R)$. First, note that if $p\mid x_i, y_i$ for all $i$, then we can scale the problem down by a factor of $p$ and finish. Assume otherwise, and WLOG $p\nmid x_1$; else cyclically shift the labels so that $p\nmid$ one of $x_1, y_1$, and then reflect over $y=x$. Let $a_i = x_i - x_{i-1}$, $b_i = y_i - y_{i-1}$. We have \[ (x_1+a_2)^2 + (y_1+b_2)^2 \equiv x_1^2 + y_1^2 \equiv R\pmod {p^k}, \]so since $p^k\mid a_2^2 + b_2^2$ and $p$ is odd, $p^k\mid x_1a_2 + y_1b_2$. Similarly, $(x_1-a_1)^2 + (y_1-b_1)^2 \equiv x_1^2 + y_1^2\pmod {p^k}$, so $p^k\mid x_1a_1 + y_1b_1$. In particular, this yields \[ x_1^2a_2^2 \equiv y_1^2b_2^2, \, x_1^2a_1^2 \equiv y_1^2b_1^2 \pmod{p^k}. \]Then \[ 0\equiv x_1^2a_2^2 + x_1^2b_2^2 \equiv (x_1^2+y_1^2)b_2^2\pmod {p^k}, \]so if $t = \left\lceil \frac{\ell-m}{2}\right\rceil$, then $p^t\mid b_2$. Similarly, $p^t\mid a_2, a_1, b_1$. Now, we claim that $p^\ell\mid A_kA_2^2$, which will finish since we can just apply induction on $A_kA_1A_2$ and $A_2A_3\cdots A_k$. Indeed, \[ A_kA_2^2 \equiv (a_1+a_2)^2 + (b_1+b_2)^2\pmod {p^k}. \]Since $p\nmid x_1$, this is zero if and only if $p^k$ divides \[ (x_1a_1+x_1a_2)^2 + (x_1b_1+x_1b_2)^2. \]But \[ (x_1a_1+x_1a_2)^2 + (x_1b_1+x_1b_2)^2\equiv (-y_1b_1-y_1b_2)^2 + (x_1b_1+x_1b_2)^2 \equiv R(b_1+b_2)^2. \]Since $p^t\mid b_1+b_2$ and $p^m\mid R$,then \[ p^{2t+m}\mid A_kA_2^2, \]so $p^\ell\mid A_kA_2^2$ indeed.

Here's a different solution using $\mathbb{Z}[i]$. Note that it suffices to prove that odd prime powers work; especially integers of the form $p^m$, where $p \equiv 1 \pmod 4$ work. We induct on $k$. For $k=3$, Heron's formula kills the problem. Now let us move to the inductive step. For a polygon $P$, let its side vectors be $\{ \overrightarrow{A_1A_2}, \overrightarrow{A_2A_3}, \cdots, \overrightarrow{A_kA_1} \}=\{ v_1, v_2, \cdots, v_n\}$. We consider vectors as complex numbers on $\mathbb{Z}[i]$. Assume that $p=\pi \bar{\pi}$ on $\mathbb{Z}[i]$. Let $m_i$ be the maximal integer such that $\pi^{m_i}$ divides $v_i$. Since $p^m$ divides $v_i \overline{v_i}$, either $m_i \ge m$, or $\pi^{m_i} \overline{\pi}^{m-m_i}$ divides $v_i$. Consider $\chi=\min_{i} m_i$. Taking $\pmod {\pi^\chi}$ on each sides of $0=v_1+v_2+\cdots +v_n$, we deduce that there are at least $2$ indices $t$ such that $\chi=m_t$. Call these indices $a,b$. Note that for any permutation $\sigma$ of $\{v_1, v_2, \cdots , v_n\}$, every polygon $Q$ having $\sigma$ as its side vectors is inscribed in a circle, and has exactly same area with $P$. Hence, if we switch $v_a$ and $v_b$, then the new polygon obtained has same area as $P$. So, WLOG assume that $b=a+1$. Then, since $m_a=m_b$, $$\overline{A_aA_{a+2}}^2=(v_a+v_b)(\overline{v_a}+\overline{v_b})$$is a multiple of $p^m$. Hence, from the induction hypothesis on polygons $A_1A_2\cdots A_aA_{a+2} \cdots A_k$ and $A_aA_{a+1}A_{a+2}$, $2S$ is a integer divisible by $p^m$. $\square$

Solved with eisirrational, goodbear, Th3Numb3rThr33. Induct on $k$: first we settle the base case $k=3$. Let $A_i=(x_i,y_i)$, and shift $A_1$ to the origin. Then by shoelace formula, $2S=x_2y_3-x_3y_2$. We are given \begin{align*} 0&\equiv(x_2-x_3)^2+(y_2-y_3)^2\\ &\equiv\left(x_2^2+y_2^2\right)+\left(x_3^2+y_3^2\right)-2(x_2x_3+y_2y_3)\\ &\equiv-2(x_2x_3+y_2y_3)\pmod n. \end{align*}Since $n$ is odd, $n\mid T:=x_2x_3+y_2y_3$. But $n^2\mid\left(x_2^2+y_2^2\right)\left(x_3^2+y_3^2\right)=T^2+4S^2$, so $n\mid2S$, as required. If $n$ is divisible by at least two distinct primes, then the inductive step follows from Chinese Remainder theorem. Henceforth $n=p^e$, where $p$ is prime. I claim for $k\ge4$, there is a diagonal whose length squared is divisible by $p^e$. Then this diagonal dissects $P$ into two polygons with fewer sides, so we are done by strong induction. Select $m$ so that $3\le m\le k-1$ and $\nu_p(A_1A_{m-1}^2)\ge\nu_p(A_1A_m^2)\le\nu_p(A_1A_{m+1}^2)$. If this is not possible, then either $2e\le\nu_p(A_1A_2^2)\le\nu_p(A_1A_3^2)$ or $\nu_p(A_1A_3^2)>\nu_p(A_1A_4^2)>\cdots>\nu_p(A_1A_k^2)\ge2e$. In either case, $n\mid A_1A_3^2$, and we are already done. Let $A$ denote the set of algebraic integers. Let $E=e+\nu_p\left(A_1A_m^2\right)$, so $\nu_p\left(A_1A_{m-1}^2\cdot A_mA_{m+1}^2\right)\ge E$ and $\nu_p\left(A_1A_{m+1}^2\cdot A_mA_{m-1}^2\right)\ge E$. By Ptolemy's theorem on $A_1A_{m-1}A_mA_{m+1}$, we have \[\sqrt{\frac{A_1A_m^2\cdot A_{m-1}A_{m+1}^2}{p^E}}=\sqrt{\frac{A_1A_{m-1}^2\cdot A_mA_{m+1}^2}{p^E}}+\sqrt{\frac{A_1A_{m+1}^2\cdot A_mA_{m-1}^2}{p^E}}\in A,\]so $p^E\mid A_1A_m^2\cdot A_{m-1}A_{m+1}^2$. It follows that $p^e\mid A_{m-1}A_{m+1}^2$, and the induction is complete.

First, note that it suffices to prove the problem for $n=p^e$, where $p$ is a prime and $e\ge 1$. Now, we will induct on $k$ with base case $3$. For $k=3$, note that by law of cosines we have $A_2A_3^2=A_1A_2^2+A_1A_3^2-2A_1A_2\cdot A_1A_3\cos\angle A_2A_1A_3$. Thus, we have that $\nu_p(A_1A_2\cdot A_1A_3\cos\angle A_2A_1A_3)\ge e$. So, $$\nu_p[A_1A_2A_3]=\nu_p\left(\frac{1}{2}A_1A_2\cdot A_1A_3\sin\angle A_2A_1A_3\right)=\nu_p\left(\frac{1}{2}A_1A_2\cdot A_1A_3\cos\angle A_2A_1A_3\right)\ge e$$as desired, since $\sin$ and $\cos$ have the same integer denominator. Now, for the inductive step, note that as long as there exists a diagonal whose square is divisible by $n$, we are done, since this diagonal splits our $k$-gon into 2 smaller cases which can both be finished by inductive hypothesis. To show that there always exists such a diagonal, we assume the contrary, namely that if $A_iA_j$ is not a side, then $\nu_p(A_iA_j^2)\le e$. Denote $\nu_p(A_iA_{i+1}^2)$ as $v_i$, and $\nu_p(R^2)$ as $v_R$, where $R$ is the circumradius.We know from Law of Sines that $$\frac{A_iA_{i+1}}{2\sin\angle A_iA_{i+2}A_{i+1}}=R\implies \nu_p(\cos^2\angle A_iA_{i+2}A_{i+1})=v_i-v_R$$Now, consider Law of Cosines with $\angle A_iA_{i+2}A_{i+1}$. We have $$A_iA_{i+1}^2=A_iA_{i+2}^2+A_{i+1}A_{i+2}^2-2A_iA_{i+2}\cdot A_{i+1}A_{i+2}\cos\angle A_iA_{i+2}A_{i+1}$$By assumption, $\nu_p(A_iA_{i+2})^2<\nu_p(A_{i+1}A_{i+2}^2),\nu_p(A_iA_{i+1})$, so the only way for this equality to hold is if $$\nu_p(A_iA_{i+2}^2)=\nu_p((A_{i+1}A_{i+2}\cos\angle A_iA_{i+2}A_{i+1})^2)=v_i+v_{i+1}-v_R$$ We now prove with induction that $\nu_p(A_iA_j^2)=v_i+v_{i+1}+\ldots+v_{j-1}-(j-i-1)v_R$. We have just done the base case, so assume that this is true for $j-i<d$, and consider when $j=i+d$. In particular, consider the quadrilateral $A_iA_{j-2}A_{j-1}A_j$. By Ptolemy, we need that $$A_iA_{j-2}\cdot A_{j-1}A_{j-2}+A_{j-2}A_{j-1}\cdot A_jA_i=A_iA_{j-1}\cdot A_{j-2}A_j$$By inductive hypothesis, $$\nu_p(RHS^2)=(v_i+\ldots +v_{j-2})+(v_{j-2}+v_{j-1})-(j-i-1)v_R$$and $\nu_p$ of the square of the first term on the left is $$v^*=(v_i+\ldots +v_{j-3})+v_{j-1}-(j-i-3)v_R$$If $v^*\le \nu_p(RHS^2)$, then $v_{j-2}\ge v_R$. However, this would mean $\nu_p(A_{j-2}A_j^2)\ge v_{j-1}\ge e$, which is a contradiction. So, $v^*>\nu_p(RHS^2)$ Hence, in order to get the desired equality, we must have $\nu_p(A_{j-2}A_{j-1}\cdot A_jA_i)=\nu_p(RHS)$, which quickly implies the result. So, the induction is complete. Note that, with this induction, we can go all the way to $j=i+k-1$. So, $v_{i-1}=v_i+v_{i+1}+\ldots+v_{j-1}-(j-i-1)v_R$. From similar relations, it is easy to get that the average of all the $v_i$ is $v_R$. However, this means that we have $i$ such that $v_i\ge v_R$, which, as we have shown above, leads to a contradiction. Hence, our assumption was wrong and we can always find a diagonal to split our $k$ gon into smaller cases, as desired.

What a fantastic problem - there seems to be a myriad of different approaches. Here is a solution which seems to be essentially different from all of the above. I left out the the somewhat boring calculations to highlight the important ideas of the proof. Step 0: Let the vertices have coordinates $(x_1, y_1), \ldots , (x_k, y_k)$. A well-known formula gives \begin{align*} 2S = \sum_{j = 1}^k x_{j+1}y_j - y_{j+1}x_j. \end{align*}(We use cyclic indices.) Step 1: Suffices to show for $n$ a prime power $p^m$ with $p$ odd. The case $p \equiv 3 \pmod{4}$ is easy, as then all $x_{j+1} - x_j$ and $y_{j+1} - y_j$ are divisible by $p$, and we may descent. Assume $p \equiv 1 \pmod{4}$ from now on. Step 2 (Main idea 1): By Hensel's lemma, the equation $x^2 \equiv -1 \pmod{p^m}$ has non-congruent two solutions. Let them be $i$ and $-i$. The condition on the squares of lengths being divisible by $p^m$ give \begin{align*} y_{j+1} - y_j \equiv \pm i (x_{j+1} - x_j) \pmod{p^m} \ \ \ \ \ \ (*) \end{align*}for all $j$ for some sign choice $\pm$ (which may depend on $j$). Step 3: Settle the case $k = 3$ by showing that the sign choices above are the same for all $j = 1, 2, 3$. This is easy algebra. Step 4: Perform induction. Aim to show that $(x_{j+2} - x_j)^2 + (y_{j+2} - y_j)^2 \equiv 0 \pmod{p^m}$ for some $j$, so that we may reduce to a $k-1$-gon and a triangle. This is possible if (*) holds with the same choice of sign $\pm$ for two consecutive values of $j$. (In particular, we are done with the induction step if $k$ is odd.) Assume not, so the sign (*) depends on the parity of $j$ only.

Step 6: Shift so we may assume $x, y \equiv 0 \pmod{p^m}$. We thus have equations \begin{align*} x_j^2 + y_j^2 \equiv c \pmod{p^m} \ \ \ \ (1) \end{align*}(by above), \begin{align*} (x_{j+1} - x_j)^2 + (y_{j+1} - y_j)^2 \equiv 0 \pmod{p^m} \ \ \ \ (2) \end{align*}(by the assumption) and \begin{align*} \frac{y_{j+1} - y_j}{x_{j+1} - x_j} \equiv - \frac{y_j - y_{j-1}}{x_j - x_{j-1}} \pmod{p^m} \ \ \ \ (3) \end{align*}(by step 4). A bit of algebraic manipulation yields $y_{j+1}x_{j-1} \equiv x_{j+1}y_{j-1} \pmod{p^m}$, i.e. that $y_j/x_j$ depends only on the parity of $j$, so that modulo $p^m$ the points $(x_j, y_j)$ lie on two lines. Let these two lines be $y \equiv ax \pmod{p^m}$ for $j$ even and $y \equiv bx \pmod{p^m}$ for $j$ odd.

Thus $x_jx_{j+1}$ is constant $C \pmod{p^m}$. Finally, plugging this in gives \begin{align*} 2S = \sum_{j=1}^k x_{j+1}y_j - y_{j+1}x_j\equiv \pm(a-b) \sum_{j=1}^k (-1)^jC \equiv 0 \pmod{p^m}, \end{align*}as desired.

Great problem, not at all what you'd expect in a number theory problem. I think the idea of recursively generating diagonal lengths is is the easiest way to motivate the use of Ptolemy:

We prove for $n=p^{e}$ for a prime $p$ with induction on $k \ge 3.$ If $k=3,$ set $A_1=(0,0),$ $A_2=(x_1,y_1),$ and $A_3=(x_2,y_2)$ WLOG. So $x_1^2+y_1^2 \equiv x_2^2+y_2^2 \equiv 0 \pmod{n}$ and $ 0 \equiv (x_1-x_2)^2+(y_1-y_2)^2 \equiv -2x_1x_2-2y_1y_2 \pmod{n}.$ So $x_1x_2+y_1y_2\equiv 0 \pmod{n}.$ So $(x_1y_2-x_2y_1)^2 \equiv (x_1^2+y_1^2)(x_2^2+y_2^2)-(x_1x_2+y_1y_2)^2 \equiv 0 \pmod{n^2}$ which finishes by Shoelace. $\square$ If $k \ge 4,$ if we have a $3 \le j \le k-1$ where $p^e \mid A_1A_{j}^2$ we split the polygon in two and induct down. Otherwise we must have three consecutive vertices $A_{m-1}, A_{m}, A_{m+1} \ne A_{1}$ where $v_p( A_1A_{m-1}^2) \ge v_p( A_1A_{m}^2) \le v_p( A_1A_{m+1}^2).$ Ptolemy's on $A_1A_{m-1}A_{m}A_{m+1}$ gives that $p^e \mid A_{m-1}A_{m+1}^2$ so we split the polygon in two that way and induct down. $\blacksquare$

Define $p_i=|A_iA_{i+1}|,$ $q_i=|A_1A_i|,$ $r_i=|A_{i-1}A_{i+1}|$ with cyclic numeration. By the Pick's theorem $2S$ is an integer. Notice that it's enough to consider case $n=p^{\alpha}$ for some odd prime $p$ and nonnegative integer $\alpha.$ Induct on $k\geq 3.$ For base case $k=3$ we use Heron's formula, which gives $$n^2\mid (-p_1^4-p_2^4-p_3^4+2p_1^2p_2^2+2p_2^2p_3^2+2p_3^2p_1^2)=16S^2\implies n\mid 2S\text{ } \Box$$ If $p^{\alpha}$ divides the squared length of some diagonal of $P,$ then we can divide $P$ on two polygons by this diagonal and induct down. Thus we may assume the opposite. Since $v_p(q_2^2),v_p(q_n^2)\geq \alpha,$ there exists such integer $m,$ that $$v_p(q_{m-1}^2),v_p(q_{m+1}^2)\geq v_p(q_m^2)\quad \quad \quad v_p(q_m^2)<\alpha.$$On the other hand, by Prolemy's theorem $$(q_mr_m)^2=(p_{m-1}q_{m+1})^2+(p_{m+1}q_{m-1})^2+2p_{m-1}p_{m+1}q_{m-1}q_{m+1}.$$Clearly LHS is an integer, so we easily conclude that $p^{\alpha +\min (v_p(q_{m-1}^2), v_p(q_{m+1}^2))}\mid (q_mr_m)^2\implies p^{\alpha} \mid r_m^2,$ contradiction.

Didn't find this too bad for 3/6: the Ptolemy solution is the only way you can really deal with the cyclic condition in an all-encompassing way, and the rest is fairly natural. We induct on $k$, and consider only the case $n = p^r$ for some odd prime $p$. Note that for the case $k=3$, we have $$n^2 \mid 2(a^2b^2+b^2c^2+c^2a^2)-(a^4+b^4+c^4) = 16S^2$$where $a, b, c$ are the side lengths, which implies the result. For the inductive step, write $$\sum_{i=1}^{k-1} \frac{A_iA_{i+1}}{A_{k+1}A_i \cdot A_{k+1}A_{i+1}} = \frac{A_1A_k}{A_{k+1}A_1\cdot A_{k+1}A_k},$$which follows by inversion with arbitrary radius at $A_{k+1}$. Notice that every term on the LHS is the square root of a rational number, so it follows that there exist rational numbers $r_i$ such that each term is of the form $a_i = \sqrt q \cdot r_i$ for some rational number $q$. If any diagonal has square length divisible by $p^r$, we may induct down by splitting the polygon. Assume otherwise. Then we can check that $\nu_p(a_i) > \nu_p(a)$ where $a$ is the last term. On the other hand this yields a contradiction when we look at the Ptolemy equation.

what is ptolemy By shoelace $2S$ is an integer. I will now show it is divisible by $n$; to do this, by CRT it clearly suffices to look at $n=p^e$ only for $p$ an odd prime. The circumcenter $O$ of $P$ can be found by intersecting any two perpendicular bisectors, which are rational lines (i.e. can be written with rational coefficients), hence $O$ is a rational point. Hence the circumradius $r$ of $P$ is the square root of a rational number. We take two cases. Case 1: $\nu_p(r^2) \geq e$. In this case, consider a triangle $OA_iA_{i+1}$ (with indices modulo $n$); let $a=A_iA_{i+1}$ with $a^2$ an integer divisible by $p^e$. Then by Heron's, $$p^{2e}\mid 16[OA_iA_{i+1}]^2=2(a^2r^2+a^2r^2+r^4)-r^4-r^4-a^4,$$where $[\triangle]$ denotes signed area, hence $[OA_iA_{i+1}]$ is a rational number with $\nu_p$ at least $e$. Summing over all $i$ yields $\nu_p([P]) \geq e$, as desired. Case 2: $\nu_p(r^2)<e$. The idea is to induct on $k$, with base case of $k=3$ following from Heron's formula similarly to above. The key idea is the following "AIME-geo" claim. Claim: Let $ABC$ with a triangle with circumradius $r$ and side lengths $a,b,c$ as usual. Then $$c=\left|a\sqrt{1-\frac{b^2}{4r^2}}\pm b\sqrt{1-\frac{a^2}{4r^2}}\right|.$$Proof: By Law of Sines, $c=2r\sin\angle ACB$. On the other hand, if WLOG $\angle ACO\geq \angle BCO$, then $\angle ACB=\angle ACO \pm \angle BCO$ for some appropriate choice of sign. On the other hand, by dropping perpendiculars we have $\cos \angle ACO=\tfrac{b/2}{r}$, hence $\sin \angle ACO=\sqrt{1-\tfrac{b^2}{4r^2}}$. Symmetric equations hold for the sine and cosine of $\angle BCO$, so we finish by the sine addition/subtraction formula, depending on sign choice. $\blacksquare$ Now consider the diagonal $A_1A_3$. Since $A_1$ and $A_3$ are integer points, $A_1A_3^2 \in \mathbb{Z}$. On the other hand, by the above formula (where $a=A_1A_2$, $b=A_2A_3$, $c=A_1A_3$), we have $$c^2=a^2\left(1-\frac{b^2}{4r^2}\right)+b^2\left(1-\frac{a^2}{4r^2}\right)\pm 2ab\sqrt{\left(1-\frac{a^2}{4r^2}\right)\left(1-\frac{b^2}{4r^2}\right)}.$$Since $\nu_p(r^2)<e$, we have $\nu_p(\tfrac{a^2}{4r^2})=\nu_p(\tfrac{b^2}{4r^2})>0 \implies \nu_p(1-\tfrac{a^2}{4r^2}),\nu_p(1-\tfrac{b^2}{4r^2})=0$. Thus each individual term has $\nu_p$ at least $e$, since it can be expressed as the product of a number with $\nu_p$ at least $e$ with a number with $\nu_p$ at least $0$. Thus $\nu_p(c^2) \geq e$ as well. Therefore, we can dissect $P$ into $A_1A_2A_3$ and $A_1A_3A_4\ldots A_k$ and apply inductive hypothesis. These two cases finish the problem. $\blacksquare$ Remark: Originally I had a solution which used the same idea, but because I didn't realize that $c^2$ was an integer, I was working with some claim along the lines of $a^2/p^e,b^2/p^e$ in $\mathbb{F}_{p^{2^i}}$ implies $c^2/p^e$ in $\mathbb{F}_{p^{2^{i+1}}}$. The finish is then that after we end up triangulating $P$, we evaluate the area as a sum of Heron's statements to get that $16S^2/p^{2e}$ is in $\mathbb{F}_{p^{2^\text{something}}}$. But it's also rational, so it's in $\mathbb{F}_p$ and then $p^e \mid S$ follows. You can also replace these all with $\overline{\mathbb{F}_p}$. Really, this solution is the same as the one above, but after someone pointed out that $c^2$ was an integer (oops) it turns out you can avoid this language and just work with $\nu_p$ directly.

Uhh, may someone tell me if anything is wrong with the following: Claim: Heron's theorem doesn't work for proving the k = 3 case. Proof: The method using Heron's theorem doesn't take into account the fact that all of the coordinates are integers. This means if we let n = 1, then an equilateral triangle of side length 1 satisfies the conditions, but its area * 2 is not an integer. Hence, the method doesn't work.

bumpity bump bump

palindrome868 wrote: Uhh, may someone tell me if anything is wrong with the following: Claim: Heron's theorem doesn't work for proving the k = 3 case. Proof: The method using Heron's theorem doesn't take into account the fact that all of the coordinates are integers. This means if we let n = 1, then an equilateral triangle of side length 1 satisfies the conditions, but its area * 2 is not an integer. Hence, the method doesn't work. Well, I think it is crucial what you mean by "it doesn't work": You are right that it alone is not sufficient as one still needs to prove $2S$ is an integer (otherwise the use of divisibility makes no sense). If one proves $2S$ is an integer beforehand though, the approach works out to show that this integer is divisible by $n$ (and is even the same way as presented in the official solution). And you are also correct that you need the integral coordinates to prove that $2S$ is an integer

what. By Shoelace $2S$ is an integer. It clearly suffices to show the problem where $n$ is a prime power $p^e$. Note that by Heron's formula, the area of a triangle with sidelengths $\sqrt a$, $\sqrt b$, and $\sqrt c$ is $1/4\sqrt{-(a^2+b^2+c^2)+2ab+2bc+2ca}$. We use this formula many times in our solution. There are two cases: Case 1: The squares of the lengths of all diagonals are divisible by $n$. In this case, we may triangulate our polygon. By Shoelace, the area of each triangle is a half-integer, but by Heron's, the area is divisible by $n$, so we're done. Case 2: There exists a diagonal whose length squared is not divisible by $n$. By ``building up'' from side lengths there exists three vertices whose triangle consists of sidelengths $\sqrt a$, $\sqrt b$, and $\sqrt c$ where $n\mid a,b$ but not $c$. Suppose $\nu_p(c)=f<e$. The circumradius $R$ satisfies \[R^2=\frac{abc}{-(a^2+b^2+c^2)+2ab+2bc+2ca}\implies \nu_p(R^2)\ge (2e+f)-2f\ge e\implies n\mid R^2,\]under the rational definition of divisibility. Now, split the polygon into triangles like a pizza such that the circumcenter $O$ is a vertex of all triangles. Since $O$ is a rational point the squares of the sidelengths of all triangles are rational numbers divisible by $n$, so we're done as in Case 1!