§ 4. Линейные сравнения с одним неизвестным.

§ 4. Линейные сравнения с одним неизвестным.

1. Общие определения.

Определение 1 . Сравнением с одним неизвестным по модулю называется сравнение вида , (1)

левая часть которого – многочлен с целыми коэффициентами. Если не делится на число , то число называется степенью сравнения; если , то старший член сравнения (1) удовлетворяет условию и поэтому в (1) его можно отбросить.

Определение 2. Решением сравнения всякое целое число , которое удовлетворяет сравнению, то есть такое, что .

Легко понять, что в этом случае вместе с числом сравнению удовлетворяют и все числа класса . Поэтому класс вычетов по модулю , числа которого удовлетворяют сравнению , считается за одно решение этого сравнения. При таком соглашении сравнение (1) будет иметь столько решений, сколько вычетов ПСВ ему удовлетворяют. Поскольку ПСВ по модулю состоит из вычетов, то сравнение (1) может иметь только конечное количество решений или не может иметь их совсем.

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

Определение 3. Два сравнения называются равносильными, если множества их решений совпадают.

Чтобы построить сравнения, равносильные заданному сравнению, над заданным сравнением проводят операции, которые основываются на свойствах сравнимости, рассмотренных раньше. К операциям, которые не меняют множества решений, принадлежат такие:

а) прибавление к обеим частям сравнения произвольного многочлена с целыми коэффициентами,

б) прибавление к одной из частей сравнения многочлена с коэффициентами, кратными модулю ,

в) умножение обеих частей сравнения на число, взаимно простое с модулем,

г) умножение обеих частей сравнения и модуля на одно и тоже положительное целое число.

2. Сравнение первой степени.

Сравнения первой степени имеют вид (2). Перенеся свободный член в правую часть сравнения, и меняя обозначения коэффициентов, получим

. (3)

При решении таких сравнений рассматривают два случая: и .

Теорема 1. Если , то сравнение (3) имеет единственное решение.

Доказательство. Сравнение может иметь не более решений, в соответствии с количеством чисел в ПСВ. Если пробегает ПСВ, то и линейная форма также пробегает ПСВ. При этом один раз линейная форма примет то значение, которое сравнимо с нулем, та как нуль есть один из вычетов ПСВ.

Теорема 2. Если и число не делится на , то сравнение не имеет решений.

Доказательство проводится методом от противного, с использованием свойств делимости.

Теорема 3. Если и , то сравнение (3) имеет решений.

Доказательство. Пусть . Тогда сокращая (3) на , получим сравнение (4), которое равносильное сравнению (3). Поскольку , то последнее сравнение по теореме 1 имеет единственное решение - , то есть . Рассмотрим последовательность классов

(5)

Нетрудно убедиться, что эти классы являются решениями сравнения (3), для этого достаточно подставить их в сравнение, причем они различны (это доказывается методом от противного и с использованием свойств сравнимости) и других решений нет.

Замечание. Неопределенное уравнение первой степени сводится к решению сравнения или .

Способы решения сравнения первой степени.

Рассмотрим некоторые наиболее распространенные способы решения сравнений первой степени.

I способ. Подстановка в сравнение чисел ПСВ. Этот способ применяется при небольших модулях. При больших модулях подстановку вычетов ПСВ проводят только на заключительном этапе построения равносильных сравнений.

II способ. Приведение сравнения первой степени к равносильному сравнению с коэффициентом при , равному единице. Этот способ основывается на проведение ряда равносильных преобразований заданного сравнения с помощью операций, рассмотренных нами выше.

III способ. Способ Эйлера. Пусть задано сравнение , (6)

где . Сравнение имеет единственное решение. По теореме Эйлера , верным будет и сравнение и сравнивая его с (6), видим, что (7).

IV способ. Решение сравнения при помощи цепных дробей.. Пусть задано сравнение , (6) где . Разложим в цепную дробь. Если и являются последними подходящими дробями, то по свойству подходящих дробей имеем , . Учитывая, что первое слагаемое кратно модулю, получим дальше . Умножая левую и правую часть сравнения на , получим . Следовательно, решением сравнения будет . (8)

Пример 1. Решить сравнение .

Решение. I способ. Решим сравнение методом проб (подстановка в сравнение чисел ПСВ). Выпишем ПСВ (наименьших неотрицательных): 0, 1, 2, 3, 4, 5, 6, 7, 8 и подставим каждый вычет в данное сравнение: не сравнимо с ; не сравнимо с 5; . Следовательно, - решение. Дальше проверять не следует, т. к. поскольку , то данное сравнение имеет единственное решение. Этот способ применяется при небольших модулях. При больших модулях подстановку вычетов ПСВ проводят только на заключительном этапе построения равносильных сравнений.

II способ. Приведение сравнения I-й степени к равносильному сравнению с коэффициентом при , равном 1. Этот способ основывается на проведении ряда равносильных преобразований заданного сравнения. Прибавив в правой части 9, получим: или . Так как , то обе части сравнения можно поделить на 7. Получим: .

III способ. (способ Эйлера). Применим теорему Эйлера:

, , . Умножим обе части сравнения на . , , или , , . Можно сразу же по общей формуле записать: . Отметим, что метод решения сравнения, основанный на применении теоремы Эйлера и Ферма, нельзя отнести к рациональным методам решения сравнений.

Пример 2. Разрешимы ли следующие сравнения:

1) ; 2) ; 3) .

Решение. 1) Так как , следовательно, сравнение имеет единственное решение: .

2) Так как и , следовательно, сравнение имеет по модулю 21 три класса решений, которые объединяются в один класс по модулю . Данное сравнение равносильно (сокращение на 3) сравнению из условия 1). Общее решение: , где . Окончательно получим: , , .

Пример 3. Решить сравнение с помощью цепных дробей (4-способ).

Решение. Так как , , то сравнение имеет 6 решений. Поделив обе части сравнения и модуль на 6, получим сравнение . Представим в виде цепной дроби число . , . Составим таблицу подходящих дробей.

n
q

; ; .

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

Пример 4. Решить неопределенное уравнение .

Решение. Так как , то уравнение имеет решение в целых числах; учитывая, что 23 – целое положительное число, его можно принять за модуль соответствующего сравнения, в результате получим: . Прибавляя к левой части сравнения число , кратное модулю, приходим к сравнению, , т.е. , где ; подставив полученное значение в данное уравнение, после простейших преобразований находим, что , где . Получим общее решение данного уравнения в виде , , где .

Пример 5. Найти числа, которые при делении на 7, 13, 17 дают в остатке соответственно 4, 9 и 1.

Решение. Искомые числа должны удовлетворять системе сравнений:

Так как модули сравнений попарно взаимно просты, что эта система имеет единственное решение по модулю . Первое сравнение имеет единственное решение: , где . Подставим во второе сравнение вместо выражение , получим: . Так как , то последнее сравнение имеет единственное решение: , т.е. , , а значит, , . Найдем те значения , при которых будет удовлетворять третьему сравнению Имеем: или . Откуда , следовательно, ; итак, или .

Упражнения.

№1. Что называется сравнением -й степени с неизвестно величиной?

№2. Почему сравнение имеет не более чем решений?

Почему при решении этого сравнения достаточно ограничиться

испытанием чисел 0, 1, 2, …, ?

№3. Какие сравнения называются равносильными?

№4. Перечислите преобразования и операции, приводящие к равносильным

сравнениям.

№5. Дано сравнение . При каких условиях оно имеет

единственное решение, не имеет решений, имеет решений?

№6. Чему равна степень сравнения: ?

№7. После некоторых преобразований, приводящих к равносильным

сравнениям, решить путем испытаний наименьших неотрицательных

вычетов следующие сравнения:

1) ; 2) ;

3) ; 4) .

№8. Решите следующие сравнения:

1) ; 2) ; 3) ;

4) ; 5) ; 6) ;

7) ; 8) ; 9) ;

10) ; 11) ; 12) .

Дата добавления: 2015-08-28