Метод последовательного замещения
Эта статья , возможно, содержит оригинальные исследования . ( сентябрь 2014 г. ) |
В модульной арифметике метод последовательной замены — это метод решения задач одновременного сравнения с использованием определения уравнения сравнения. условия китайской теоремы об остатках Обычно его применяют в тех случаях, когда не выполняются .
Существует также несвязанный метод последовательной замены численного анализа, рандомизированный алгоритм, используемый для поиска корня , применение итерации с фиксированной точкой .
Метод последовательной замены также известен как обратная замена.
Примеры
[ редактировать ]Пример первый
[ редактировать ]Рассмотрим простой набор одновременных сравнений
- х ≡ 3 (по модулю 4)
- х ≡ 5 (по модулю 6)
Теперь, чтобы x ≡ 3 (mod 4) было истинным, x = 3 + 4 j для некоторого целого числа j . Подставим это во второе уравнение
- 3+4 j ≡ 5 (по модулю 6)
так как мы ищем решение обоих уравнений.
Вычтите 3 из обеих частей (это разрешено в модульной арифметике)
- 4 j ≡ 2 (по модулю 6)
Мы упрощаем, разделив на наибольший общий делитель 4, 2 и 6. Деление на 2 дает:
- 2 j ≡ 1 (по модулю 3)
Евклидово модульное мультипликативное обратное к 2 по модулю 3 равно 2. После умножения обеих частей на обратное, мы получаем:
- j ≡ 2 × 1 (по модулю 3)
или
- j ≡ 2 (по модулю 3)
Чтобы вышесказанное было правдой: j = 2 + 3 k для некоторого целого числа k . Теперь подставим обратно в 3 + 4 j и получим
- х = 3 + 4(2 + 3к )
Расширять:
- х = 11 + 12 к
чтобы получить решение
х ≡ 11 (по модулю 12)
Пример 2 (более простой метод)
[ редактировать ]Хотя метод, использованный в предыдущем примере, является последовательным, он не работает для каждой проблемы.
Рассмотрим эти четыре системы сравнений:
- х ≡ 1 (мод. 2)
- х ≡ 2 (по модулю 3)
- х ≡ 3 (по модулю 5)
- х ≡ 4 (мод. 11)
Чтобы продолжить поиск выражения, представляющего все решения, удовлетворяющие этой системе линейных сравнений, важно знать, что a (mod b) имеет аналогичное тождество:
- a (mod b) ⇔ b k + a, ∀k ∈ Z, где k — произвольная константа.
ПРОЦЕДУРА
[ редактировать ]1. Начните с переписывания первого сравнения в виде уравнения:
- x = 2a + 1, ∀a ∈ Z
2. Перепишем второе сравнение в виде уравнения, и уравнение, найденное на первом шаге, приравняем этому уравнению, так как x заменит x во втором сравнении:
- х ≡ 2 (по модулю 3)
- х = 2а + 1 ≡ 2 (по модулю 3)
- 2а ≡ 1 (мод. 3)
- а ≡ 2 −1 (против 3)
- а = -1.
Поскольку a должна быть положительной неотрицательной инверсией , нам нужен положительный a . Таким образом, мы добавляем любой текущий модуль к a, который равен a = -1 + 3 = 2 .
3. Теперь перепишем a = 2 через наш текущий модуль:
- а = 2 (модуль 3)
- ∴а = 3б + 2
4. Теперь мы подставляем наше текущее значение a в наше уравнение, которое мы нашли на шаге 1 относительно x:
- х = 2а + 1
- = 2(3b + 2) + 1, ∀b ∈ Z
- = 6б + 5.
∴ х = 6б + 5.
5. Теперь мы подставим наше новое значение x в x в нашем третьем линейном сравнении и перепишем 3 (по модулю 5) в его эквивалентное выражение:
- х ≡ 3 (по модулю 5)
- = 6b + 5 ≡ 3 (по модулю 5)
- = 6б + 5 = 5б + 3
- = б = -2.
Поскольку b = -2 , мы добавляем к нему наш ток по модулю, чтобы получить b = 3.
∴ б = 5в + 3.
6. Мы снова подставляем наше новое значение b в наше уравнение, которое мы нашли на шаге 4 относительно x:
- х = 6б + 5
- = 6(5в + 3) + 5
- = 30с + 23
∴ x = 30c + 23, ∀c ∈ Z
7. Теперь мы подставляем наше новое значение x в x нашего окончательного линейного сравнения, переписывая 4 (по модулю 11) в его эквивалентное выражение:
- х ≡ 4 (мод. 11)
- = 30c + 18 ≡ 4 (по модулю 11)
- = 30с + 23 = 11с + 4
- = 19с = -19
- = с = -1.
Добавляя наш текущий модуль к значению, которое представляет c , мы получаем новое c = 10.
∴ c = 11d + 10, ∀d ∈ Z.
8. Наш последний шаг — подставить c в уравнение относительно x , которое мы нашли на шаге 6:
- х = 30с + 23
- = 30(11д + 10) + 23
- = 330д + 323.
∴ 330d + 323 представляет все решения, удовлетворяющие системе сравнений, с которой мы начали.
Проверка нашей работы
[ редактировать ]Чтобы проверить правильность нашего ответа, мы выясняем, задуман ли каждый соответствующий остаток, когда мы вычисляем 323 по модулю каждого сравнения:
323 ≡ 1 (мод. 2)
- 323 = 161 * 2 + 1
323 ≡ 2 (мод. 3)
- 323 = 107 * 3 + 2
323 ≡ 3 (мод. 5)
- 323 = 64 * 5 + 3
323 ≡ 4 (мод. 11)
- 323 = 29 * 11 + 4
Альтернативный метод мог бы заключаться в том, чтобы определить, делит ли каждый модуль разницу 323 и соответствующий остаток каждого сравнения:
2 | (323 - 1) верно.
3 | (323 - 2) верно.
5 | (323 – 3) верно.
11 | (323 – 4) верно.
Другой способ решения системы линейных сравнений — использовать китайскую теорему об остатках , и она даст нам тот же результат.
Пример 3 (аналогичный метод, использованный выше, но с некоторыми изменениями)
[ редактировать ]При решении системы линейных сравнений с использованием метода, использованного в приведенном выше примере, возникнут ситуации, когда решение переменной приведет к рациональному результату.
Ключом к решению переменной является добавление текущего модуля к другой стороне уравнения до тех пор, пока коэффициент переменной, которая решается, не станет кратным.
закупается. Вот пример:
- х ≡ 2 (по модулю 3)
- х ≡ 3 (по модулю 5)
- х ≡ 2 (по модулю 7)
ПРОЦЕДУРА
[ редактировать ]1. Перепишем первое линейное сравнение в эквивалентное ему уравнение:
- х ≡ 2 (по модулю 3)
- x = 3a + 2, ∀a ∈ Z.
2. Перепишем второе сравнение в виде уравнения и приравняем выражение к выражению, найденному на предыдущем шаге:
- х ≡ 3 (по модулю 5)
- x = 5a + 3, ∀a ∈ Z
- 3а + 2 = 5а + 3
- -1 = 2а
Здесь у метода, использованного в примере 2, возникают проблемы, но я нашел решение: добавьте любой текущий модуль к той части уравнения, где нет переменной, до тех пор, пока коэффициент не сможет его разделить. Причина, по которой мы можем это сделать, заключается в определении класса конгруэнтности . Таким образом,
3. Добавьте 5, наш модуль, к -1, чтобы получить:
- -1 + 5 = 4
- 4 = 2а
- а = 2.
4. Перепишите a = 2 как эквивалентное модульное уравнение.
- a = 2 становится a = 5b + 2, ∀b ∈ Z.
5. Подставим наш ток a в уравнение, полученное на шаге 1 относительно x:
- х = 3а + 2 = 3 (5б + 2) + 2 = 15б + 8.
- ∴ х = 15б + 8.
6. Наконец, перепишите третье сравнение и приравняйте его к уравнению, полученному на предыдущем шаге, решая для b.
- x ≡ 2 (mod 7) можно переписать как x = 7b + 2.
Подставив х, получим
- 15б + 8 = 7б + 2
- 8б = -6
Добавьте наш текущий модуль, равный 7, к -6, пока не получится число, кратное 8:
- -6 + 7 = 1 + 7 = 8.
Таким образом,
- 8б = 8
- б = 1.
Переписывая b через его модуль, имеем
- b = 7c + 1, ∀c ∈ Z
7. Замените наше новое уравнение b на b в уравнении относительно x, которое мы придумали на шаге 6:
- х = 15б + 8
- = 15 (7в + 1) + 8
- = 105с + 23
- ∴ х = 105с + 23.
∴ 105c + 23 представляет все решения, удовлетворяющие системе сравнений, с которой мы начали.
Проверка нашей работы
[ редактировать ]Чтобы проверить правильность нашего ответа, мы выясняем, задуман ли каждый соответствующий остаток, когда мы вычисляем 23 по модулю каждого сравнения:
23 ≡ 2 (мод. 3)
- 23 = 7 * 3 + 2
23 ≡ 3 (мод. 5)
- 23 = 4 * 5 + 3
23 ≡ 2 (мод. 7)
- 23 = 3 * 7 + 2
Общий алгоритм
[ редактировать ]В общем:
- напишите первое уравнение в эквивалентной форме
- заменить его на следующий
- упростите, используйте модульное мультипликативное обратное при необходимости
- продолжайте до последнего уравнения
- обратно заменить, затем упростить
- переписать обратно в форму сравнения
Если модули взаимно просты , китайская теорема об остатках дает простую формулу для получения решения.