8,9,10 |
| :---: | :---: | :---: |
|  | Geometric Interpretations in Algebra |  |
|  | $\underline{\text { Equations in Integers }}$ |  |
|  | Integer Lattices |  |

Author: Kirillov A.A.

Given two coprime natural numbers $a$ and $b$. Consider the set $M$ of integers that can be represented in the form $a x + b y$, where $x$ and $y$ are non-negative integers.

a) What is the largest integer $c$ that does not belong to the set $M$?

b) Prove that of the two numbers $n$ and $c - n$ (where $n$ is any integer), one belongs to $M$ and the other does not.
Let's formulate our problem in geometric terms. Each pair of integers $(x, y)$ will be called an "integer point" and will be represented as a red point if both its coordinates are non-negative, and as a blue point if at least one coordinate is negative. For each integer $n$, the equation $a x + b y = n$ defines a line $l_{n}$. All lines $l_{n}$ are parallel to each other. Let $n$ be an integer. We will consider the line $l_{n}$ to be red if it passes through at least one red point, and blue otherwise.

Each line $l_{n}$ passes through exactly one integer point in the strip $0 \leq x \leq b-1$ (see problem $\underline{60525}$ a, when $b=1$ the strip degenerates into a line). It is clear that if a line is red, then its integer point in the specified strip will also be red (and the point of a blue line, of course, will be blue).

Now notice that under the symmetry relative to the point $({ }^{-1}-1 / 2, 1 / 2)$ (this symmetry is defined by the formula $(x, y) \rightarrow (b-1-x, -1-y)$), the specified strip maps to itself, and red points map to blue points, and vice versa. The line $l_{n}$ is mapped by this symmetry to the line $l_{a b-a-b-n}$:

if $a x + b y = n$, then $a x^{\prime} + b y^{\prime} = a(b-1-x) + b(-1-y) = a b - a - b - n$. Clearly, the lowest red line is $l_{0}$. Therefore, the highest blue line is $l_{a b-a-b}$. Thus, the largest number not belonging to the set $M$ is $c = a b - a - b$, and out of the two numbers $n$ and $c - n$, one belongs to $M$ and the other does not.

## Answer

a) $c = a b - a - b$.