Решение системы уравнений по модулю

Решение системы уравнений по модулю

§ 3. Решение систем с параметром и с модулями

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

Решите систему уравнений $$ \left\<\begin\left|x-y\right|=5,\\ 3x+2y=10.\end\right.$$

Модуль в уравнении `|x-y|=5` можно «раскрыть», пользуясь определением модуля числа:

$$\left|x-y\right|=\left\<\beginx-y,\;\mathrm<или>\;x-y\geq0,\\y-x,\;\mathrm<или>\;x-y =0` записывается в виде `x-y=5`, а при `x-y =0`, система имеет вид:

Итак, `x=5`, `y=0`, условие `x-y>=0` выполняется. Значит, найденные пары чисел является решением исходной системы.

2 случай. Если `x-y =0`, `y>=0`;

4) `x =0`, `y>=0`, система имеет вид:

Оба полученные значения удовлетворяют заданным условиям: `1,5>=0`, `0>=0`.

2 случай. `x>=0`, `y =0`.

3 случай. `x =0` система имеет вид:

Первое уравнение не имеет решения, так как сводится к равенству `0=6`, значит система не имеет решений.

4 случай. `x -5/2`, то `|y+5/2|=y+5/2`; если `y то `|y+5/2|=-y-5/2`.

Выражение `y-1=0`, если `y=1`.

Если `y>1`, то `|y-1|=y-1`, а если `y =1`, то `|y-1|=y-1` и `|y+5/2|=y+5/2`, получаем уравнение:

Тогда `x=1/3(2*2+5)=3`. Число `2>1`, так что пара `(3;2)` является решением системы.

Пусть теперь `-5/2 хождения `y` получаем уравнение

Число `8/13` больше `(-5/2)`, но меньше, чем `1`, поэтому пара чисел `(27/13;8/13)` является решением системы.

Онлайн НОД и НОК, разложение на множители, сравнения по модулю

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

Наибольший общий делитель (НОД, англ. GCD) нескольких целых чисел есть наибольшее из натуральных чисел, которое делит каждое из данных чисел.

Наименьшее общее кратное (НОК, англ. LCM) нескольких целых чисел есть наименьшее из натуральных чисел, которое делится на каждое из данных чисел.

Запишите свои числа через запятую и/или пробел и нажмите кнопку.

Системы линейных сравнений по модулю. Китайская теорема об остатках

Определение 1.Системой m линейных cравнений с n неизвестными x₁, x₂,…, x_n (СЛCУ) называется система cравнений вида:

(1)

Определение 2.Решением системы сравнений (1) называется такой вектор , состоящий из классов вычетов по некоторому модулю m, для которого любой вектор целых чисел

удовлетворяет всем сравнениям системы (1).

Рассмотрим сначала случай, когда все модули m₁,…, m_k в системе (1) равны и система (1) имеет вид:

(2)

Если p простое число, то множество классов вычетов Z_p по модулю p является полем и для системы сравнений применимы все методы решений и основные теоремы, которые имеют место для теории СЛУ над полем.

Пример 1.Решить СЛС

Способ 1. Метод Гаусса:

Все операции выполняются по модулю 7 или в роле Z₇.

Способ 2. Правило Крамера:

Тогда система равносильна системе

Ответ: .

В общем случае для решению системы сравнений вида (2) можно применить методы, изложенные в лекции 2 для решения систем линейных диофантовых уравнений, учитывая следующие замечания:

Нельзя умножать или делить сравнения системы на числа, которые не взаимно простые с модулем, так как при этом может получиться не равносильная система сравнений. Такие преобразования системы назовем элементарными целочисленными приведенными преобразованиями.

Определение 3. Целая матрица D = (d_ij) размерности m´n называется матрицей канонического вида, если она обладает свойствами:

Элементы d_ij, i = 1, 2,…,k, где k = min <m, n>, называем диагональными элементами канонической матрицы. Обозначим число ненулевых диагональных элементов канонической матрицы через r. Очевидно, что r = rang D.

Теорема 1.Любую целую матрицу конечным числом целочисленных приведенных элементарных преобразований строк и столбцов можно привести к матрице канонического вида, при этом r = rang A.

Диагональные элементы d₁₁,…, d_rr, r = rang A, матрицы канонического вида, эквивалентной матрице A, называются элементарными делителями матрицы A.

Теорема 2.Система ЛC (2) разрешима тогда и только тогда, когда НОД(d_ii, m), элементарных делителей d_ii матрицы A делит соответствующие элементарные делители расширенной матрицы СЛС.

Пример 2. Выяснить разрешимость данной СЛС

Решение. Приводим матрицу и расширенную матрицу СЛС к каноническому виду.

,

Так как элементарные делители матриц равны, то данная СЛДУ разрешима.

Алгоритм решения СЛС Пусть дана СЛС (2). Запишем ее в матричном виде:

Расширенную матрицу СЛДУ (2) расширим вторично, приписав к ней снизу единичную матрицу размерности n´n и нулевую матрицу размерности n´1. Получим дважды расширенную матрицу СЛДУ:

.

Преобразуем матрицу A к каноническому виду D, выполняя элементарные целочисленные приведенные преобразования над первыми m строками и первыми столбцами n матрицы . Тогда матрица B перейдет в матрицу F = U₁B, где U₁ — произведение элементарных матриц, соответствующих элементарным преобразованиям строк. Единичная матрица E¢ перейдет в матрицу U₂, где U₂ — произведение элементарных матриц, соответствующих элементарным преобразованиям столбцов. Получим матрицу:

.

Полученной матрице соответствует матричное уравнение:

(5)

Если хотя бы один из элементов f_{r + 1} ,…, f_m не сравним с нулем по mod m, или хотя бы одно из чисел f_k не делится на D_k =НОД(d_kk, m), (k =1, 2, …, r), то система (5), а поэтому и система (2) не имеют решений. Если же

.

Так как Y = U₂ -1 X, то отсюда находим

Пример 3. Решить СЛC:

Решение. Составим дважды расширенную матрицу и приведем ее к каноническому виду:

.

Отсюда приходим к системе сравнений вида (5):

где t Î Z₁₂. Таким образом, получаем решения сравнения:

.

Случай, когда дана СЛУ с различными модулями решается более сложно. Рассмотрим СЛС простейшего вида с одним неизвестным:

(6)

но с различными и попарно взаимно простыми модулями.

Тогда совокупность всех значений x, удовлетворяющих системе (5), определяется сравнением

Доказательство.Для любого j ¹ s все M_j делятся на m_s. Тогда отсюда и из (7) следует, что

Тогда система (6) равносильна системе:

Так как числа m₁,…, m_k – попарно взаимно простые, то система (10) равносильна сравнению (9).ÿ

Из теоремы 3 следует, что для любых попарно взаимно простых целых чисел m₁,…, m_k и любых целых чисел r₁,…, r_k где 0 £ r₁ n + a₁x n — 1 +…+a_n Î Z[x], a₀ T 0(mod p). Рассмотрим сравнение

Так как кольцо классов вычетов Z_p по простому модулю p является полем, то рассматривая сравнение (1) как уравнение над конечным полем Z_p, можем применить к сравнению (1) всю теорию многочленов над конечным полем и получаем следующие теоремы.

Теорема 1.Любое сравнение вида (1) равносильно нулевому сравнению или сравнению степени не большей p-1.

Доказательство.Разделим многочлен f (x) на многочлен x p – x с остатком

где – нулевой многочлен или многочлен степени не выше p-1. Так как по теореме Ферма для любого целого числа a

то сравнение (1) равносильно сравнению

Теорема 2.Число x₀ удовлетворяет сравнению (1) тогда и только тогда, когда

Теорема 3.Если число решений сравнения (1) больше чем n решений, то все его коэффициенты делятся на p.

Доказательство.Допустим, что сравнение (1) имеет, по крайней мере, n + 1 решений. Обозначим числами x₁, x₂, …, x_n+1 вычеты этих решений. Деля многочлен f (x) с остатком последовательно на двучлены x — x₁, x — x₂, …, x — x_n представим многочлен f (x) в виде:

Следствие.Если a₀ T 0(mod p), то число решений сравнения (1) не больше степени сравнения.

Доказательство.Допустим, что сравнение (1) имеет более чем n решений, то все его коэффициенты делятся на p. Тогда a₀ º 0(mod p), и получили противоречие с условием.ÿ

Теорема 4(теорема Вильсона).Число p простое, тогда и только тогда, когда справедливо сравнение

Доказательство.Длячисла p = 2 сравнение выполняется. Пусть p – нечетное простое число. Тогда по малой теореме Ферма следует, что сравнение

имеет p -1 решений `0, `1 ,…, `p-1. Тогда по теореме 2 получим:

Отсюда при x º 0(mod p) следует формула (4).ÿ

равносильно системе сравнений

(6)

при этом, число T решений сравнения (5) равно

где T₁,…, T_k – обозначают соответственно число отдельных решений сравнений системы (6).

Доказательство.Первая часть теоремы 1 следует из свойства делимости на взаимно простые числа:число a делится на m тогда и только тогда, когда оно делится на каждый из взаимно простых множителей m₁,…, m_k числа m.

Пусть теперь все попарно различные решения соответственно сравнений системы (6). Тогда для каждого набора чисел ; i=1,…,T₁;…; j=1,…,T_k по формуле (8) предыдущего параграфа находится число, удовлетворяющее всем сравнениям системы (6), т.е. удовлетворяющее системе (5). При этом все полученные числа попарно несравнимы по модулю m. Таким образом система (6) имеет T = T₁… T_k решений.ÿ

Пусть — каноническое разложение числа m. В виду теоремы 5 исследование и решение сравнения

(7)

сводится к исследованию и решению сравнений:

. (8)

Поэтому рассмотрим сравнение вида:

, (9)

где p – простое число. Покажем, что решение этого сравнения сводиться к решению сравнения (1).

Теорема 6.Всякое решение x º x₁ (mod p) сравнения (1) при условии, что f´(x₁) не делится на p, даст одно решение сравнения (9):

(10)

Доказательство.Так как всякое число x, удовлетворяющее сравнению (9) удовлетворяет и сравнению (1), то x º x₁ (mod p), где x₁ – какое-нибудь решение сравнения (1).

Обратно, пусть x₁ – любое решение сравнения (1), x º x₁ (mod p). Тогда x = x₁ + pt₁, где t₁ – целое число. Подставляем это значение x в сравнение

(11)

и применяем формулу Тейлора n-го порядка, получим:

Заметим, что в этой формуле все коэффициенты в формуле целые числа и последние n – 2 членов делятся на p. Тогда сравнение (11) принимает вид:

Так как f´(x₁) не делится на p, то последнее сравнение имеет единственное решение

где t₂ – целое число. Тогда выражение для x принимает вид

где t₂ – целое число. Подставляя это значение x в сравнение

(12)

где t₃ – целое число. Тогда выражение для x принимает вид

Продолжая эти рассуждения, получим справедливость утверждения теоремы.ÿ

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

f(x) = 2x 3 — x 2 + 3x +2 º 0 (mod 225). (13)

Так как 225 = 3 2 5 2 , то сравнение равносильно системе сравнений:

(14)

методом испытаний, выполняя проверку по схеме Горнера:

Первое сравнение имеет 1 решение x º 1(mod 3), второе сравнение имеет 1 решение x º 2(mod 5). Далее

f´ (1) = 7 º 1 T 0(mod 3),

f´ (2) = 24 – 4 + 3 = 23 º 3 T 0(mod 5),

то каждое из сравнений (14) и сравнение (13) имеет по одному решению.

Решая первое из сравнений (14) положим x = 1 + 3t₁, где t₁ – целое число. Подставляем это значение x в сравнение, получим

Решая второе из сравнений (14) положим x = 2 + 5t₁, где t₁ – целое число. Подставляем это значение x в сравнение, получим

Все решения сравнения (13) являются решениями системы сравнений:

M₂´ º 9 19 º 9× (9 2 ) 9 º 9×6× (6 2 ) 4 º 4× (11 2 ) 2 º 4× 4 2 º -4×9 º -11 (mod 25),

Тогда число x₀ вычислим о формуле:

Ответ: .