1.2: Визначення - прості числа

Last updated
Save as PDF

Page ID: 64930

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Можливо, ви помітили, що в розділі 1.1 дуже багато уваги було зроблено на те, чи були у нас хороші, точні визначення речей. Дійсно, не раз вибачалися за те, що дали неточні або інтуїтивно зрозумілі визначення. Це тому, що в математиці визначення - це наша життєва кров. Більше, ніж у будь-яких інших людських починаннях, математики прагнуть до точності. Ця точність пов'язана з вартістю - Математика може мати справу лише з найпростішими явищами ¹. Для мирян, які вважають математику жахливо складною темою, це останнє речення, безумовно, звучить дивним, але більшість професійних математиків киватимуть головами в цей момент. Важкими питаннями правильніше займаються філософи, ніж математики. Чи є у кішки душа? Неможливо сказати, тому що жоден з іменників у цьому питанні не може бути визначено з будь-якою точністю. Чи є квадратний корінь$2$ раціональним числом? Абсолютно ні! Причина впевненості, яку ми відчуваємо, відповідаючи на це друге питання, полягає в тому, що ми точно знаємо, що мається на увазі під фразами «квадратний корінь$2$» та «раціональне число».

Нам часто потрібно спочатку підійти до теми, думаючи візуально або інтуїтивно, але коли справа доходить до доведення наших тверджень, ніщо не зрівняється з силою наявності «правильних» визначень навколо. Можливо, дивно дізнатися, що «правильне» визначення часто розвивається з роками. Це відбувається з тієї простої причини, що деякі визначення легше піддаються доведенню тверджень. Насправді часто буває так, що визначення надихаються спробами довести щось, що не вдається. У розпал такої невдачі, це не рідкість для математика, щоб bemoan «Якби було лише визначення (заповнити порожній).», то зрозуміти, що можна використовувати це визначення або його модифікацію. Але! Коли є кілька визначень для однієї ідеї, вони краще погодитися один з одним!

Розглянемо визначення простого числа.

Визначення: Просте число

Просте число - це натуральне ціле число, більше$1$, чиї єдиними факторами є$1$ і саме.

Ви, напевно, вперше почули це визначення в середній школі, якщо не раніше. Це цілком дійсне визначення того, що це означає для цілого числа, щоб бути простим. У більш просунутій математиці було встановлено, що необхідно визначити поняття первинності для об'єктів, відмінних від цілих чисел. Виявляється, що наступний оператор по суті еквівалентний визначенню «простого», який ми щойно дали (при роботі з цілими числами), але це може бути застосовано в більш загальних налаштуваннях.

Визначення: Прем'єр

Просте - це$p$ така величина, що всякий раз$ab$, коли$p$ є коефіцієнтом деякого$p$ добутку, то$a$ або$p$ є коефіцієнтом або є коефіцієнтом\ (b\ |).

Практика

Число не$1$ вважається простим. Чи$1$ задовольняє вищевказане визначення?

Якщо ви продовжуєте вивчати теорію чисел або абстрактну алгебру, ви побачите, як альтернативне визначення, яке ми дали, потрібно налаштувати, щоб (наприклад)$1$ не зараховуватися як просте. Виправлення не дуже складне (але це трохи складно) і зараз трохи виходить за межі нашої сфери.

Часто це так, що ми можемо сформулювати багато еквівалентних визначень для якогось поняття. Коли це станеться, ви можете зіткнутися з абревіатурою TFAE, яка розшифровується як «Наступні еквівалентні». Доказ TFAE полягає у тому, щоб показати, що безліч різних тверджень насправді визначають одну і ту ж концепцію.

Оскільки ми обговорювали прості числа в цьому розділі (головним чином як приклад концепції з більш ніж одним еквівалентним визначенням), це здається розумним часом, щоб зробити деякі дослідження щодо простих чисел. Ми почнемо в третьому столітті до н.е. Ератосфен Кіренський був грецьким математиком і астрономом, який пам'ятається донині своїми численними досягненнями. Був бібліотекарем у великій Олександрійській бібліотеці. Він робив вимірювання окружності Землі і відстаней Сонця і Місяця, які були надзвичайно точними, але, мабуть, його найбільш запам'ятовується досягненням є «сито» метод пошуку простих чисел. Дійсно, сито Ератосфена все ще має важливе значення в математичних дослідженнях. В основному, метод сита складається з створення дуже довгого списку натуральних чисел, а потім перекреслення всіх чисел, які не є простими числами (додатне число, яке не є$1$, і не є простим називається складовим). Цей процес здійснюється поетапно. Спочатку ми обводимо,$2$ а потім перекреслюємо кожне число, яке має$2$ як фактор - таким чином, ми визначили$2$ як перше просте число і усунули цілу купу чисел, які не є простими. Перше число, яке не було усунуто на цьому етапі$3$, ми обводимо його (вказуючи, що$3$ це друге просте число), а потім перекреслюємо кожне число, яке має$3$ як множник. Зверніть увагу, що деякі цифри (наприклад,$6$ і$12$) будуть перекреслені не один раз! На третьому етапі процесу сита ми обводимо$5$, яке є найменшим числом, яке ще не перекреслено, а потім перекреслюємо всі кратні$5$. Перші три етапи в ситовому способі показані на рис$1.2.1$.

Малюнок$\PageIndex{1}$: Перші три стадії в ситі Ератосфена. Яке найменше складене число, яке не було перекреслено? (Авторське право; автор через джерело)

Цікаво відзначити, що сито дає нам засіб пошуку всіх простих чисел аж до за$p^2$ допомогою простих чисел до (але не включаючи)$p$. Наприклад, щоб знайти всі прості числа менше$13^2 = 169$, нам потрібно тільки використовувати$2$,,$3$$5$,$7$ і$11$ в ситі.

Незважаючи на те, що за допомогою цього простого механічного методу можна знайти прості числа, спосіб розподілу простих чисел між цілими числами дуже непостійний. Майже будь-яке твердження, яке має на меті показати певну закономірність у розподілі простих чисел, виявиться помилковим. Ось два таких помилкових домисли щодо простих чисел.

здогадки$\PageIndex{1}$

$p$Всякий раз, коли$2^p − 1$ є простим числом, також є простим.

здогадки$\PageIndex{2}$

Многочлен$x^2 − 31x + 257$ обчислюється простим числом, коли$x$ є натуральним числом.

У вправах для цього розділу вам буде запропоновано вивчити ці твердження далі.

Прості числа діють як мультиплікативні будівельні блоки для решти цілих чисел. Коли ми розбираємо ціле число на його будівельні блоки, ми знаходимо просту факторизацію цього числа. Основні факторизації унікальні. Тобто число є або простим, або воно має прості множники (можливо, підвищені до різних повноважень), які однозначно визначаються - за винятком того, що вони можуть бути повторно впорядковані.

Нижче наведена таблиця, яка містить всі прості числа, яких менше$5000$. Вивчіть цю таблицю і відкрийте секрет його компактності!

$clipboard_ed6073821076fff9a34a6228574637c9a.png$

Вправи

Вправа$\PageIndex{1}$

Знайдіть прості множники наступних цілих чисел.

105
414
168
1612
9177

Вправа$\PageIndex{2}$

Використовуйте сито Ератосфена, щоб знайти всі прості числа аж до$100$.

\[ \begin{array} a1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20\\ 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30\\ 31 & 32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 & 40 \\ 41 & 42 & 43 & 44 & 45 & 46 & 47 & 48 & 49 & 50 \\ 51 & 52 & 53 & 54 & 55 & 56 & 57 & 58 & 59 & 60 \\ 61 & 62 & 63 & 64 & 65 & 66 & 67 & 68 & 69 & 70 \\ 71 & 72 & 73 & 74 & 75 & 76 & 77 & 78 & 79 & 80 \\ 81 & 82 & 83 & 84 & 85 & 86 & 87 & 88 & 89 & 90 \\ 91 & 92 & 93 & 94 & 95 & 96 & 97 & 98 & 99 & 100 \\ \end{array} \]

Вправа$\PageIndex{3}$

Що було б найбільшим простим, з яким би просіяти, щоб знайти всі прості числа до 400?

Вправа$\PageIndex{4}$

Охарактеризуйте прості множники чисел, які є досконалими квадратами.

Вправа$\PageIndex{5}$

Заповніть наступну таблицю, яка пов'язана з гіпотезою$1.2.1$.

$p$	$2^p - 1$	прем'єр?	чинники
$2$	$3$	так	$1$і$3$
$3$	$7$	так	$1$і$7$
$5$	$31$	так
$7$	$127$
$11$

Вправа$\PageIndex{6}$

Знайдіть контрприклад для «Гіпотеза»$1.2.2$

Вправа$\PageIndex{7}$

Використовуйте друге визначення «простого», щоб побачити, що$6$ це не просте. Іншими словами, знайдіть два числа (a і b, які фігурують у визначенні) такі, що не$6$ є коефіцієнтом того чи іншого, а є фактором їх добутку.

Вправа$\PageIndex{8}$

Використовуйте друге визначення «простого», щоб показати, що$35$ це не просте.

Вправа$\PageIndex{9}$

Відомою здогадкою, яка вважається правдою (але для якої не відомо жодних доказів), є гіпотеза Twin Prime. Пара простих чисел, як кажуть, близнюки, якщо вони відрізняються на$2$. Наприклад,$11$ і$13$ є подвійними простими числами, як$431$ і$433$. Гіпотеза Twin Prime стверджує, що таких близнюків існує нескінченна кількість. Спробуйте придумати аргумент щодо того$3$, чому,$5$ і$7$ є єдиними простими трійками.

Вправа$\PageIndex{10}$

Ще одна відома здогадка, яку також вважали правдою - але поки ще не доведена, є здогадка Гольдбаха. Гіпотеза Гольдбаха стверджує, що кожне парне число більше ніж$4$ є сумою двох непарних простих чисел. Існує функція$g(n)$, відома як функція Гольдбаха, визначена на додатних цілих числах, яка дає кількість різних способів записати задане число як суму двох непарних простих чисел. Наприклад,$g(10) = 2$ так як$10 = 5 + 5 = 7 + 3$. Таким чином, ще одна версія здогадки Гольдбаха полягає в тому, що$g(n)$ є позитивним, коли п парне число більше, ніж$4$.

Графік$g(n)$ для$6 ≤ n ≤ 20$.

Нотатки

1. Для інтригуючого обговорення цього пункту прочитайте книгу Джан Карло Роти Недискретні думки [14]

\(p\)	\(2^p - 1\)	прем'єр?	чинники
\(2\)	\(3\)	так	\(1\)і\(3\)
\(3\)	\(7\)	так	\(1\)і\(7\)
\(5\)	\(31\)	так
\(7\)	\(127\)
\(11\)

Вправа\(\PageIndex{1}\)

Вправа\(\PageIndex{2}\)

Вправа\(\PageIndex{3}\)

Вправа\(\PageIndex{4}\)

Вправа\(\PageIndex{5}\)

Вправа\(\PageIndex{6}\)

Вправа\(\PageIndex{7}\)

Вправа\(\PageIndex{8}\)

Вправа\(\PageIndex{9}\)

Вправа\(\PageIndex{10}\)