Файл: Учебнометодический комплекс Для студентовбакалавров, обучающихся по направлению.doc

Глава 5. Теория делимости в кольце Z.

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

• 
  знать определения отношений делимости без остатка и с остатком и их свойства;
  
• 
  знать определения НОК, НОД, их связь, свойства и методы нахождения;
  
• 
  знать алгоритм Евклида и уметь использовать его для нахождения НОД двух целых чисел;
  
• 
  знать и уметь находить каноническое разложение натурального числа на простые множители.
  

§1. Отношение делимости в Z и его свойства.

Определение 1. Целое число (а) делится на целое число (b0), если  q  Z : a=bq

Обозначается: a/b и читается "а делится на b", или "b делит а".

а – делимое,

b – делитель,

q – частное.

Это отношение есть частичная бинарная операция на Z, т.к. . Например, 4 не делится на 3. С другой стороны, это отношение будет трехместным предикатом на множестве Z.

Свойства:

1. Отношение делимости рефлексивно. Действительно:  a  Z а/а, т.к.  1  Z : а = а  1

2. Отношение делимости транзитивно. Действительно:

" a, b, c Î Z (a/b & b/c) => (а/с), т.к. из того что (a/b) 

 q₁  Z : a=bq₁, а из того что (b/c)   q₂  Z : b=cq₂, тогда

а = cq₂q₁ = cq₃ => (а/с)

3. Отношение делимости антисимметрично, т.к. " a, b Î Z из того что (а/b & b/а) => [(а= b) v (a = -b)]

Следовательно, отношение делимости не является отношением эквивалентности, а будет отношением частичного порядка на множестве Z.

Определение 2. Целое число (а) делится на (bZ & b0) с остатком, если  q, r  Z : а = bq + r, где 0 < r < |b| а – делимое.

b – делитель, q - неполное частное, r — остаток.

Замечание 1. Из определения следует, что остаток всегда число неотрицательное.

Пример 1. Разделить - 49 на 17. Получим: - 49 = 17 • (-3)+2

Теорема 1. В кольце Z любое целое число (а) можно разделить на целое число (b0) с остатком, единственным образом.

1. Покажем возможность деления.

Пусть bq - наибольшее кратное числа b, которое не превосходит (а), тогда bq  а b(q+l) => 0 a-bq  b положим, что a-bq = г, тогда получим, что а = bq + r, где 0< r <|b|.

---

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

Пусть a=bq₁+r₁, 01<|b| и а= bq₂+r₂ 0< r₂ <|b| =>

=> b(q₁ -q₂) = (r₁-r₂) => (r₂-r₁)/b , а т.к. |r₂-r₁|<|b| =>

=> (r₂-r₁) = 0 => (r₂ = r₁)

Т.к. b¹0 то из равенства b(q₁-q₂) = 0 => (q₁-q₂) = 0 => (q₁ = q₂).

§2.НОД(а, b), HOK(a, b). Алгоритм Евклида.

Определение 1. Целое число dZ, (d¹0) называется общим делителем чисел a₁,а₂,..a_k,если каждое a_i(i=1,2,..., к) делится на d.

Определение 2. Целое число dZ, (d¹0) называется наибольшим общим делителем чисел a₁,а₂,... ,а_к если:

1 d - общий делитель всех а_i

2. d - делится на любой другой общий делитель этих чисел

Обозначение: НО Д (a₁ ,а₂,. . a_k)= d или (а₁ ,а₂,…,a_k) = d

Пример 1. Даны числа: 4, 8, 12, 16, 20, 24, 48

Числа 2 и 4 являются общими делителями этих чисел Число 4 является наибольшим общим делителем данных чисел, т е НОД (4, 8, 12, 16, 20, 24, 48) = 4

Задача 1. Доказать, что d = (a, b) определяется однозначно с точностью до знака.

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

Пусть d₁ = (a, b) & d₂ = (a, b) => (d₁ / d₂)&(d₂ / d₁) => [(d₁ = d₂) v (d₁ = -d₂)].

Замечание 1. Обычно берется положительное значение d = (a,b).

Существует метод, который позволяет доказать существование НОД (а, b) и находить его для любой пары целых чисел, его называют алгоритмом Евклида. Он основан на двух леммах:

Лемма 1. Если (а /b), то (a,b)=b.

Лемма 2. Если а = bq + г, где а, b, r  0, то (а, b) = (b, r).

Алгоритм Евклида.

1 Шаг. Делим а на (b¹0), если а /b, то (a, b) = b по лемме 1, если а = bq₀ + r₁, то (a, b)=(b, r₁)

2Шаг. Делим b на r₁ если (b /r₁) => (b, r₁) = r₁, если b = r₁q₁+r₂, то (b, r₁) = (r₁, r₂).

3 Шаг. Делим r₁ на r₂и т. д.

Поскольку остатки, получаемые в процессе деления, убывают и являются натуральными числами, то на каком-то шаге получим остаток, равный нулю, т.е. r_n-1 = r_nq_n и тогда (r_n-1, r_n) = r_n.

Задача 2. Доказать, что последний неравный нулю остаток в алгоритме Евклида является наибольшим общим делителем чисел (а) и (b).

Решение: Применим к числам (а) и (b) алгоритм Евклида:

a = bq_o+r₁ 0r₁
b = r₁q₁ + r₂ 0 r₂ 1

. . . . . . . . . . . . . . . . . . . . .

r_n-2=r_n-1•q_n-1 +r_n 0 r_nn_-1

r_n-1 =r_nq_n + 0

Из первого равенства по лемме 2 будем иметь:

(a, b) = (b, r₁)

Из второго равенства алгоритма Евклида тоже по лемме 2 будем иметь (b, r₁)= (r₁ г₂) и т. д.

Из последнего равенства (r_n-1 , r_n) = r_n по лемме 1. Т.е. получили цепочку равенств (а, b) = (b, r₁) = (r₁, r₂) = (r₂, r₃) = …..

=(r_n-2, r_n-1) = (r_n-1, r_n) = r_n

Итак, (а, b)=r_n.

Пример 2. Найти d = (3220,1550) с помощью алгоритма Евклида

Решение:


Итак, (3220, 1550) = 10 = r₂

Задача 3. Доказать, что если d=(а,b), то х, у Z :

d = ах + by.

Решение:

Применим к числам а и b алгоритм Евклида:

а = bq₀ + r₁

b = r₁ q₁ + r₂

r_i = r₂q₂ + r<sub>3

……………………</sub>

r_n-3 = r_n-2q_n-2 + r_n-1

r_n-2 = r_n-1q_n + d, (d = r_n)

Тогда, последовательно выражая, из последнего равенства, d = r_n-2 - r_n-1 q_n (*) из предпоследнего r_n-1 = r_n-3 – r_n-2q_n-2 и т.д.

Из первого r₁ = а-bq_o и последовательно подставляя их в равенство (*) получаем: d = ах + by.

1   ...   5   6   7   8   9   10   11   12   ...   16

---

§3. Взаимно простые числа и их свойства.

Определение1. Целые числа а₁ ,а₂,…,a_kназываются взаимно-простыми, если (а₁ ,а₂,…,a_k )=1

Определение 2. Целые числа а₁ ,а₂,…,a_k называются попарно взаимно-простыми, если i,s (i, s = 1, 2, .. , к, is, (а_i, а_s) =1).

Если числа удовлетворяют определению 2,то они удовлетворяют и определению 1. Обратное утверждение в общем случае неверно, например: (15, 21, 19)= 1, но (15, 21) = 3

Теорема (критерий взаимной простоты)

(а, b) = 1 <=>  х, у Z: ах + by = 1

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

Докажем необходимость. Пусть (а, b) = 1. Выше мы показали, что если d=(a,b), то  х, y Z : d = ax +by.

Т.к. в этом случае d =1, то будут  х, y Z (определяемые из алгоритма Евклида): 1 = ах + bу.

Достаточность. Пусть (*) ах + by = 1, докажем, что (а, b)=1. Предположим, что (a, b) = d, тогда в левой части равенства (*)

(a /d) & (b /d) => (ах + by) /d => (1/d) => (d=l) => (a, b) = 1.

§4. НОК целых чисел и его свойства.

Определение 1. Общим кратным конечного множества целых чисел а₁ ,а₂,…,a_k, отличных от нуля, называют целое число m, которое делится на все числа a_i (i=l, 2,…, к)

Определение 2. Целое число (m) называется наименьшим общим кратным чисел а₁ ,а₂,…,a_k, отличных от нуля, если:

1 m - является их общим кратным;

2 (m) делит любое другое общее кратное этих чисел.

Обозначение: m = НОК (а₁ ,а₂,…,a_k) или m = [а₁ ,а₂,…,a_k]

Пример. Даны числа: 2, 3, 4, 6, 12.

Числа 12, 24. 48. 96 являются общими кратными чисел 2, 3, 4, 6, 12 Наименьшим общим кратным будет число 12. т.е.

[2, 3, 4, 6, 12] = 12

НОК определяется однозначно с точностью до порядка следования сомножителей. Действительно, если предположить, что m₁= [а, b] &m₂ = [a, b]  (m₁ / m₂) & (m₂/m₁) => [(m₁ = m₂) v (m₁= - m₂)]. Между наименьшим общим кратным и наибольшим общим делителем двух целых чисел существует зависимость, которая выражается формулой: [а, b] = ab/(а, b) (выведите ее самостоятельно)

Эта связь позволяет утверждать, что для любой пары целых чисел, отличных от нуля, существует их наименьшее общее кратное. Действительно, (а, b) – всегда можно однозначно вывести из алгоритма Евклида и по определению (а, b)  0, тогда дробь ab/(а, b)  0 и будет определена однозначно.

---

Наиболее просто НОК двух целых чисел вычисляется в том случае, когда (а,b)= 1, тогда [а, b] = ab/1 = а • b

Например, [21, 5] = 215/1 = 105, т. к. (21, 5) = 1.

§5. Простые числа и их свойства.

Определение 1. Натуральное число (р) называется простым, если р > 1 и не имеет положит. делителей, отличных от 1 и р.

Определение 2. Натуральное число а >1, имеющее кроме 1 и самого себя другие положительные делители, называется составным.

Из этих определений следует, что множество натуральных чисел можно разбить на три класса:

а) составные числа;

б) простые числа;

в) единица.

Если а - составное, то а = nq, где 1
Задача 1. Доказать, что если aZ и р - простое число, то (а, р) = 1 v (a / р)

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

Пусть d = (а, р) => (a /d) & (р /d), т.к. р - простое число, то оно имеет два делителя 1 и р. Если (а, р) = 1, то а и р взаимно просты, если (а, р) = р, то (а/р).

Задача 2. Если произведение нескольких сомножителей делится на р, то по крайней мере один из сомножителей делится на р.

Решение.

Пусть произведение (а₁,а₂,...,а_k)/р, если все a_i не будут делиться на р, тогда и произведение будет взаимно просто с р, следовательно, какой-то сомножитель делится на р.

Задача 3. Доказать, что наименьший отличный от 1 делитель целого числа а>1, есть число простое.

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

Пусть aZ и а - составное число (если а = р, то утверждение доказано), тогда а = a₁q.

Пусть q - наименьший делитель, покажем, что он будет простым числом. Если предположить, что q - составное число, тогда q = q₁k и а = a₁•q₁k, т.к. q₁
Задача 4. Доказать, что наименьший простой делитель (р) натурального числа (n) не превосходит n .

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

Пусть n = рn₁, причем р < n₁ и р - простое. Тогда n  р² => р<n .

Из этого утверждения следует, что если натуральное число (n) не делится ни на одно простое число р n , то n – простое, в противном случае оно будет составным.

Пример 1. Выяснить, будет ли число 137 простым? 11 <137 <12.

---

Выписываем простые делители, не превосходящие 137: 2, 3, 5, 7, 11. Проверяем, что 137 не делится на 2, на 3, на 5, на 7, на 11. Следовательно, число 137 – простое.

Теорема Евклида. Множество простых чисел бесконечно.

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

Предположим противное, пусть p₁,p₂,...,p_k все простые числа, где p₁ = 2, а p_k – самое большое простое число.

Составим натуральное число  = p₁p₂ ...p_к +1, т.к.  p_i , то оно должно быть составным, тогда его наименьший делитель будет простым (см. задачу 3). Однако  не делится ни на p₁ , ни на p₂ ,…, ни на p_k , т.к. 1 не делится на любое p_I.

Следовательно, наше предположение о конечности множества простых чисел было неверно.

Однако существует теорема, которая утверждает, что простые числа составляют лишь небольшую часть чисел натурального ряда.

Теорема об интервалах. В натуральном ряду существует сколь угодно длинные интервалы, не содержащие ни одного простого числа.

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

Возьмём произвольное натуральное число (n) и составим последовательность натуральных чисел (n+1)!+2, n+1)!+3,…,(n+1)!+(n+1).

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

Теорема Евклида и теорема об интервалах свидетельствуют о сложном характере распределения простых чисел в натуральном ряду.

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

Любое натуральное число n>1 может быть представлено единственным образом в виде произведения простых чисел, с точностью до порядка следования сомножителей.

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

Докажем возможность представления:

Пусть nN и n>1, если n – простое число, то n = p и теорема доказана. Если n – составное, то наименьший его делитель будет числом простым и n = p₁n₁, где n₁
Далее рассуждаем аналогично. Если n₁ простое число, то теорема доказана, если n₁

---