Теорема формулируется для взаимно простых оснований. Существует ли какой-то универсальный критерий определения существования решения системы линейных сравнений в случае, когда эти основания не взаимно просты? Если такой критерий есть, то есть ли алгоритм решения такой системы сравнений. Как я понимаю, если решение существует, то оно будет единственным по модулю НОК всех оснований.

задан 25 Мар '16 10:22

10|600 символов нужно символов осталось
1

Рассмотрим сравнение $%x\equiv a\pmod{n}$% по составному модулю. Оно равносильно системе сравнений вида $%x\equiv a\pmod{p^k}$% по модулю степеней простых чисел, входящих в каноническое разложение. Тогда для каждого простого $%p$% мы из нескольких сравнений получаем систему условий вида $%x\equiv a_i\pmod{p^{k_i}}$%. Надо взять наибольшее из чисел вида $%k_i$%, для которого мы знаем, с чем сравнимо $%x$%, и тогда для всех остальных степеней значения определяются однозначно. Скажем, если мне известен остаток от деления числа на 64, то я автоматически знаю остатки от его деления на 32, 16, и так далее. Нужно сравнить, такие ли они в системе, и если где-то есть несовпадение, то это означает несовместность. А если везде имеют место совпадения, то все условия, кроме одного, являются лишними. Тогда их удаляем, и получаем систему, где для каждого простого $%p$% присутствует только одно условие сравнимости по модулю степени числа $%p$%. Это случай обычной китайской теоремы об остатках.

Из этого описания ясно, что решение, в случае его существования, единственно по модулю НОК. То же следует и из общих соображений: если $%x$% и $%y$% -- два решения системы, то их разность делится на каждое число, сравнение по модулю которого у нас рассматривается, а это равносильно делимости на НОК.

При практическом способе решения систем, мы можем применять метод исключения неизвестных независимо от взаимной простоты. Если есть одно уравнение вида $%x\equiv a\pmod{n}$%, то полагаем $%x=ny+a$%, где $%y$% -- новая целочисленная неизвестная. Далее подставляем это выражение в уравнения системы, и поочерёдно решаем. Если где-то при решении линейного сравнения не получается решения, то система несовместна. А сам этот момент всегда отслеживается. Поэтому мы либо получаем несовместную систему, либо одно условие вида $%x\equiv c\pmod{N}$%, где $%N$% есть НОК.

ссылка

отвечен 25 Мар '16 11:24

изменен 25 Мар '16 11:26

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×48

задан
25 Мар '16 10:22

показан
1072 раза

обновлен
25 Мар '16 11:26

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru