ПРОСТІ ЧИСЛА: ХАРАКТЕРИСТИКИ, ПРИКЛАДИ, ВПРАВИ - МАТЕМАТИКА - 2024

У простих числах , звані також простих абсолютні, є тими натуральними числами , які тільки діляться сам по собі і 1. Цією категорія номер , як 2, 3, 5, 7, 11, 13, 17, 19, 23 і безліч плюс.

Натомість складене число ділиться самим собою на 1, і принаймні одне інше число. У нас є, наприклад, 12, яка ділиться на 1, 2, 4, 6 і 12. За умовою, 1 не входить до списку простих чисел або до списку сполук.

Малюнок 1. Деякі прості числа. Джерело: Wikimedia Commons.

Знання простих чисел відноситься до найдавніших часів; стародавні єгиптяни їх уже використовували, і вони, напевно, були відомі задовго до цього.

Ці числа дуже важливі, оскільки будь-яке натуральне число може бути представлене добутком простих чисел, при цьому подання є унікальним, за винятком порядку множників.

Цей факт повністю встановлений в теоремі під назвою Фундаментальна теорія арифметики, де зазначено, що числа, які не є простими, обов'язково складаються з добутків чисел, які є.

Характеристика простих чисел

Ось основні характеристики простих чисел:

-Вони нескінченні, оскільки незалежно від того, наскільки велике просте число, завжди можна знайти більшу.

-Якщо просте число p точно не розділяє інше число a, тоді кажуть, що p і a є простими один для одного. Коли це відбувається, єдиний спільний дільник, який є у обох, є 1.

Це не обов'язково, щоб бути абсолютним простим. Наприклад, 5 є простим, і хоча 12 - ні, обидва числа є простими один для одного, оскільки обидва мають 1 як спільний дільник.

-Коли просте число p ділить потужність числа n, воно також ділить n. Розглянемо 100, що є потужністю 10, конкретно 10 ² . Буває, що 2 ділить і 100, і 10.

-Все прості числа непарні, за винятком 2, тому його остання цифра становить 1, 3, 7 або 9. 5 не включається, тому що, хоча вона непарна і проста, вона ніколи не є кінцевою цифрою іншого простого числа. Насправді всі числа, які закінчуються на 5, кратні цьому, і тому вони не є простими.

-Якщо p - просте і дільник добутку двох чисел ab, то p ділить одне з них. Наприклад, просте число 3 ділить добуток 9 х 11 = 99, оскільки 3 - дільник на 9.

Як дізнатися, чи є простим число

Первинність - це ім'я, яке надається якості першості. Ну, французький математик П'єр де Ферма (1601-1665) знайшов спосіб перевірити первинність числа у так званій невеликій теоремі Ферма, де сказано:

"Враховуючи просте натуральне число p та будь-яке натуральне число, що перевищує 0, це правда, що ^p - a - кратне p, доки p є простим".

Ми можемо це підтвердити, використовуючи невеликі числа, наприклад, припустимо, що p = 4, який ми вже знаємо, не є простим і вже = 6:

6 ⁴ - 6 = 1296 - 6 = 1290

Число 1290 точно не ділиться на 4, тому 4 не є простим числом.

Зробимо тест зараз з р = 5, який є простим і ya = 6:

6 ⁵ - 6 = 7766 - 6 = 7760

7760 ділиться на 5, оскільки будь-яке число, яке закінчується на 0 або 5, є. Насправді 7760/5 = 1554. Оскільки справедлива теорема Ферма, ми можемо гарантувати, що 5 є простим числом.

Доведення через теорему є ефективним і прямим з малими числами, в яких операцію легко виконати, але що робити, якщо нас попросять дізнатись первинність великої кількості?

У такому випадку число послідовно ділиться між усіма меншими простими числами, поки не буде знайдено точний поділ або коефіцієнт менший від дільника.

Якщо будь-який поділ точний, це означає, що число складене, а коли коефіцієнт менший від дільника, це означає, що число є простим. Ми втілимо це на практиці у розв'язаній вправі 2.

Способи знайти просте число

Існує нескінченно багато простих чисел, і немає єдиної формули для їх визначення. Однак, дивлячись на кілька простих чисел, таких як:

3, 7, 31, 127 …

Спостерігається, що вони мають форму 2 ⁿ - 1, з n = 2, 3, 5, 7, 9 … Ми переконуємось у цьому:

2 ² - 1 = 4 - 1 = 3 ; 2 ³ - 1 = 8 - 1 = 7 ; 2 ⁵ - 1 = 32 - 1 = 31 ; 2 ⁷ - 1 = 128 - 1 = 127

Але ми не можемо гарантувати, що 2 ⁿ - 1 є простим, оскільки є деякі значення n, для яких воно не працює, наприклад 4:

2 ⁴ - 1 = 16 - 1 = 15

І число 15 не є простим, оскільки закінчується в 5. Однак один з найбільших відомих прайменів, знайдений за допомогою комп'ютерних обчислень, має форму 2 ⁿ - 1 із:

n = 57,885,161

Формула Мерсена запевняє, що 2 ^p - 1 завжди є простим, доки p також є простим. Наприклад, 31 є простим, тому певно, що 2 ³¹ - 1 також є простим :

2 ³¹ - 1 = 2,147,483,647

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

Формула Ейлера

Наступний многочлен дозволяє знаходити прості числа за умови, що n становить від 0 до 39:

P (n) = n ² + n + 41

Пізніше у розділі розв’язаних вправ є приклад його використання.

Сито Ератосфена

Ератостен був фізиком і математиком з Стародавньої Греції, який жив у 3 столітті до н.е.

-Числа розміщуються в таблиці, як та, яка показана в анімації.

-Після цього перекреслюються парні числа, за винятком 2, про які ми знаємо, що є простими. Усі інші є кратними цим і тому не є простими.

-Кліпси 3, 5, 7 і 11 також позначені, виключаючи всі вони, тому що ми знаємо, що вони є простими.

-Кратки 4, 6, 8, 9 і 10 вже позначені, тому що вони є складовими і, отже, кратніми деяких із зазначених прайменів.

-Зрештою, числа, які залишаються без позначення, є простими.

Малюнок 2. Анімація сита Ератостена. Джерело: Wikimedia Commons.

Вправи

- Вправа 1

Використовуючи поліном Ейлера для простих чисел, знайдіть 3 числа, що перевищують 100.

Рішення

Це поліном, який Ейлер запропонував знайти прості числа, які працюють для значень n від 0 до 39.

P (n) = n ² + n + 41

За допомогою проб і помилок вибираємо значення n, наприклад n = 8:

Р (8) = 8 ² + 8 + 41 = 113

Оскільки n = 8 створює просте число, що перевищує 100, то ми оцінюємо поліном для n = 9 і n = 10:

Р (9) = 9 ² + 9 + 41 = 131

Р (10) = 10 ² + 10 + 41 = 151

- Вправа 2

Дізнайтеся, чи є простими такі числа:

а) 13

б) 191

Рішення для

13 досить малі, щоб використовувати маленьку теорему Ферма та допомогу калькулятора.

Ми використовуємо a = 2, щоб числа були не надто великими, хоча a = 3, 4 або 5 також можна використовувати:

2 ¹³ - 2 = 8190

8190 ділиться на 2, оскільки це парне, тому 13 є простим. Читач може підтвердити це, зробивши той же тест з a = 3.

Рішення b

191 занадто великий, щоб довести його теоремою та загальним калькулятором, але ми можемо знайти поділ між кожним простим числом. Ми пропускаємо ділення на 2, тому що 191 не є рівним і ділення не буде точним або коефіцієнтом менше 2.

Спробуємо розділити на 3:

191/3 = 63 666 …

І це не дає точного, а також коефіцієнта менше дільника (63 666 … більше 3)

Ми продовжуємо, таким чином, намагаючись розділити 191 між простими числами 5, 7, 11, 13, і точного поділу не досягнуто, ані коефіцієнта менше, ніж дільник. Поки він не розділиться на 17:

191/17 = 11, 2352 …

Оскільки це не точно, а 11.2352… менше 17, число 191 є простим.

Список літератури

1. Бальдор, А. 1986. Арифметика. Видання та дистрибутивні кодекси.
2. Пріето, С. Прості числа. Відновлено з: paginas.matem.unam.mx.
3. Властивості простих чисел. Відновлено з: mae.ufl.edu.
4. Smartick. Прості номери: як їх знайти за допомогою сита Ератостена. Відновлено з: smartick.es.
5. Вікіпедія. Основний номер. Відновлено з: es.wikipedia.org.