Представление по остаткам. Аналог Китайской теоремы об остатках.

Пусть и — взаимно простые целые числа, и взаимно просто с . Тогда рациональному числу поставим в соответствие остатки . Под понимается решение сравнения .

Рассмотрим задачу восстановления рационального числа по его остаткам. Пусть рациональное число имеет остатки по модулям . Задача восстановления заключается в построении целого числа а и натурального числа , удовлетворяющего системе сравнений . Пусть — целое число, удовлетворяющее сравнениям . Систему сравнений можно заменить одним сравнением . Естественно среди решений сравнения желательно выбирать минимальные в каком-то смысле. Наиболее распространенными критериями выбора являются и , .

Задача восстановления рационального числа может быть записана как задача целочисленного программирования при условии , . При получается первый критерий, при — второй критерий, а при - третий. Все перечисленные функции являются однородными симметричными и выпуклыми. Приведем ряд результатов об условиях однозначности восстановления рационального числа для однородной симметричной выпуклой функции. Обозначим через V площадь фигуры .

Теорема. Для того, чтобы несократимая дробь была однозначно восстановлена по остаткам, достаточно выполнения неравенства < .

Доказательство. Допустим, имеется два решения сравнения — и , соответствующие разным дробям, для которых < , < и . Обозначим через S фигуру . Площадь этой фигуры, в силу однородности функции равна . Точки , , и принадлежат внутренности S. А в силу выпуклости функции, и весь параллелограмм с вершинами в этих точках лежит внутри S. Площадь параллелограмма равна модулю удвоенного определителя матрицы (по предположению, , поэтому определитель отличен от нуля). Если из первой строки вычтем вторую, умноженную на , то получим матрицу с целыми числами, причем элементы ее первой строки делятся на . Следовательно, значение определителя по абсолютной величине не меньше , и площадь параллелограмма не меньше 2 . Параллелограмм лежит внутри S, тем самым получили противоречие. Теорема доказана.

Площади фигур , , равны, соответственно, , 2 и 4. По теореме, для однозначного восстановления дроби а/b достаточно выполнения неравенства , или , или .

В качестве замечания к только что доказанной теореме отметим, необходимым условием однозначного восстановления дроби а/b является неравенство <2 .

Задача восстановления рационального числа сводится к задаче построения , при ограничениях , , и - целые числа. Функция предполагается квазивыпуклой на и симметричной. Для любого решения сравнения найдется целое , что . Подставив вместо его выражение, получим задачу целочисленного программирования , методы решения которой разберем ниже.