MAXimal | |
добавлено: 11 Jul 2008 10:35 Содержание [скрыть] Модульное линейное уравнение первого порядкаПостановка задачиЭто уравнение вида: где — заданные целые числа, — неизвестное целое число. Требуется найти искомое значение , лежащее в отрезке (поскольку на всей числовой прямой, ясно, может существовать бесконечно много решений, которые будут отличаться друг друга на , где — любое целое число). Если решение не единственно, то мы рассмотрим, как получить все решения. Решение с помощью нахождения Обратного элементаРассмотрим сначала более простой случай — когда и взаимно просты. Тогда можно найти обратный элемент к числу , и, домножив на него обе части уравнения, получить решение (и оно будет единственным): Теперь рассмотрим случай, когда и не взаимно просты. Тогда, очевидно, решение будет существовать не всегда (например, ). Пусть , т.е. их наибольший общий делитель (который в данном случае больше единицы). Тогда, если не делится на , то решения не существует. В самом деле, при любом левая часть уравнения, т.е. , всегда делится на , в то время как правая часть на него не делится, откуда и следует, что решений нет. Если же делится на , то, разделив обе части уравнения на это (т.е. разделив , и на ), мы придём к новому уравнению: в котором и уже будут взаимно просты, а такое уравнение мы уже научились решать. Обозначим его решение через . Понятно, что это будет также являться и решением исходного уравнения. Однако если , то оно будет не единственным решением. Можно показать, что исходное уравнение будет иметь ровно решений, и они будут иметь вид: Подводя итог, можно сказать, что количество решений линейного модульного уравнения равно либо , либо нулю. Решение с помощью Расширенного алгоритма ЕвклидаПриведём наше модулярное уравнение к диофантову уравнению следующим образом: где и — неизвестные целые числа. Способ решения этого уравнения описан в соответствующей статье Линейные диофантовы уравнения второго порядка, и заключается он в применении Расширенного алгоритма Евклида. Там же описан и способ получения всех решений этого уравнения по одному найденному решению, и, кстати говоря, этот способ при внимательном рассмотрении абсолютно эквивалентен способу, описанному в предыдущем пункте.
|