Китайская теорема об остатках

6.2K

Китайская теорема об остатках — это основное утверждение теории чисел, которое позволяет решать системы линейных диофантовых уравнений с двумя или более неизвестными. В основном, это теорема о системах сравнений.

Материал на этой странице не был проверен методистами Skysmart и может содержать ошибки. Если вы заметили неточность, напишите нам на skysmart.blog@skyeng.ru.

Для кого эта статья:

студенты и выпускники математических и технических специальностей
преподаватели математики или исследования в области теории чисел
интересующиеся криптографией и её математическими основами

Формулировка

Пусть — попарно взаимно простые числа. Тогда для любых целых существует число x, такое что:

Более того, решение x определено однозначно по модулю M, где .

Доказательство

Для простоты начнем с системы из двух уравнений:

Поскольку и взаимно просты, существуют такие числа и , что:

Это следует из тождества Безу.

Теперь определим число x:

Проверим, удовлетворяет ли это число уравнениям:

По модулю :

Таким образом, x удовлетворяет обоим уравнениям. Подобные рассуждения можно обобщить на систему из k уравнений, рассматривая их попарно.

Китайская теорема об остатках играет важную роль в различных областях математики и её приложениях, включая криптографию. Она предоставляет эффективный метод для решения систем линейных уравнений с попарно взаимно простыми модулями.