20746

Простые числа. Бесконечность множества простых чисел. Каноническое разложение составного числа и его единственность

Доклад

Математика и математический анализ

Определение: Всякое натуральное число p 1 не имеющее других натуральных делителей кроме 1 и p называется простым числом. Наименьшее простое число – 2. 1 Если p 1 является наименьшим делителем целого числа n 1 то оно простое число p. 2 Если произведение где p – простое число то по крайней мере либо либо .

Русский

2013-07-31

44.5 KB

60 чел.

Алгебра.

Вопрос №2.

Простые числа. Бесконечность множества простых чисел. Каноническое разложение составного числа и его единственность.

Определение: Всякое натуральное число p>1, не имеющее других натуральных делителей, кроме 1 и p, называется простым числом.

Наименьшее простое число – 2. 1 – не простое и не составное, так как имеет один делитель 1.

1) Если p>1 является наименьшим делителем целого числа n>1, то оно простое (число p).

2) Если произведение , где p – простое число, то, по крайней мере, либо , либо .

3) Натуральное число a и p – простое число, либо взаимно простые, либо .

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

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

Предположим, что множество простых чисел конечно. Пронумеруем их в порядке возрастания: p1, p2, …, pn.

Рассмотрим . Докажем, что Q – простое. По предположению число Q не может быть простым, так как . Тогда Q – составное число и должно делиться на простое число pm, но тогда , что невозможно. Следовательно, число Q – простое.

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

Что и требовалось доказать.

Существует один простой способ выявления простых чисел на конечном множестве.

Решето Эратосфена: наименьший простой делитель числа a не может быть больше .

p – наименьший простой делитель числа a. .

Метод: (этот факт используется при составлении таблиц простых чисел меньших или равных N, способом, который был указан Эратосфеном и названным решето Эратосфена). Выписывают числа от 2 до N и вычёркивают числа, кратные 2, 3, …. И продолжают до тех пор, как найдено число большее или равное .

По теореме Евклида множество простых чисел бесконечно, тем не менее, можно указать отрезки натуральных чисел сколь угодно большой длины, которые не содержат простые числа. Например: n!+2, n!+3, …, n!+n.

С другой стороны, встречаются такие простые числа, разность между которыми равна 2. Такие числа называются близнецами. Например: 2 и 3, 5 и 7, 11 и 13, 17 и 19, 29 и 31.

Теорема. Всякое натуральное число a (кроме 1), может быть представлено в виде произведения простых множителей и причём единственным образом, если не учитывать порядок следования сомножителей.

.

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

Если число a составное, то наименьший делитель, отличный от 1, число простое. a1 – составное.

Единственность.

Предположим, что существует ещё одно разложение: .

Не нарушая общности рассуждений:

Теорема доказана.

Среди p1, …, pn могут быть одинаковые. Тогда – каноническое разложение на простые множители.


 

А также другие работы, которые могут Вас заинтересовать

38012. ОПРЕДЕЛЕНИЕ ЭФФЕКТИВНОСТИ И СЛОЖНОСТИ ИССЛЕДУЕМЫХ АЛГОРИТМОВ 146.5 KB
  Краткая теория Теория сложности алгоритмов Сложность алгоритма характеристика алгоритма определяющая зависимость времени выполнения программы описывающей этот алгоритм от объёма обрабатываемых данных. Формально определяется как порядок функции выражающей время работы алгоритма. Эффективность алгоритма – временная сложность в самом худшем случае Ofn или просто fn.
38013. ИЗУЧЕНИЕ БЕТА –АКТИВНОСТИ 145.5 KB
  10 ЛАБОРАТОРНАЯ РАБОТА № 95 ИЗУЧЕНИЕ БЕТА –АКТИВНОСТИ Цель работы Изучение явления бета распада определение длины пробега –частиц и максимальной энергии –частиц радиоактивного источника. Например радиоактивный изотоп водорода испускает –частицы с Еmx = 18 кэВ а изотоп азота – с Еmx = 166 МэВ. Типичная кривая распределения –частиц по энергиям изображена на рис.1 где dN dE– число –частиц имеющих полную энергию от Е до Е dЕ Еmx –максимальная энергия –частиц данного радиоактивного вещества.
38014. Изучение нормального закона распределения случайных величин (закон Гаусса) на основе опытных данных 190 KB
  Составить интервальную таблицу частот статистический интервальный ряд распределения: а Разбить весь диапазон случайных величин на k интервалов. Строки 13 Таблицы 3 называют статистическим интервальным рядом распределения. Интервальный ряд распределения изобразить графически в виде гистограммы.
38015. ФОТОМЕТРИЧЕСКОЕ ТИТРОВАНИЕ 115.5 KB
  Если измерение ведется на определенной длине волны а прибор снабжен монохроматором процесс титрования называют спектрофотометрическим титрованием. находят по резкому перегибу полученной в ходе титрования графической зависимости оптической плотности раствора поглощения пропускания от объема добавленного титранта. При СФтитровании достигается особая селективность что связано с возможностью перехода в ходе титрования многокомпонентных систем от одной длины волны к другой.
38016. ДИФФЕРЕНЦИАЛЬНАЯ ФОТОМЕТРИЯ 176.5 KB
  Сущность метода Точность спектрофотометрического анализа можно значительно повысить если измерять не абсолютную величину оптической плотности анализируемого раствора а ее относительную величину ΔD проводя измерения раствора с концентрацией Сx против эталона уже содержащего определяемый компонент в известной концентрации Со. Однако способы настройки существенно отличаются в разных вариантах фотометрического анализа: Способ настройки 1 2 3 4 5 Концентрация раствора в кювете во время настройки на Т = 100 0 С0 С0 или Сх 0 С 0 Концентрация...
38017. Запуск и настройка СУБД VFP 6.0 133 KB
  Вызывается Ctrl F2.0 специальные и функциональные клавиши Сочетание клавиш Пункт меню Комментарий CtrlN File New Создать новый файл CtrlO File Open Открыть существующий файл CtrlS File Sve Сохранить текущий файл CtrlP File Print Печать CtrlZ Edit Undo Отменить действие CtrlR Edit Redo Повторить действие CtrlX Edit Cut Вырезать CtrlC Edit Copy Копировать CtrlV Edit Pste Вставить Ctrl Edit Select ll Выделить все CtrlF Edit Find Найти в текущем файле CtrlG Edit Find gin Найти следующий CtrlL Edit Replce CtrlD Progrm Do CtrlM...
38018. ИЗУЧЕНИЕ И ПРИМЕНЕНИЕ ФИЗИЧЕСКОГО И МАТЕМАТИЧЕСКОГО МАЯТНИКОВ 98.63 KB
  Ознакомление с физическим и математическим маятниками изучение периодического движения маятников как примера колебаний в системах с одной степенью свободы. Измерение ускорения силы тяжести с помощью математического маятника. Измерение периода колебаний физического маятника и сравнение его с расчётным значением. Измерение момента инерции тела сложной формы с помощью физического маятника.
38019. Основы электрохимии 48.5 KB
  В пробирку налить 2 мл раствора йодида калия KJ добавить 2 – 3 капли раствора уксусной кислоты CH3COOH затем прилить 1 мл раствора перекиси водорода H2O2. В пробирку налить 2 мл раствора перманганата калия KMnO4 добавить 2 – 3 капли раствора серной кислоты H2SO4 затем прилить 1 мл раствора перекиси водорода H2O2. Собрать гальванический элемент из двух металлических электродов и растворов электролитов: зачистить наждачной бумагой две металлические пластинки промыть их дистиллированной водой просушить фильтровальной...
38020. ПРЕДСТАВЛЕНИЕ И РЕАЛИЗАЦИЯ АТД «СПИСОК» 355.5 KB
  Краткая теория Реализация списка посредством массивов. При реализации списка посредством массивов используют два способа.n] of record pole1: integer; pole2: Boolen; end; vr :Spisok; Обращение к элементам такого списка будет выглядеть так. Тип для второй реализации списка посредством массивов рис 1.