20746

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

Доклад

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

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

Русский

2013-07-31

44.5 KB

58 чел.

Алгебра.

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


 

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

22032. Дельта - модуляция (кодирование с предсказанием) (ДИКМ) 158.5 KB
  Основные параметры характеристики компрессии по А – закону приведены в таблице: № сегмента Вид кодовой комбинации P XYZ ABCD Относительный интервал изменения входного сигнала Значение шага квантования относительно Uогр 0 P 000 ABCD 0  1 128 1 2048 1 P 001 ABCD 1 128  1 64 1 2048 2 P 010 ABCD 1 64  1 32 1 1024 3 P 011 ABCD 1 32  1 16 1 512 4 P 100 ABCD 1 16  1 8 1 256 5 P 101 ABCD 1 8  1 4 1 128 6 P 110 ABCD 1 4  1 2 1 64 7 P 111 ABCD 1 2  1 1 32 Кодовая комбинация и есть код квантованного сигнала P  ABCD ...
22033. Особенности передачи сигналов данных 67 KB
  Качество передачи при этом оценивается не искажениями формы сигналов как в аналоговых системах а числом ошибок в принятой информации т. верностью передачи. В хороших модемах перед началом передачи информации вначале устанавливается связь между модемами которые автоматически обмениваясь сигналами подстраиваются под конкретную линию связи и автоматически выбирают необходимую скорость передачи а затем передают саму информацию.
22034. Графическая визуализация вычислений 83.54 KB
  В ходе выполнения данной лабораторной работы я освоил визуализацию вычислений средствами указанных функций
22035. Казкотерапія як напрям психолого-педагогічної терапії 132.5 KB
  Озброїти студентів знаннями про сутність казкотерапії та особливості психолого-педагогічої терапії за допомогою казки. Ознайомити з видами казок у казко терапії. Пояснити особливості використання різних форм роботи з казкою у процесі казко терапії. Сформувати поняття про використання різних арттерапевтичних технік та їх поєднання в казкотерапевтичній роботі.
22036. Музикотерапія та особливості її використання 57.5 KB
  Музикотерапія – це контрольоване використання звуків і музикп в лікуванні і реабілітації клієнтів, що являє собою діяльність, яка включає: відтворення, фантазування, імпровізацію за допомогою людського голосу і вибраних музичних інструментів чи прослуховування спеціально підібраних музичних творів.
22037. Математическая обработка данных 21.98 KB
  В ходе выполнения лабораторной работы мною были освоены функции, позволяющие решать нетривиальные математические задачи.
22038. Основные графические возможности 131.8 KB
  Построить график дискретных отсчетов функции. Отразить координатную сетку. Закрасить маркеры. Построить графики в логарифмическом и полулогарифмическом масштабе, используя разбиение графического окна. Построить лестничный график. В этом же графике графическом окне построить плоской график заданной функции.
22039. Общая схема мультиплесирования PDH трибов 180.5 KB
  POH – поле размером не более 9 байт двумерного формата 1×n. Пример: 1×9 байт для VC4 или VC32 формат 1×6 байт для VC31. Каждый элемент рамки содержит 1 байт. Порядок передачи байтов во всех структурах одинаков: слева направо и сверху вниз.
22040. Функциональные модули сетей SDH 72.5 KB
  СОПРЯЖЕНИЕ сети SDH с каналами пользователя производится терминальным оборудованием включающим в себя конверторы интерфейсов конверторы скоростей конверторы импедансов и т. Мультиплексоры SDH Поскольку в каждом комплекте оборудования узла связи одновременно производится в одном направлении передача а другом приём то в одном блоке монтируется и мультиплексор и демультиплексор выполняющие взаимообратные функции объединения разъединения расшивки потоков. Мультиплексоры SDH в отличае от мультиплексоров PDH выполняют как функции...