Kvant Math Problem 2445

Let $A_{k+1} = A_1$, and let $q = p^t$ be an arbitrary prime power dividing the odd integer $n$.

kvantmathematicsolympiad

Verified: no
Verdicts: FAIL + PASS
Solve time: 33m36s
Source on kvant.digital

Problem

Let $P=A_1A_2\ldots A_k$ be a convex polygon in the plane. The vertices $A_1$, $A_1$, $\ldots$, $A_k$ have integer coordinates and lie on a single circle. Denote by $S$ the area of the polygon $P$. An odd natural number $n$ is such that the squares of the lengths of all sides of the polygon $P$ are integers divisible by $n$. Prove that $2S$ is an integer divisible by $n$.

A. Gaifullin

International Mathematical Olympiad (57th)

Exploration

Let $A_{k+1} = A_1$, and let $q = p^t$ be an arbitrary prime power dividing the odd integer $n$. It suffices to prove that $q \mid 2S$ for every such prime power. The vertices lie on a circle with an integer equation

$a(x^2 + y^2) + bx + cy + d = 0,$

chosen primitive so that $\gcd(a,b,c,d) = 1$. For a vertex $A_i = (x_i, y_i)$ define the edge vector $e_i = A_{i+1} - A_i = (u_i, v_i)$. Subtracting the circle equation evaluated at $A_i$ and $A_{i+1}$ gives

$a\bigl((x_i + u_i)^2 + (y_i + v_i)^2 - x_i^2 - y_i^2\bigr) + b u_i + c v_i = 0,$

which simplifies to

$2a(x_i u_i + y_i v_i) + a(u_i^2 + v_i^2) + b u_i + c v_i = 0.$

Since $q \mid \lVert e_i \rVert^2 = u_i^2 + v_i^2$ for every side, we have

$2a(x_i u_i + y_i v_i) + b u_i + c v_i \equiv 0 \pmod q.$

Summing over all $i = 1, \dots, k$ yields

$\sum_{i=1}^k \bigl(2a(x_i u_i + y_i v_i) + b u_i + c v_i\bigr) \equiv 0 \pmod q.$

The terms involving $b$ and $c$ vanish under the telescoping sum, because $\sum_{i=1}^k u_i = \sum_{i=1}^k v_i = 0$, leaving

$2a \sum_{i=1}^k (x_i u_i + y_i v_i) \equiv 0 \pmod q.$

The well-known formula $x_i u_i + y_i v_i = \det(A_i, e_i)$ gives

$2a \sum_{i=1}^k \det(A_i, e_i) = 4aS,$

where $S$ is the area of the polygon. Therefore

$4aS \equiv 0 \pmod q.$

The proof now splits according to the residue class of $p$ modulo $4$.

Approaches

The case $p \equiv 3 \pmod 4$ is handled by a valuation argument. The condition $q \mid \lVert e_i \rVert^2$ forces both coordinates of every edge vector to be divisible by $p^{\lceil t/2 \rceil}$, and the shoelace formula then yields $q \mid 2S$. For $p \equiv 1 \pmod 4$, the cyclicity of the polygon is essential. Define the vectors

$B_i = 2a A_i + (b, c).$

Then $B_i \cdot e_i \equiv 0 \pmod q$ because $2a A_i \cdot e_i + b u_i + c v_i \equiv 0 \pmod q$, and also $e_i \cdot e_i \equiv 0 \pmod q$. The key lemma is as follows. If $u \in (\mathbb{Z}/q\mathbb{Z})^2$ satisfies $u \cdot u \equiv 0$ and $v \cdot u \equiv 0$, then $v$ is a scalar multiple of $u$ modulo $q$. This is justified by lifting solutions modulo $p$ using Hensel's lemma, because $-1$ is a square modulo $p$ and $q = p^t$. Applying this lemma to $B_i$ and $e_i$ gives that $B_i \equiv \lambda_i e_i \pmod q$ for some scalar $\lambda_i \in \mathbb{Z}/q\mathbb{Z}$. Summing over all sides, $\sum_{i=1}^k B_i \cdot e_i \equiv \sum_{i=1}^k \lambda_i \lVert e_i \rVert^2 \equiv 0 \pmod q$, and this implies $4aS \equiv 0 \pmod q$ as before. Because $q$ is odd and $p \nmid a$, the integer $4a$ is invertible modulo $q$, so $q \mid 2S$.

Solution

Fix a prime power $q = p^t \mid n$. We first show that $p \nmid a$. Suppose $p \mid a$. Reducing the circle equation modulo $p$ yields

$b x + c y + d \equiv 0 \pmod p$

because $a \equiv 0 \pmod p$ and the equation is primitive. Hence all vertices lie on a line modulo $p$. For every side vector $e_i = (u_i, v_i)$, $q \mid u_i^2 + v_i^2$ implies $u_i \equiv v_i \equiv 0 \pmod p$ if $p \equiv 3 \pmod 4$, and $e_i$ is parallel to $(1, \omega)$ or $(1, -\omega)$ modulo $p$ if $p \equiv 1 \pmod 4$, where $\omega^2 \equiv -1 \pmod p$. In both cases, all vertices are congruent modulo $p$ to a single point, contradicting the primitiveness of the circle equation. Therefore $p \nmid a$.

Case 1: $p \equiv 3 \pmod 4$

Let $e_i = (u_i, v_i)$. The condition $q \mid u_i^2 + v_i^2$ forces $v_p(u_i^2 + v_i^2) \ge t$. Because $-1$ is a non-square modulo $p$, at least one of $u_i$, $v_i$ must be divisible by $p^{\lceil t/2 \rceil}$, so $v_p(u_i) \ge \lceil t/2 \rceil$ and $v_p(v_i) \ge \lceil t/2 \rceil$. Translating the polygon so that $A_1 = (0,0)$, every vertex is a sum of edge vectors, so each coordinate of every vertex is divisible by $p^{\lceil t/2 \rceil}$. By the shoelace formula, each term $x_i y_{i+1} - x_{i+1} y_i$ is divisible by $p^t$, and thus $q \mid 2S$.

Case 2: $p \equiv 1 \pmod 4$

Choose $\omega \in \mathbb{Z}/q\mathbb{Z}$ with $\omega^2 \equiv -1 \pmod q$, obtained by Hensel lifting from a solution modulo $p$. Let $B_i = 2a A_i + (b, c)$, then $B_i \cdot e_i \equiv 0 \pmod q$ and $e_i \cdot e_i \equiv 0 \pmod q$. The lemma asserts that if $u \cdot u \equiv 0$ and $v \cdot u \equiv 0$ modulo $q$, then $v \equiv \lambda u \pmod q$ for some $\lambda$. To prove this, write $u = (u_1, u_2)$ with $u_1$ invertible modulo $p$; the equation $u_1^2 + u_2^2 \equiv 0 \pmod q$ implies $u_2/u_1 \equiv \pm \omega \pmod q$. Then any $v$ orthogonal to $u$ satisfies $v_1 u_1 + v_2 u_2 \equiv 0$, hence $v_2/v_1 \equiv -u_1/u_2 \equiv \pm \omega$, so $v \equiv \lambda u \pmod q$. Applying this lemma to $B_i$ gives $B_i \equiv \lambda_i e_i \pmod q$ for some $\lambda_i$. Summing over all sides, $\sum_{i=1}^k B_i \cdot e_i \equiv \sum_{i=1}^k \lambda_i \lVert e_i \rVert^2 \equiv 0 \pmod q$, hence $4aS \equiv 0 \pmod q$. Since $q$ is odd and $p \nmid a$, we conclude $q \mid 2S$.

Combining prime powers

For every prime power $q \mid n$, we have proved $q \mid 2S$. The prime power divisors of $n$ are pairwise coprime, so $n \mid 2S$. This establishes the required divisibility.