Лекция Основы теории делимости целых чисел



Скачать 184.43 Kb.
Дата07.11.2012
Размер184.43 Kb.
ТипЛекция
Лекция 6. Основы теории делимости целых чисел


6.1. Отношение делимости на множестве целых чисел 2

6.2. Деление с остатком 4

6.3. НОД нескольких целых чисел 5

6.4. Взаимно-простые числа и их свойства 9

6.5. НОК, свойства НОК 9

6.6. Простые числа и их свойства 9

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

6.8. Мультипликативные числовые функции 9

6.9. Функция Е(х) и её применение 9

6.10. Конечные цепные дроби 9

6.11. Подходящие дроби и их свойства 9

6.12. Распределение простых чисел 9

6.13. Асимптотический закон распределения простых чисел 9

6.14. Систематические числа 9




Задания.

1. Сравнить составленный конспект с текстом лекции, внести коррективы.

2. Восстановить доказательства теорем.

2. Изложить содержание одного из разделов 6.4-6.14 структурно по аналогии с содержанием лекции.

6.1. Отношение делимости на множестве целых чисел



Обозначения. N = {1, 2, 3,…} – множество натуральных чисел.

Z  = {…, –3, –2, –1, 0, 1, 2, 3, …} – множество целых чисел.

Определение. О двух целых числах а и b говорят, что а делится на b (обозначают а  b), если  с , такое, что a =  c.

Свойства делимости (теоремы о делимости).

  1. Отношение делимости рефлексивно, то есть ( а  ) (а  а).

Доказательство очевидно, в силу свойства единицы: a = а  1.

  1. Отношение делимости транзитивно, то есть ( а, b, c  ) (а  b, b  c  а  c).

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


Шаг

Утверждение

Аргументация

1

а  b

дано

2

 q , a =  q

из (1) по определению делимости

3

b  c

дано

4

 p , b =  p

из (3) по определению делимости

5

a = (c  p)  q

из (2) и (4) по свойству равенства

6

a = c  (p  q),
p  q,

p  q = r

из (5) согласно ассоциативности умножения целых чисел,

по определению целых чисел,

обозначение

7

a = c  r, r

из (6) с учётом введённого обозначения

8

а  с

из (7) по определению делимости

  1. Отношение делимости сохраняется при изменении знака делимого или/и делителя, то есть (а  b)  [(–а)  b]; [а  (–b)]; [(–a)  (–b)].

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

Шаг

Утверждение

Аргументация

1

а  b

дано

2







  1. Если а  b и с  b, то (а  с)  b.

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

Шаг

Утверждение

Аргументация

1

а  b

дано

2







  1. Если а  b и с , то ас  b.

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

Шаг

Утверждение

Аргументация

1

а  b

дано

2










  1. Если а  b и с не делится на b, то (а  с) не делится на b.

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

Шаг

Утверждение

Аргументация

1

(а  с)  b

допущение

2

 q , a  с =  q

из (1) по определению делимости

3

 q , с = b  q  а

из (2) по определению разности целых чисел

4

b  q  b

свойство 5

5

а  b

дано

6

с  b

из (2)-(4) по свойству 4

7

с не делится на b

дано

8

не верно, что (а  с)  b

(6) и (7) – противоречивые утверждения

9

Если а  b

и с не делится на b, то (а  с) не делится на b

из (7)

  1. Любое целое число делится на 1.

  2. Для любого целого числа а справедливо утверждение: 0  а.

Доказательство (для случая а = 0).

?...

  1. Если а  b и а  0, то  а    b .

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

Шаг

Утверждение

Аргументация

1

а  b

дано

2

а  0

дано

3

 q , a =  q

из (1) по определению делимости

4

 q   1

из (2) и (3) по свойству абсолютной величины целого числа

5

a = (c  p)  q

из (2) и (4) по свойству равенства

6

 а  = b  q 

из (3) по свойству равенства

7

 b  q  =  b    q 

свойство модуля

8

 а  = b    q 

из (6) и (7) – транзитивность равенства

9

 а ,  b ,  q   N

свойство абсолютной величины целого числа отличного от нуля

10

 а    b 

из (8)и (9) по свойству произведения натуральных чисел

(9.1) Если 1  а, то а =  1.

(9.2) Если а  b и b  a, то а =  b.

6.2. Деление с остатком



Определение 1. О двух целых числах а и b (b  0) говорят, что а делится на b с остатком, если  q, r  , такие, что = bq + r, причём <  b .

Свойство делимости с остатком (теорема о делимости с остатком).

( а, b  , b  0) (! q, r  ,) (a = bq + r, 0  r <  b  )

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

1. Докажем факт существования, то есть,

( а, b  , b  0) ( q, r  ,) (a = bq + r, 0  r <  b  )

    1. а, b  , b  0.

Выпишем в виде последовательности множество чисел, кратных b:

, (–2) b, (–1) b, 0b, 1b, 2b,…

и рассмотрим часть последовательности: 0b, 1b, 2b,…

Пусть qbнаибольшее из кратных b, не превосходящих а, тогда

qb  а  (q +1)b.

Выполним ряд преобразований в стремлении получить требуемое равенство: а – qb (+1)b – qb;

0  а – qb  b.

Обозначив разность через r, получим, 0   r b, = а – qb, или

a = bq + r, 0   r  b

    1. а, b  , b  0.

(–b 0, а для всякого положительного числа, согласно 1.1, имеем:  = (–b)+ r, 0   r  (–b), что равносильно

= b(–q) + r, 0   r  (–b)

Из подчеркнутого (1.1 и 1.2) и определения модуля, следует

( q, r  ,) (a = bq + r, 0  r <  b  ).

2. Докажем факт единственности (от противного).

Предположим, что для некоторой пары чисел a и b существует два разложения: q1  q2  и  r1 r2

a = bq1 + r1,  r1   b ,

a = bq2 + r2,  r2   b .

Тогда bq1 + r1 = bq2 + r2,  r1 – r2    b .

Продолжим преобразовывать первое равенство

bq1  bq2 = r r1, 

b(q1  q2) = r r1, 

По определению делимости, (r r1) делится на b.

По свойству 9 делимости целых чисел, если (r r1) делится на b, то модуль (r r1) больше или равен модуля b, то есть  r1 – r2    b .

Получили противоречие: одновременно выполняются два неравенства:

 r1 – r2    b  и  r1 – r2    b . Противоречие возникло из-за неверности допущения о существовании двух различных пар: q1  q2  и  r1 r2. Следовательно, q1 q2 q и  r1= r2 = r, что означает «единственность деления с остатком».

6.3. НОД нескольких целых чисел



Определение 1. Целое число (  0) называется общим делителем целых чисел а1, а2,…, ап, если каждое из этих чисел делится на .

Определение 2. Целое число d (d  0) называют наибольшим общим делителем (НОД) целых чисел а1, а2,…, ап, если

2.1. d – общий делитель этих чисел,

2.2. d  , где любой другой общий делитель этих чисел.

Теорема 1. НОД целых чисел определяется с точностью до знака.

Доказательство (метод …).

Пусть d1 и d2 два различных наибольших общих делителя чисел а1, а2,…, ап,

то есть . Надо доказать, что

По определению 2, признак 2.1, d1 и d2 общие делители чисел а1, а2,…, ап.

По определению 2, признак 2.2,

если d1 наибольший общий делитель чисел а1, а2,…, ап, то d d2,

если d2 наибольший общий делитель чисел а1, а2,…, ап, то d d1.

Согласно свойству делимости (9.2), если d d2 и d d1, то d2 =  d1, то есть НОД определяется с точностью до знака.

Пример. Найдём НОД(135, –180).

135 = {1, 3, 5, 9, 15, 27, 45, 135},

180 = {1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 45, 60, 90, 180},

135  180 = {1, 3, 5, 9, 15, 45},

НОД(135, –180) = 45

Определение 3. Алгоритм Евклида – способ нахождения НОД целых чисел.

Лемма 1. а  b НОД (а, b) = b.

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

Шаг

Утверждение

Аргументация

1

а  b

дано

2

b  b

свойство делимости (1)

3

b – общий делитель а и b

из (1) и (2) по определению общего делителя

4

другой общий делитель а и b

допущение

5

b  с

из (4) по определению общего делителя

6

b – наибольший общий делитель а и b, т.е.

НОД (а, b) = b

из (3) и (5) по определению НОД целых чисел,

обозначение


Лемма 2. Пусть а = bq + r, abr 0, тогда НОД (а, b) = НОД (b, r).

Доказательство (подведение под понятие).

Другими словами, нужно доказать: если
1. Докажем для а = bq r: если – общий делитель а и b, то – общий делитель b и r 

а = bq + r, abr 0. Обозначим – общий делитель а и b. Тогда, по определению общего делителя, а  , b  . Если сумма делится на , и одно из слагаемых делится на , то другое слагаемое тоже делится на (следствие из свойства делимости (4)), то есть r  . Если же b   и r  , то, по определению общего делителя, – общий делитель b и r 

Докажем, по аналогии, для а = bq r: если – общий делитель b и r, то – общий делитель а и b

 

2. Обозначим d = НОД (а, b). Докажем, что d = НОД (br).
Итак, а = bq + r, abr 0 НОД (а, b) = НОД (b, r).

Теорема 2 (алгоритм Евклида). НОД двух целых чисел равен последнему ненулевому остатку в алгоритме Евклида: (ab Z, ab  0) (НОД (а, b) = rп)

а = bq0 + r1, 0  r1   b,

b = r1q1 + r2, 0  r2   r1,

r1 = r2q2 + r3, 0  r3   r2,…

………… rп–2 = rп–1qп–1 + rп, 0  rп   rп–1

rп–1 = rпqп .

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

Пример. Найдём НОД(2585, 7975).

7975 2585

7755 3

2585 220 – первый остаток

220 11

385

220

220 165второй остаток

165 1

165 55 – третий остаток, последний в алгоритме Евклида

165 3

0 – деление без остатка

Итак, НОД(2585, 7975) = 55.

Теорема 3 (алгоритм Евклида). Если НОД п целых чисел – а1, а2,…, ап – равен , и НОД (ап+1) = d, то НОД (а1, а2,…, апап+1) = d.

Доказательство (подведение под понятие).

3.1. Докажем, что d – общий делитель а1, а2,…, апап+1.

Шаг

Утверждение

Аргументация

1

НОД (, ап+1) = d

дано

2

  d, ап+1  d

из (1) по определению НОД (признак 2.1)

3

НОД (а1, а2,…, ап) = 

дано

4

а1  , а2  , … , ап  

из (1) по определению НОД (признак 2.1)

5

а1  d, а2  d, … , ап  d

из (2) и (4) по свойству транзитивности отношения делимости

6

dобщий делитель а1, а2,…, апап+1

из (2) и (5) по определению общего делителя целых чисел

3.2. Докажем, что, если d1 – другой общий делитель а1, а2,…, ап, ап+1, то d  d1.

Если d1 – другой общий делитель а1, а2,…, ап, ап+1, то d1 – общий делитель для а1, а2,…, ап; по условию, НОД (а1, а2,…, ап) = , следовательно (по определению НОД),   d1. Это значит, что d1один из делителей . (*)

По другому условию, НОД (ап+1) = d, то есть   d и d – наибольший делитель . (**)

Из утверждений (*) и (**) следует, что d  d1.

Оформим доказательство 3.2 в таблицу.

Шаг

Утверждение

Аргументация

1

d1 – общий делитель а1, а2,…, ап, ап+1

дано

2







3







4







5







6







По определению НОД целых чисел, из 3.1 и 3.2 следует, что НОД (а1, а2,…, апап+1) = d.

Замечание. Из теоремы 3 вытекает способ последовательного определения НОД нескольких целых чисел а1, а2,…, ап:

  1. НОД (а1, а2) = d1.

  2. НОД (d1, а3) = d2.

  3. НОД (d2, а4) = d3.



  4. НОД (dп–1, ап) = d = НОД (а1, а2,…, ап).

Свойства НОД (теоремы о НОД).

(1) Наибольшим общим делителем целых чисел является наибольший положительный делитель изо всех общих делителей этих чисел.

Доказательство (подведение под понятие).

Обозначим d = НОД (а1, а2,…, ап), наибольший из положительных делителей чисел а1, а2,…, ап, следовательно, а1  , а2  , … , ап  .

(а)  Рассмотрим случай, когда НОД (а1, а2,…, ап) = d, а другой общий делитель. В этом случае или d > , или d = .

(б)  Рассмотрим случай, когда наибольший (по условию) общий делитель, а dдругой общий делитель. В этом случае или  > d , или  = d .

Из (а) и (б) следует, что  = d, то есть  = НОД (а1, а2,…, ап).

(2) НОД (kа, kb) = k НОД (a, b).

Другими словами,
Доказательство.

Рассмотрим и преобразуем правую часть равенства (к виду левой части).

Будем находить НОД (a, b) по алгоритму Евклида: .

Умножим систему на k, получим: .

По теореме 2 (алгоритму Евклида),

для первой системы, НОД (a, b) = rn,

для второй системы, НОД (kа, kb) = krn . Из этого следует, что

НОД (a, b) = k НОД (a, b).

(3) Если d  = НОД (а, b), то существуют такие целые числа х и у, что  aх + bу = d.

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

Рассмотрим алгоритм Евклида: .

Из каждого равенства выразим остатки. Получим

r1 =  1 + b  (– q), где х = 1, у = – q;

r2 = + r1  (– q) = b + ( 1 + b  (– q))  (– q) = a  (– q1) + b  (1 + q1q2),

где х = – q1, у = 1 + q1q2;

и т.д.

rn = a  x* + b y*,

но  rn = НОД (a, b), а НОД (а, b) = d (дано). Значит, d = aх + bу.

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




6.5. НОК, свойства НОК




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




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




6.8. Мультипликативные числовые функции




6.9. Функция Е(х) и её применение




6.10. Конечные цепные дроби




6.11. Подходящие дроби и их свойства




6.12. Распределение простых чисел




6.13. Асимптотический закон распределения простых чисел




6.14. Систематические числа


Похожие:

Лекция Основы теории делимости целых чисел iconОсновы теории чисел
Делимость целых чисел. Деление с остатком. Алгоритм Евклида нахождения наибольшего общего делителя. Решение линейных уравнений в...
Лекция Основы теории делимости целых чисел iconИсследование свойств делимости полиномиальных коэффициентов и степеней методом формальных степенных рядов
В статье методом формальных степенных рядов доказано несколько новых результатов по теории делимости целых чисел и следствий из них,...
Лекция Основы теории делимости целых чисел iconЙона «Баймакский район» Математическая секция Построение признаков делимости чисел Кулешов Богдан
Теория чисел – раздел математики, в котором изучаются свойства чисел. Основной объект теории чисел – натуральные числа. Главное их...
Лекция Основы теории делимости целых чисел iconОбобщение знаний по теме «Делимость чисел»
«Делимости чисел». Кто живет в этой стране? Вы, наверное, догадались: множество натуральных чисел, признаки делимости. А правят этой...
Лекция Основы теории делимости целых чисел iconУрок-путешествие по теме: «нод и нок. Делимость чисел»
Образовательные: отработка умений систематизировать, обобщать знания о делимости чисел, признаков делимости, нахождении нод и нок...
Лекция Основы теории делимости целых чисел iconВопросы к экзамену 6 семестр Система натуральных чисел N. Аксиомы Пеано. Строгий порядок в n и его свойства
Деление с остатком в кольце целых чисел. Основная теорема о делении с остатком в кольце целых чисел Примеры
Лекция Основы теории делимости целых чисел iconАлгоритм Евклида и его сложность
Рассмотрим математические вопросы, связанные с шифрами, использующие операции с целыми числами. Обозначим n – множество натуральных...
Лекция Основы теории делимости целых чисел iconРешение задач на условие делимости чисел При решении таких задач для определения делимости используются операции mod (остаток от деления) или div (целочисленное деление)
Алгоритм решения таких задач заключается в переборе возможных значений с проверкой условия делимости
Лекция Основы теории делимости целых чисел iconСистемы с открытым ключом. Алгоритм Евклида и его сложность
Рассмотрим математические вопросы, связанные с шифрами, использующие операции с целыми числами. Обозначим n – множество натуральных...
Лекция Основы теории делимости целых чисел icon«Признаки делимости в различных системах счисления»
Данная работа посвящена исследованию признаков делимости в различных системах счислениях. Здесь рассматриваются признаки делимости...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org