I. Основы теории чисел алгебраические операции на множестве целых чисел




Скачать 146.52 Kb.
НазваниеI. Основы теории чисел алгебраические операции на множестве целых чисел
Дата публикации16.08.2013
Размер146.52 Kb.
ТипДокументы

Глава I. Основы теории чисел



§1.1. Алгебраические операции на множестве целых чисел.

Делимость целых чисел



Наиболее популярными числовыми множествами являются следующие:

N – множество натуральных чисел,

Z – множество целых чисел,

Q – множество рациональных чисел,

R – множество вещественных чисел,

C – множество комплексных чисел.

Они связаны следующим отношением включения: NZQRC.

Отношения >, <,  и  полностью упорядочивают множество R. Если A  R и a  A, то в дальнейшем будем обозначать A>a, A<a, Aa и Aa подмножества A, состоящие из всех чисел, больших a, меньших a, больших или равных a и меньших или равных a соответственно.

Множество целых чисел Z – счетное, состоит из элементов 0, 1, 2,…, n,… На нем определены две алгебраические операции – сложение и умножение. Эти операции обладают следующими общими свойствами (для любых a, b, c  Z):

  1. ассоциативность: , ;

  2. коммутативность: , ;

  3. существуют нейтральные элементы – 0 относительно сложения и 1 относительно умножения соответственно: , .

Кроме того, операция сложения обладает свойством:

  1. для каждого существует единственное такое, что: .

Ясно, что здесь – противоположное целое. Это свойство позволяет ввести на Z вспомогательную операцию – вычитание. – целое число – разность чисел a и , получаемое вычитанием из a.

Умножение и сложение связаны свойством:

5.  – закон дистрибутивности умножения относительно сложения.

Аналог свойства 4 для умножения выполняется лишь для двух целых чисел: 1 и –1.

Вообще говоря, для каждого целого существует обратное относительно умножения (то есть такое число , что ), но оно является рациональным и не обязательно целым числом. Следовательно, результат операции деления целого числа a на целое число есть число рациональное и в редких случаях является целым. В общем же случае имеет место следующая теорема.

Теорема 1.1.1 (о делении с остатком). Для любых целых чисел a и , , существуют единственные целые числа и , 0  r < | b |, такие, что

. (1.1.1)

Доказательство существования.

1. . В этом случае q = r = 0.

2. .

(вычитаем из a b столько раз, чтобы получилось число 0 или число r < b), .

3. .

, .

4. .

.

5. .



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

Пусть a = bq1 + r1 и a = bq2 + r2. Вычтем из 1-го равенства 2-е:

0 = bq1 – bq2 + r1 – r2,

b(q2 – q1) = r1 – r2.

Пусть q1  q2, тогда | r1 – r2 |  | b |, но 0  r1r2 < | b |,  | r1 – r2 | < | b |. Значит, q1 = q2, поэтому и r1 = r2.

Определение 1.1.1. В равенстве (1.1.1) называют остатком, а частным (неполным частным при ) от деления a на .

Для нахождения частного и остатка можно использовать метод деления «уголком».

Пример 1.1.1.

1

.
 .

.

2. .

203 = 16  12 + 11;

–203 = 16  (–12) – 11 = 16  (–12) – 16 + 5 = 16  (–13) + 5;

.





3. .

1

78 = 11  16 + 2;

–178 = (–11)  16 – 2 = (–11)  16 – 11 + 9 = (–11)  17 + 9;

.

4. .

7

25 = (–53)  (–13) + 36;

.

Определение 1.1.2. Если в равенстве (1.1.1) , то есть , то говорят, что a делится на (и пишут ), что a является кратным числа , что делит a (и пишут b | a), а также называют делителем или множителем числа a. Все вышесказанное для b справедливо и для q при q  0. Будем обозначать , если а не делится на b, и ba, если не делит a.

Свойства делимости целых чисел

1.  для : действительно, .

2.  для , поскольку и .

3.  (свойство транзитивности).

a = bq, c = at = bqt = bs, где qts  Z.

4. .

, , ,  q = t = 1  q = t = – 1  a = ba = – b

a | = | b |.

5. ,…, для , .



6. Если в равенстве , все слагаемые, принадлежащие Z, делятся на d, кроме, быть может, одного ai, , то и это слагаемое также делится на d.

. По свойству 5 d | ai.

7. b | a  | b | | | a |.

, , 

, t = 1, a  0,  , a = 0,  | b | | | a |.

^

§1.2. Наибольший общий делитель целых чисел. Алгоритм

Евклида. Соотношение Безу. Наименьшее общее кратное



Определение 1.2.1. Если целые числа а1, а2,…, аn, n  2, делятся на целое d  0, то d называют их общим делителем (ОД).

В дальнейшем речь пойдет только о положительных целых делителях.

Определение 1.2.2. Максимальный из общих делителей целых чисел а1, а2,…, аn, хотя бы одно из которых отлично от нуля, называется их наибольшим общим делителем (НОД) и обозначается НОД(а1, а2,…, аn) или (если это не вызывает разночтений) (а1, а2,…, аn).

Свойства НОД

1. d  N.

2. d | ai, .

3. Для  :  | ai, ,   | d.

Определение 1.2.2 НОД целых чисел а1, а2,…, аn равносильно выполнению свойств 1–3.

4. НОД целых чисел единственный.

Пусть d и d1 – два НОД целых чисел а1, а2,…, аn, n  2. Тогда по свойству 3 НОД d1 | dd | d1  | d | = | d1 | по свойству 4 делимости целых чисел. Так как dd1  N, то d = d1.

Очевидно, что если b | a, то (ab) = | b |.

Теорема 1.2.1. Если , то (ab) = (br).

По свойству 6 делимости целых чисел – ОД b и r, По свойствам 5, 6 делимости целых чисел (br) – ОД a и b, Согласно свойству 4 делимости целых чисел, поскольку

Это наблюдение (теорема 1.2.1) позволило выдающемуся древнегреческому математику Евклиду (III в. до н.э.) обосновать следующий факт, являющийся по сути кратным применением теоремы 1.2.1.

Теорема 1.2.2 (Евклид). Наибольший общий делитель целых чисел a и b при условии, что | a | > | b |, , равен последнему отличному от нуля остатку от деления в цепочке равенств:

a = b  q1 + r1,

b = r1  q2 + r2, если ,



rn  2 = rn  1  qn + rn, если ,

rn  1 = rn  qn + 1, если .

То есть .

Согласно теореме 1.2.1 и поскольку , как остаток от деления, имеем

(ab) = (br1) = (r1r2) = … = (rn  1rn) = rn.

Процесс получения (ab) конечен, поскольку мы оперируем только с целыми числами и, начиная с деления r1 на r2, – с целыми положительными числами. Идет постоянное уменьшение остатков ri: 0  ri < ri  1, и за конечное число шагов будет достигнут остаток rn + 1 = 0.

Пример 1.2.1. Найти (72, 26).

Решение. ;

;

;

.

Следовательно, (72, 26) = 2.

Теорема 1.2.2 дает алгоритм Евклида нахождения НОД целых чисел. Он с помощью рекурсии легко преобразуется в алгоритм нахождения НОД не только двух, но и большего количества целых чисел: (a1,…, an  1, an) = ((a1,…, an  1), an), n = 3, 4,… Алгоритм Евклида остается в классе самых быстрых алгоритмов нахождения НОД целых чисел.

Обратное применение цепочки равенств теоремы 1.2.2, равно как и выражение на каждом шаге остатка от деления в виде целочисленной линейной комбинации a и b – так называемый расширенный алгоритм Евклида – доказывает следующий факт.

Теорема 1.2.3. Если d = (ab), то существуют такие целые u и v, что выполняется соотношение:

d = u  a + v  b.

Если a | b, то d = | a |,

Если b | a, то d = | b |,

Если , , то, не ограничивая общности, можем считать | a | > | b | и согласно теореме 1.2.2 получаем:

,

где uv  Z. Используя расширенный алгоритм Евклида, получим те же значения u и v:

r1 = a – q1b,

r2 = b – q2r1 = b – q2(a – q1b) = – q2a + (1 + q2q1)b,



d = rn = rn  2 – qnrn  1 = … = ua + vb.

Следствие. Пусть d = (а1, а2,…, аn). Тогда существуют такие u1, u2,…, un  Z, что

(1.2.1)

Для n = 2 равенство (1.2.1) справедливо согласно теореме 1.2.3. При n  2 сделаем индуктивное предположение о справедливости равенства (1.2.1). Поскольку , то согласно теореме 1.2.3 получаем соотношение: . Тогда . Таким образом, равенство (1.2.1) справедливо для любого натурального n  2.

Определение 1.2.3. Равенство (1.2.1) называют соотношением Безу для наибольшего общего делителя целых чисел.

Пример 1.2.2. Из примера 1.2.1 следует, что

2 = 20 + 6  (–3) = 20 + (26 + 20  (–1))  (–3) = 20  4 + 26  (–3) =

= (72 + 26  (–2))  4 + 26  (–3) = 72  4 + 26  (–11).

2 = 72  u + 26  v, u = 4, v = –11.

Замечание. Числа в (1.2.1) не являются единственными с таким условием. Это следует из теории диофантовых линейных уравнений, которая будет рассмотрена ниже. Так, в примере 1.2.2 числа u = – 9 и v = 25 также удовлетворяют соотношению Безу.

Определение 1.2.4. Если целые, отличные от нуля числа а1, а2,…, аn, n  2, делят целое m, то m называют их общим кратным (ОК).

В дальнейшем речь здесь пойдет только о положительных целых кратных.

Определение 1.2.5. Минимальное из общих кратных целых чисел а1, а2,…, аn называется их наименьшим общим кратным (НОК) и обозначается НОК(а1, а2,…, аn) или (если это не вызывает разночтений) [а1, а2,…, аn].

Свойства НОК

1. m  N.

2. 

3. Для .

Определение 1.2.5 НОК целых чисел а1, а2,…, аn равносильно выполнению свойств 1–3.

4. Если НОК целых чисел существует, то оно единственное.

Пусть m, – два НОК целых чисел а1, а2,…, аn, n  2. По свойству 3 НОК  | m | = || по свойству 4 делимости целых чисел. Поскольку m,  N, то m = .

Очевидно, что если b | a, то [ab] = | a | при a  0.

C помощью рекурсии НОК вычисляется не только для двух, но и большего количества целых чисел: [a1,…, an  1, an] = [[a1,…, an  1], an], n = 3, 4,…

^

§1.3. Простые числа



Определение 1.3.1. Натуральное число p > 1 называется простым, если оно делится только на 1 и на само себя, в противном случае p называется составным. 1 не является ни простым, ни составным числом. Таким образом,

= {1}  {простые числа}  {составные числа}.

Очевидно, справедлива следующая теорема.

Теорема 1.3.1. Наименьший делитель p > 1 натурального числа n > 1 есть число простое, причем если n – составное число, то .

1. n – простое число, .

2. n – составное число, пусть p – составное,   t  N: , что противоречит минимальности делителя p.

Пусть теперь

Свойства простых чисел

1. Для  n  N и любого простого p

2. (p1p2) = 1, если p1  p2 – различные простые числа.

Заметим, что из соотношения натуральных чисел при n > 1, 1 < pq < n следует, что либо , либо принадлежит отрезку [2; ]. Исторически первый метод проверки числа n на простоту заключался в делении его на простые числа, не превосходящие . Это один из вариантов так называемого «решета» Эратосфена, ставшего его наиболее знаменитым достижением. Эратосфен (ок. 276–194 до н.э.) – один из самых разносторонних ученых античности.

23, 4, 5, 6, 7, 8, 9, 10, 11, 12,…, [],

где [] – целая часть .

  1. 2 – простое число, исключаем все числа, кратные 2 (2 | n – да или нет?);

  2. 3 – простое число, исключаем все числа, кратные 3 (3 | n – да или нет?);

и т.д. до ближайшего к простого числа.

В целом «решето» Эратосфена решает более общую задачу нахождения всех простых чисел на отрезке натурального ряда [mn], где m < n.

Добавить документ в свой блог или на сайт

Похожие:

I. Основы теории чисел алгебраические операции на множестве целых чисел iconМножество действительных чисел. Ограниченные числовые множества,...
Ограниченные числовые множества, верхняя и нижняя грани. Метрика множества действительных чисел, открытые и замкнутые множества....

I. Основы теории чисел алгебраические операции на множестве целых чисел iconПрограма за курсом „Обчислювальні методи” Курс 2, Прикладна математика...
Система чисел с плавающей точкой. Представление вещественных чисел числами с плавающей точкой. Погрешности представления вещественных...

I. Основы теории чисел алгебраические операции на множестве целых чисел iconРасчет электрических цепей символическим методом
А’, а проекция на мнимую ось – мнимой части A”, т е. A=A’+jA” – алгебраическая форма комплексных чисел. В зависимости от знаков чисел...

I. Основы теории чисел алгебраические операции на множестве целых чисел iconПростые числа
Определение 5 нок целых чисел а1, а2,…, аn равносильно выполнению свойств 1–3

I. Основы теории чисел алгебраические операции на множестве целых чисел iconПояснительная записка тема: «Выделение максимального и минимального...
Разработать устройство, выделяющее максимальное и минимальное число из потока востмиразрадных чисел

I. Основы теории чисел алгебраические операции на множестве целых чисел iconИз двух дробей с одинаковыми числителями та больше, знаменатель которой...
Арифитические действия с десятичными дробями и их свойства (Пример) Сложение и вычитание десятичных дробей. Эти операции выполняются...

I. Основы теории чисел алгебраические операции на множестве целых чисел iconРешение: N=1607=11001000111
Все числовые данные хранятся в машине в двоичном виде, т е в виде последовательности нулей и единиц, однако формы хранения целых...

I. Основы теории чисел алгебраические операции на множестве целых чисел iconРешить тригонометрическое уравнение и указать корни, принадлежащие отрезку
Среднее арифметическое трёх натуральных чисел в 4 раза больше, чем среднее арифметическое обратных им чисел. Найдите эти натуральные...

I. Основы теории чисел алгебраические операции на множестве целых чисел iconТема : Системы счисления и двоичное представление информации в памяти компьютера
Даны 4 числа, они записаны с использованием различных систем счисления. Укажите среди этих чисел то, в двоичной записи которого содержится...

I. Основы теории чисел алгебраические операции на множестве целых чисел iconВ олков Александр – Математика – как единый источник мировых религий
Ислама, а также мифов древних народов, трудов Посвящённых и стремления автора отыскать в натуральном числовом ряду закон простых...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

Разработка сайта — Веб студия Адаманов