# 2016 IMO Problems/Problem 3

## Problem

Let be a convex polygon in the plane. The vertices have integral coordinates and lie on a circle. Let be the area of . An odd positive integer is given such that the squares of the side lengths of are integers divisible by . Prove that is an integer divisible by .

## Solution

Note that is always an integer for any lattice polygon, so it remains to show that it is divisible by . It clearly suffices to prove the problem for when is a prime power. We proceed using induction on , with the base case of settled by Heron's formula: If are the side lengths of the triangle, then the square of the area is . As , we have that , as desired.

For the inductive step, we claim that there exists a diagonal whose length squared is also divisible by . Then, we may split into two polygons with less vertices and areas divisible by by assumption. Let be such that is minimized. By Ptolemy's Theorem on cyclic quadrilateral , we have that , or . As we have and , the terms under the square roots on the LHS are integers, so the LHS is an algebraic integer. This implies that the term under the square root on the RHS is also an integer, so , as desired.