Сравнения и системы сравнений с неизвестной величиной

§1. Решение сравнений. Равносильные сравнении

Пусть многочлены f(x),g(x)€ Z[x]. Будем рассматривать сравнения вида f(x)=g(x)(mod m), которые называют алгебраическими. Если в такое сравнение вместо х подставлять различные целые числа, то получится верное числовое равенство.

Теорема 1. Если число с удовлетворяет сравнению

f(x)≡g(x)(mod m), (1). j

то и все числа из класса с удовлетворяют этому сравнению.

Доказательство. Пусть b ≡ c(mod m). Тогда b^k ≡с^k (mod m), k = 0,1 2,...; a_kb^k ≡ a_kc^k(mod m). Складывая такие сравнения, получим, что f(b) ≡ f(c)(mod m), g(b) ≡ g(c)(mod m). А так как по условию, f(c) ≡ g(c)(mod m), то по транзитивности f(b) ≡g(b)(mod m) и b

удовлетворяет (l). Таким образом вместе с с любое число класса с тоже удовлетворяет сравнению (1).

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

Числом решений сравнения называют число классов чисел, удовлетворяющих сравнению. Так как классов по модулю m конечное число, то для решения сравнения (1) достаточно взять полную систему вычетов по модулю m и отобрать те классы, представители которых удовлетворяют (1).

Примеры.

1. x³-2x+6≡0(mod 11). Непосредственная проверка показывает, что в полной системе наименьших по абсолютной величине вычетов - 5, -4, -3, -2, -1,0, 1,2, 3, 4, 5 сравнению удовлетворяет только одно число 5. Решение записываем в виде х ≡ 5(mod ll).

2. Х⁴ + 2х² + 6 ≡ 0(mod 8). В полной системе вычетов -3, -2,-1, 0,1,2,3,4 ни одно число не удовлетворяет сравнению, и, следовательно, сравнение не имеет решений.

3. Х³- х ≡0(mod 3). Этому сравнению удовлетворяет любое число (по т. Ферма). Сравнение имеет 3 решения — классы 0,1,2.

Определение. Пусть f(x), g(x), f₁ (x), g₁ (x) € Z[x]. Сравнения f(x) ≡ g(x)(mod m) и f₁ (x) ≡g₁(x)(mod m) называются равносильными (эквивалентными), если множества чисел, удовлетворяющих этим сравнениям, совпадают.

Теорема 2.

1) Если к обеим частям сравнения f(x) ≡ g(x)(mod m) прибавим любой многочлен u(х)€ Z[x], то получим сравнение, равносильное первоначальному.

2) Если обе части сравнения f(x) ≡ g(x)(mod m) умножим на одно и то же число, взаимно простое с модулем, то получим сравнение, равносильное первоначальному.

3) Если обе части сравнения и модуль умножим на одно и то же натуральное число, то получим сравнение, равносильное первоначальному.

Доказательство.

1) Из свойств сравнений f(с) ≡ g(c)(mod m) тогда и только тогда, когда f(с)+u(с)≡ g(c)+ u(c)(mod m). Поэтому любое число, удовлетворяющее сравнению f(x) ≡ g(x)(mod m), удовлетворяет и сравнению f(х)+ u(x) ≡ g(x)+ u(mod m) и наоборот, любое число, удовлетворяющее второму сравнению, удовлетворяет первому.

2) Если при некотором с f(c)≡g(c)(mod m), k€Z, то kf(c) ≡ kg(c)(mod m). А из kf(c) ≡kg(c)(mod m) следует

F(c)≡g(c)(mod m), если (k,m)=1 (свойства сравнении 6 и 13). Итак, при (k,m)= 1 число удовлетворяет сравнению f(x)≡ g(x)(mod m) тогда и только тогда, когда оно удовлетворяет kf(x) ≡ kg(x)(mod m).

3) Из свойств сравнений 11 и 12: если k€ N, то f(с) ≡ g(c)(mod m) тогда и только тогда, когда kf(c) ≡ kg(c)(mod km). Поэтому множества чисел, удовлетворяющих сравнениям f(x)≡g(x)(mod m) и kf(х)≡ kg(x)(mod km) совпадают.

Из теоремы 2 (пункт 1) следует, что сравнение f(x) ≡ g(x)(mod m) можно заменить равносильным сравнением f(x)- g(x) ≡ 0(mod m). Поэтому в дальнейшем достаточно рассматривать сравнения вида F(x)≡ 0(mod m), (F(x)=f(x)-g(x)).

Теорема 3. Пусть f(x)=a₀ +а₁x+...+а_nxⁿ и g(x)=b₀ + b₁ x+... + b_n xⁿ- многочлены с целыми коэффициентами. Если a₀ ≡ b₀ (mod m), a_1≡b₁(mod m),..., а_n ≡ b_n (mod m), то сравнения f(x)≡ 0(mod m) и g(x) ≡ 0(mod m) равносильны.

Доказательство. Умножим сравнения a_0≡b₀ (mod m), а₁ ≡b₁(mod m), …, a_n ≡b_n(mod m) соответственно на 1, x₀,X₀,²..., x₀ⁿ. Складывая полученные cравнения, имеем: f(х₀) ≡ g(x₀)(mod m). Обе части этого сравнения могут только одновременно быть сравнимы с нулём по модулю m. Таким образом, сравнения f(x) ≡ 0(mod m) и g(x)≡ 0(mod m) равносильны.

Пример. Сравнения 17x¹⁵+20х¹⁰ +12х⁵ + 6x⁴ +1 ≡ 0(mod 3) и 2х¹⁵ –x¹⁰ + 1≡ 0(mod3) равносильны, так как 17 ≡ 2, 20 ≡ -1,12 ≡ 0, 6 ≡0 по модулю 3.

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

Определение. Степенью сравнения f (x)≡0(mod m) называют степень многочлена f(x), если старший коэффициент f(x) не делится на m.

Пример. Степень сравнения 14x¹² -З5x⁷-10х² -3 ≡ 0(mod7) равна двум, так как 14:7, -35:7, а само сравнение равносильно Зх² -3 ≡ 0(mod7).