20746

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

Доклад

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

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

Русский

2013-07-31

44.5 KB

56 чел.

Алгебра.

Вопрос №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 могут быть одинаковые. Тогда – каноническое разложение на простые множители.


 

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

24409. Деловой этикет - это установленный порядок поведения в сфере бизнеса и деловых контактов 34.5 KB
  Деловой этикет это установленный порядок поведения в сфере бизнеса и деловых контактов. Деловой этикет включает в себя следующие разделы: Технологии невербального общения: жесты хорошего тона походка как правильно сидеть вход и выход из автомобиля рукопожатие и пр. Этикет если понимать его как установленный порядок поведения помогает избегать промахов или сгладить их доступными общепринятыми способами. Поэтому основную функцию или смысл этикета делового человека можно определить как формирование таких правил поведения в обществе...
24410. Имидж и его свойства 41 KB
  Имидж складывается в ходе личных контактов человека на основе мнений высказываемых о нем окружающими. Многие индивиды от природы обладают привлекательным имиджем наделены обаянием. Однако отсутствие внешней привлекательности не должно мешать созданию благоприятного имиджа.
24411. Архитектура безопасности. Модели безопасности ее оценки. Общие критерии 44.5 KB
  Данные файла занимают весь первый кластер и только один байт второго остальная же часть второго кластера ничем не заполнена однако недоступна для других файлов эта незанятая область поанглийски называется slack. В следующем доступном кластере могут размещаться данные другого файла. Если под данные этого файла не хватит второго кластера файл будет продолжен в следующем доступном кластере. DOS использует FAT для хранения информации необходимой для доступа к файлам записанным на диске.
24412. Типы процессов, развитие процесса в системе (ОС) 662.5 KB
  Каждый вычислительный процесс характеризуется набором действий набором информационных объектов последовательностью обработки и начальными состояниями говорят о наличии полного процесса в системе. Состояние системы определяется действиями производимыми процессами которые могут затребовать захватить или освободить ресурсы. В этом случае типы отношений предшествования которые возможны между процессами можно представить в следующем виде: Развитие процесса P представляется направленной дугой графа.
24413. Понятие семафора, назначение семафора, операции P(Q) и V(Q) 90 KB
  Ее можно проводить из любой точки Интернета в адрес любого сервера а для отслеживания злоумышленника потребуются совместные действия всех провайдеров составляющих цепочку от злоумышленника до атакуемого сервера VPN Потребительская сущность VPN виртуальный защищенный туннель или путь с помощью которого можно организовать удаленный защищенный доступ через открытые каналы Интернета к серверам баз данных FTP и почтовым серверам. VPN это: защита трафика основанная на криптографии; средство коммуникации с гарантией защиты доступа к...
24414. Понятие тупика, характеристика отношений, возникающих в системе (граф запросов и разделения ресурсов).Способ определения наличия тупиковой ситуации в системе (редукция графа) 112 KB
  К основным законам и подзаконным актам регламентирующим деятельность в области защиты информации относятся: Законы Российской Федерации: О федеральных органах правительственной связи и информации от 19.95 № 15ФЗ; Об информации информатизации и защите информации от 20.95 N 170; О лицензировании деятельности предприятий учреждений и организаций по проведению работ связанных с использованием сведений составляющих государственную тайну созданием средств защиты информации а также с осуществлением мероприятий и или оказанием услуг по...
24415. Четыре условия возможности возникновения тупика 77 KB
  Политика безопасности. Процедуры управления безопасностью также важны как и политики безопасности. Если политики безопасности определяют что должно быть защищено то процедуры безопасности определяют как защитить информационные ресурсы компании. Нескольких важных процедур безопасности: 1.
24416. Факторы сложности восстановления систем после тупика 69 KB
  Эксплуатация инфраструктуры безопасности. Эксплуатация инфраструктуры безопасности. Если такое превышение имеет место значит данная строка – это одна из первоочередных целей разработки политики безопасности. Если интегральный риск превышает допустимое значение значит в системе набирается множество мелких огрешностей в системе безопасности которые в сумме не дадут предприятию эффективно работать.
24417. Описание формальной модели ОС для абстрактной микропроцессорной ЭВМ 155 KB
  Структуру ОС в t T можно представить с помощью графа Гt вершинами которого являются элементы Р={P0 Pn} множество процессов и множество ресурсов R={r0 rq} а ребра устанавливают связь между вершинами. ОС является динамически изменяемая система то некоторые элементы в моменты времени t1 t2 принадлежащие Т если t1≠t2 представляют структуру ОС в виде графа Гt1 и графа Гt2. Проследим изменения графа Гt отображая структуру ОС в любой момент времени t T. Определим множество Е как совокупность правил фиксирующих изменение структуры...