Делимость и деление с остатком в кольце целых чисел.

Делимость — одно из основных понятий арифметики и теории чисел, связанное с операцией деления. С точки зрения теории множеств, делимость целых чисел является отношением, определённым на множестве целых чисел.

Говорят, что число a делится на b, существует такое целое число q, для которого a = qb.
Для отношения делимости справедливы следующие свойства.
Свойство 1. Если a делится на b и b делится на c, то a делится на c.
Свойство 2. Если a₁, …, a_n делятся на b, то и a₁ + … + a_n делится на b.

Свойство 3. Если a₁ делится на b₁, …, a_n делится на b_n, то и a₁…a_n делится на b₁…b_n.

 

Основная теорема арифметики.

Любое целое число можно представить в виде простых чисел (делятся только на себя и на 1), с точностью до порядка.

 

Взаимно простые числа – их НОД = 1.

 

Кольца вычетов.

Два целых числа a и b сравнимы по модулю натурального числа n, если при делении на n они дают одинаковые остатки. Число n называется модулем сравнения.

Эквивалентные формулировки: a и b сравнимы по модулю n, если их разность a-b делится на n без остатка, или если a может быть представлено в виде a = b + kn, где k — некоторое целое число.

Утверждение «a и b сравнимы по модулю n» записывается в виде:

Отношение сравнимости по модулю натурального числа обладает следующими свойствами:

§ рефлексивности: для любого целого справедливо

§ симметричности: если то

§ транзитивности: если и то

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

Любые два целых числа сравнимы по модулю 1.

- (и вычитать, и умножать тоже)

- ; d – общий делитель чисел a, b, m

- ; a, b делятся на d, (d, m)=1

 

 

Системы вычетов.

– классы вычетов, а элементы – вычетами по модулю m.

Числа из одного класса сравнимы по модулю m, из разных – не сравнимы.

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

0, 1, ……, m – 1 - полная система вычетов по модулю m (полная система наименьших неотрицательных вычетов)

Если в классе вычетов по модулю m есть одно число, взаимно простое с m, то в нем все числа взаимно просты с m.

Класс вычетов по модулю m, состоящий из чисел, взаимно простых с m, называется классом, взаимно простым с модулем m.

Совокупность классов, взятых по одному из всех классов, взаимно простых с модулем m, называется приведенной системой вычетов по модулю m. (для 8 – представители соответствующих классов 1, 3, 5, 7 образуют приведенную систему вычетов по модулю 8)

Число чисел в приведенной системе вычетов по модулю m (число классов, взаимно простых с m) определяют функцией Эйлера.

φ (2) = 1, φ (3) = 2, φ (4) = 2, φ (5) = 4, φ (6) = 2

φ (p) = p – 1, p – простое число

φ (p^k) = p^k – p^k-1

φ (mn) = φ (m) φ (n)

Если число m имеет каноническое разложение (представимо в виде произведения взаимно простых с ним чисел):

то:

Если a₁, a₂, …, a_{φ (m)} есть приведенная система вычетов по модулю m и число m взаимно просто с a, то набор чисел aa₁, aa₂, …, aa_{φ (m)} также является приведенной системой вычетов по модулю m.

 

Теорема Эйлера. Если a и m взаимно просты, то:

a^{φ (m)}≡ 1 (mod m)

Если m = p – простое число, то φ (p) = p – 1

a^p-1≡ 1 (mod m)

 

Уравнения в кольце вычетов и сравнения с неизвестным.

Пусть a_nxⁿ + a_n-1x^n-1 + … + a₁x¹ + a₀ ≡ 0 (mod m) есть сравнение, в котором a₀, ­a₁, …, a_n ∈ Z, а x – неизвестное.

 

Если некоторое целое число х – есть решение сравнения x≡ y(mod m), то y также есть решение сравнения. Иначе говоря, если целое число х удовлетворяет сравнению, то ему удовлетворяют и все числа класса [x]_m. В связи с этим весь этот класс называют одним решением по модулю m, а число различных классов целых чисел, удовлетворяющих сравнению, - числом решений по модулю m.

 

Если m = m₁m₂, и (m₁, m₂)=1, то исходное сравнение равносильно системе сравнений:

a_nxⁿ + a_n-1x^n-1 + … + a₁x¹ + a₀ ≡ 0 (mod m₁)

a_nxⁿ + a_n-1x^n-1 + … + a₁x¹ + a₀ ≡ 0 (mod m₂)

Третье свойство с учетом наличия канонического разложение числа m на простые множители позволяет свести решение к более простым модулям.

Пример:

13x + 40 ≡ 71x +2 (mod 35)

13x + 5 ≡ x + 2 (mod 35) (40%35 = 5, 71%35=1)

12x ≡ -3 (mod 35)

3x ≡ 8 (mod 35)

решение первого – x = [1]₅, второго – x = [5]₇. Решение системы – общие представители этих классов:

x∈ [1]₅ ⋂ [5]₇

[1]₅ ⋂ [5]₇ = [26]₃₅

x = [26]₃₅

 

 

Кольцо многочленов.

 

a_nxⁿ +a_n-1x^n-1 + … + a₁x + a₀ – типа многочлен от х над кольцом R. Обозначается как a(x). Множество всех многочленов от x над кольцом R обозначается через R[x]

многочлены вида a_ixⁱ_, i = 0, 1, …, n – члены многочлена, a₀, a₁, … a_n – коэффициенты, a₀ – свободный член. Если a_n ≠ 0, а все коэффициенты с большими индексами равны нулю, то n – степень многочлена, а а_n – старший коэффициент.

Если ненулевым является только свободный член, то, как следует из определения, степень соответствующего многочлена равна нулю. Если нулевыми является все коэффициенты и свободный член, то соответствующий многочлен a(x) называется нулевым и записывается как а(х) = 0. Степень нулевого многочлена равна -∞.

Степень многочлена а(х) обозначается как deg a(x) (degree). многочлен со старшим коэффициентом. равным единице, называется унитарным или каноническим.

На множестве R[x] могут быть определены операции сложения и умножения.

a(x) =a_nxⁿ +a_n-1x^n-1 + … + a₁x + a₀

b(x) = b_mx^m +b_m-1x^m-1 + … + b₁x + b₀

c(x) = c_nxⁿ +c_n-1x^n-1 + … + c₁x + c₀, c_i = a_i + b_i, n = max(n, m)

 

a(x) =a_nxⁿ +a_n-1x^n-1 + … + a₁x + a₀

b(x) = b_mx^m +b_m-1x^m-1 + … + b₁x + b₀

d(x) = d_kx^k +d_k-1x^k-1 + … + d₁x + d₀

 

 

Эти операции – внутренние бинарные на множестве R[x], т.к. с(х) и d(x) принадлежат R[x]. Операция сложения ассоциативна и коммутативна. Нулевым элементов в R[x] является многочлен 0. Противоположным к

a(x) =a_nxⁿ +a_n-1x^n-1 + … + a₁x + a₀

является

-a(x) = -a_nxⁿ -a_n-1x^n-1 - … - a₁x - a₀

Нейтральный по умножению – 1.

 

Приводимые многочлены – разлагаются в произведение многочленов двух меньших степеней

Не приводимые – не разлагаются.

 

⇐ Предыдущая123456789Следующая ⇒

Поделиться: