Jump to content

Метод последовательного замещения

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

Существует также несвязанный метод последовательной замены численного анализа, рандомизированный алгоритм, используемый для поиска корня , применение итерации с фиксированной точкой .

Метод последовательной замены также известен как обратная замена.

Пример первый

[ редактировать ]

Рассмотрим простой набор одновременных сравнений

х ≡ 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 + )

Расширять:

х = 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

Общий алгоритм

[ редактировать ]

В общем:

  • напишите первое уравнение в эквивалентной форме
  • заменить его на следующий
  • продолжайте до последнего уравнения
  • обратно заменить, затем упростить
  • переписать обратно в форму сравнения

Если модули взаимно просты , китайская теорема об остатках дает простую формулу для получения решения.

См. также

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 2d65fde0b434226ac6d73c074310049f__1715738520
URL1:https://arc.ask3.ru/arc/aa/2d/9f/2d65fde0b434226ac6d73c074310049f.html
Заголовок, (Title) документа по адресу, URL1:
Method of successive substitution - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)