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

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

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

По-друге, єдиним парним числом, яке затесалося до групи «прості числа» є, природно, двійка. Будь-яке інше парне число сюди потрапити просто не може, тому що вже за визначенням, окрім себе та одиниці, ділиться ще й на два.

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

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

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

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

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

Які числа називають англійським словом "Симпл"?

Дуже часто школярі на одне з найпростіших на перший погляд питань математики, про те, що таке просте число, не знають, як відповісти. Вони часто плутають прості числа з натуральними (тобто числа, які використовуються людьми за рахунку предметів, причому в деяких джерелах вони починаються з нуля, а в інших – з одиниці). Але це зовсім два різних поняття. Прості числа - це, натуральні, тобто цілі та позитивні числа, які більше одиниці і які мають лише 2 натуральні дільники. При цьому один із цих дільників - це це число, а другий – одиниця. Наприклад, три - це просте число, оскільки він не ділиться без залишку ні на яке інше число, окрім себе самого та одиниці.

Складові числа

Протилежністю простих чисел є складові. Вони також є натуральним, також більше одиниціале мають не два, а Велика кількістьдільників. Приміром, числа 4, 6, 8, 9 тощо. буд. є натуральними, складовими, але з простими числами. Як бачите - це переважно парні числа, але не всі. А ось "двійка" - парне число та "перший номер" у ряді простих чисел.

Послідовність

Щоб побудувати ряд простих чисел, необхідно здійснити відбір із усіх натуральних чисел з урахуванням їх визначення, тобто потрібно діяти методом протилежного. Необхідно розглянути кожне з натуральних позитивних чисел щодо того, чи має воно більше двох дільників. Давайте намагатимемося побудувати ряд (послідовність), який складають прості числа. Список починається з двох, наступним три три, оскільки воно ділиться тільки на себе і на одиницю. Розглянемо число чотири. Чи має воно дільники, крім чотирьох та одиниці? Так, це число 2. Отже, чотири не є простим числом. П'ять також є простим (воно, крім 1 і 5, на жодне інше число не ділиться), а ось шість - ділиться. І взагалі, якщо простежити за всіма парними числами, можна помітити, що крім “двох”, жодна з них не є простим. Звідси зробимо висновок, що парні числа, крім двох, є простими. Ще одне відкриття: усі числа, що діляться на три, крім самої трійки, чи то парні, чи непарні, також не є простими (6, 9, 12, 15, 18, 21, 24, 27 тощо). Те саме стосується і чисел, які діляться на п'ять і сім. Усі їх безліч також не є простим. Давайте підіб'ємо підсумки. Отже, до простих однозначним числамставляться все непарні числа, крім одиниці і дев'ятки, та якщо з парних - лише “два”. Самі десятки (10, 20, ... 40 та ін.) не є простими. Двозначні, тризначні і т. д. прості числа можна визначити, виходячи з вищевикладених принципів: якщо вони не мають інших дільників, крім самих себе і одиниці.

Теорії про властивості простих чисел

Існує наука, яка вивчає властивості цілих чисел, у тому числі і найпростіших. Це розділ математики, що називається вищою. Крім властивостей цілих чисел, вона також займається алгебраїчними, трансцендентними числами, а також функціями різного походження, пов'язаними з арифметикою цих чисел У цих дослідженнях, крім елементарних та алгебраїчних методів, також використовуються аналітичні та геометричні. Саме вивченням найпростіших чисел займається “Теорія чисел”.

Прості числа - "будівельні блоки" натуральних чисел

В арифметиці є теорема, яка називається основною. Згідно з нею, будь-яке натуральне число, крім одиниці, можна представити у вигляді твору, множниками якого є прості числа, причому порядок проходження множників є єдиним, це означає, що і спосіб подання є єдиним. Він називається розкладанням натурального числа на прості множники. Є й інша назва цього процесу – факторизація чисел. Виходячи з цього, прості числа можна назвати “ будівельним матеріалом”, „блоками” для побудови натуральних чисел.

Пошук простих чисел. Тести простоти

Багато вчених різних часів намагалися знайти якісь принципи (системи) для знаходження списку простих чисел. Науці відомі системи, які називаються Решето Аткіна, Решето Сундартама, Решето Ератосфена. Однак вони не дають якихось суттєвих результатів, і знаходження простих чисел використовується проста перевірка. Також математиками було створено алгоритми. Їх прийнято називати тестами простоти. Наприклад, існує тест, розроблений Рабіном та Міллером. Його використовують криптографи. Також існує тест Каяла-Агравала-Саскени. Однак він, незважаючи на достатню точність, дуже складний у обчисленні, що принижує його прикладне значення.

Чи має безліч простих чисел межа?

Про те, що безліч простих є нескінченністю, писав у книзі "Початки" давньогрецький вчений Евклід. Він говорив так: “Давайте на хвилину уявімо, що прості числа мають межу. Тоді давайте перемножимо їх один з одним, а до твору додамо одиницю. Число, отримане в результаті цих простих дій, не може ділитися на одне з ряду простих чисел, тому що в залишку завжди буде одиниця. А це означає, що є якесь інше число, яке ще не включено до списку простих чисел. Отже, наше припущення не вірне, і це безліч не може мати межі. Крім доказу Евкліда, існує більше сучасна формула, дана швейцарським математиком вісімнадцятого століття Леонардом Ейлером Згідно з ним, сума, оборотна суміперших n чисел зростає необмежено зі зростанням числа n. І це формула теореми щодо розподілу простих чисел: (n) зростає, як n/ln (n).

Яке найбільше просте число?

Той самий Леонард Ейлер зміг знайти найбільше для свого часу просте число. Це 2 31 - 1 = 2147483647. Однак до 2013 року було обчислено інше найбільш точне найбільше у списку простих чисел - 257885161 - 1. Його називають числом Мерсенна. Воно містить близько 17 мільйонів десяткових цифр. Як бачите, число, знайдене вченим із вісімнадцятого століття, у кілька разів менше від цього. Так і мало бути, адже Ейлер вів цей підрахунок вручну, нашому ж сучасникові напевно допомагала обчислювальна машина. Більше того, це число було отримано на математичному факультеті в одному з американських факультетів. Числа, названі на вшанування цього вченого, проходять через тест простоти Люка-Лемера. Однак наука не бажає зупинятися на досягнутому. Фонд Електронних рубежів, заснований 1990 року у Сполучених Штатах Америки (EFF), призначив за перебування великих простих чисел грошову нагороду. І якщо до 2013 року приз покладався тим ученим, які знайдуть їх із числа 1 та 10 мільйонів десяткових чисел, то сьогодні ця цифра досягла від 100 мільйонів до 1 мільярда. Розмір призів становить від 150 до 250 тисяч доларів.

Назви спеціальних простих чисел

Ті числа, які знайшли завдяки алгоритмам, створеним тими чи іншими вченими, і пройшли тест простоти, називаються спеціальними. Ось деякі з них:

1. Мерссен.

4. Каллена.

6. Міллса та ін.

Простота цих чисел, названих на честь перелічених вище вчених, встановлюється з використанням наступних тестів:

1. Люка-Лемера.

2. Пепіна.

3. Різель.

4. Біллхарта - Лемера - Селфріджа та ін.

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

Ще з часів стародавніх греків найпростіші числа були дуже привабливі для математиків. Вони постійно шукають різні способиїх знаходження, але найбільш ефективним способом«упіймання» простих чисел, вважається спосіб, знайдений олександрійським астрономом і математиком Ератосфеном. Цьому способу вже близько 2000 років.

Які числа є простими

Як визначити просте число? Багато чисел діляться без залишку на інші числа. Число, на яке ділиться ціле число, ми називаємо дільником.

У даному випадкуми говоримо про поділ без залишку. Наприклад, число 36 можна розділити на 1, 2, 3, 4, 6, 9, 12, 18 і на себе, тобто на 36. Значить, 36 має 9 дільників. Число 23 ділиться тільки на себе і на 1, тобто це число має 2 дільники - це число є простим.

Числа, які мають лише два дільники, називаються простими числами. Тобто число, яке ділиться без залишку тільки на себе та на одиницю, називається простим.

Для математиків відкриття закономірностей у ряді чисел, які потім можна використовувати для побудови гіпотез, є дуже приємною подією. Але прості числа відмовляються підкорятися будь-якій закономірності. Але є спосіб визначення простих чисел. Цей спосіб знайдено Ератосфеном, він називається «решіткою Ератосфена». Давайте розглянемо варіант такого «решета», поданий як таблиці чисел до 48 і зрозуміємо, як її складено.

У цій таблиці всі прості числа менше 48 відзначені помаранчевим кольором . Знайдені вони так:

• 1 - має єдиний дільник і тому не є простим числом;
• 2 – найменше просте число і єдине парне, тому що всі інші парні числа діляться на 2, тобто мають не менше 3 дільників, ці числа зведені фіолетову колонку;
• 3 - просте число, має два дільники, всі інші числа, які діляться на 3, виключаються - ці числа зведені в жовту колонку. Колонка, відзначена і фіолетовим, і жовтим, містить числа, що діляться і на 2 і на 3;
• 5 - просте число, всі числа, які діляться на 5, виключаються - ці числа обведені зеленим овалом;
• 7 – просте число, всі числа, які діляться на 7, обведені червоним овалом – вони є простими;

Всі числа, що не є простими, відмічені синім кольором. Далі цю таблицю можна скласти самому за образом і подобою.

• Переклад

Властивості простих чисел вперше почали вивчати математику Стародавню Грецію. Математики піфагорійської школи (500 – 300 до н.е.) насамперед цікавилися містичними та нумерологічними властивостями простих чисел. Вони першими прийшли до ідей про досконалі та дружні числа.

У досконалого числа сума його дільників дорівнює йому самому. Наприклад, власні дільники числа 6: 1, 2 та 3. 1 + 2 + 3 = 6. У числа 28 дільники – це 1, 2, 4, 7 та 14. При цьому, 1 + 2 + 4 + 7 + 14 = 28.

Числа називаються дружніми, якщо сума власних дільників одного числа дорівнює іншому, і навпаки – наприклад, 220 та 284. Можна сказати, що досконале число є дружнім для самого себе.

На час появи роботи Евкліда «Початку» 300 року до н.е. вже було доведено декілька важливих фактівщодо простих чисел. У книзі IX "Початок" Евклід довів, що простих чисел нескінченна кількість. Це, до речі, один із перших прикладів використання доказу від протилежного. Також він доводить Основну теорему арифметики – кожне ціле число можна уявити єдиним чином у вигляді добутку простих чисел.

Також він показав, якщо число 2 n -1 є простим, то число 2 n-1 * (2 n -1) буде досконалим. Інший математик, Ейлер, в 1747 зумів показати, що всі парні досконалі числаможна записати у такому вигляді. Досі невідомо, чи є непарні досконалі числа.

У 200 році до н.е. Грек Ератосфен вигадав алгоритм для пошуку простих чисел під назвою «Решето Ератосфена».

А потім трапилася велика перерва в історії дослідження простих чисел, пов'язана із Середні віки.

Наступні відкриття були зроблені вже на початку 17 століття математиком Ферма. Він довів гіпотезу Альбера Жірара, що будь-яке просте число виду 4n+1 можна записати унікальним чином у вигляді суми двох квадратів, і також сформулював теорему про те, що будь-яке число можна подати у вигляді чотирьох квадратів.

Він розробив новий методфакторизації великих чиселі продемонстрував його на числі 2027651281 = 44021 × 46061. Також він довів Малу теорему Ферма: якщо p – просте число, то для будь-якого цілого a буде вірно a p = a modulo p.

Це твердження доводить половину того, що було відомо як китайська гіпотеза», і датується 2000 роками раніше: ціле n є простим тоді і лише тоді, коли 2 n -2 ділиться на n. Друга частина гіпотези виявилася хибною - наприклад, 2341 - 2 ділиться на 341, хоча число 341 складове: 341 = 31 × 11.

Мала теорема Ферма послужила основою багатьох інших результатів теорії чисел і методів перевірки чисел на приналежність до простих – багато з яких використовуються і донині.

Ферма багато листувався зі своїми сучасниками, особливо з ченцем на ім'я Марен Мерсенн. В одному з листів він висловив гіпотезу про те, що числа виду 2n+1 завжди будуть простими, якщо n є ступенем двійки. Він перевірив це для n = 1, 2, 4, 8 і 16, і був упевнений, що у випадку, коли n не є ступенем двійки, число не обов'язково виходило простим. Ці числа називаються числами Ферма, і лише через 100 років Ейлер показав, що наступне число, 2 32 + 1 = 4294967297 ділиться на 641, а отже, не є простим.

Числа виду 2 n - 1 також служили предметом досліджень, оскільки легко показати, що й n – складове, те й саме число теж складове. Ці числа називають числами Мерсенна, оскільки він їх активно вивчав.

Не всі числа виду 2 n - 1, де n – просте, є простими. Наприклад, 2 11 - 1 = 2047 = 23 * 89. Вперше це виявили 1536 року.

Багато років такого виду давали математикам найбільші відомі прості числа. Що число M 19 було доведено Катальді в 1588 році, і протягом 200 років було найбільшим відомим простим числом, поки Ейлер не довів, що M 31 також просте. Цей рекорд протримався ще сто років, а потім Люкас показав, що M 127 - просте (а це вже число з 39 цифр) і після нього дослідження продовжилися вже з появою комп'ютерів.

У 1952 було доведено простота чисел M 521 , M 607 , M 1279 , M 2203 і M 2281 .

До 2005 року знайдено 42 простих чисел Мерсенна. Найбільше їх, M 25964951 , складається з 7816230 цифр.

Робота Ейлера справила величезний вплив на теорію чисел, у тому числі і найпростіших. Він розширив Малу теорему Ферма та запровадив φ-функцію. Факторизував 5-е число Ферма 2 32 +1, знайшов 60 пар дружніх чисел і сформулював (але не зміг довести) квадратичний закон взаємності.

Він першим увів методи математичного аналізута розробив аналітичну теоріючисел. Він довів, що гармонійний ряд ∑ (1/n), а й ряд виду

1/2 + 1/3 + 1/5 + 1/7 + 1/11 +…

Одержуваний сумою величин, обернених до простих чисел, також розходиться. Сума n членів гармонійного рядуросте приблизно як log(n), а другий ряд розходиться повільніше, як log[log(n)]. Це означає, що, наприклад, сума обернених величин до всіх знайдених на сьогодні простих чисел дасть всього 4, хоча ряд все одно розходиться.

На погляд здається, що прості числа розподілені серед цілих досить випадково. Наприклад, серед 100 чисел, що йдуть прямо перед 10000000, зустрічається 9 простих, а серед 100 чисел, що йдуть відразу після цього значення - всього 2. Але на великих відрізках прості числа розподілені досить рівномірно. Лежандр і Гаус займалися питаннями їх розподілу. Гаус якось розповідав другу, що у будь-які вільні 15 хвилин він завжди підраховує кількість простих у черговий 1000 чисел. До кінця життя він порахував усі прості числа у проміжку до 3 мільйонів. Лежандр і Гаусс однаково обчислили, що з великих n щільність простих чисел становить 1/log(n). Лежандр оцінив кількість простих чисел у проміжку від 1 до n, як

π(n) = n/(log(n) - 1.08366)

А Гаус - як логарифмічний інтеграл

π(n) = ∫ 1/log(t) dt

Із проміжком інтегрування від 2 до n.

Твердження про щільність простих чисел 1/log(n) відоме як Теорема про розподіл простих чисел. Її намагалися довести протягом усього 19 століття, а прогресу досягли Чебишев та Ріман. Вони пов'язали її з гіпотезою Рімана - досі не доведеною гіпотезою про розподіл нулів дзета-функції Рімана. Щільність простих чисел була одночасно доведена Адамаром та Валле-Пуссеном у 1896 році.

Теоретично простих чисел є ще безліч невирішених питань, деяким із яких вже багато сотень років:

• гіпотеза про прості числа-близнюки – про нескінченну кількість пар простих чисел, що відрізняються один від одного на 2
• гіпотеза Гольдбаха: будь-яке парне число, починаючи з 4, можна подати у вигляді суми двох простих чисел
• Чи нескінченно кількість простих чисел виду n 2 + 1?
• чи завжди можна знайти просте число між n 2 and (n + 1) 2? (факт, що між n та 2n завжди є просте число, було доведено Чебишевим)
• Чи нескінченна кількість простих чисел Ферма? чи є взагалі прості числа Ферма після 4-го?
• чи існує арифметична прогресіяз послідовних простих чисел для будь-якої заданої довжини? наприклад, для довжини 4: 251, 257, 263, 269. Максимальна зі знайдених довжина дорівнює 26 .
• Чи нескінченно число наборів із трьох послідовних простих чисел в арифметичній прогресії?
• n 2 - n + 41 – просте число для 0 ≤ n ≤ 40. Чи нескінченна кількість таких простих чисел? Те саме питання для формули n 2 - 79 n + 1601. Ці числа прості для 0 ≤ n ≤ 79.
• чи нескінченно кількість простих чисел виду n# + 1? (n# - результат перемноження всіх простих чисел, менших за n)
• Чи нескінченно кількість простих чисел виду n # -1?
• чи нескінченно кількість простих чисел виду n! + 1?
• чи нескінченно кількість простих чисел виду n! - 1?
• якщо p – просте, чи завжди 2 p -1 не містить серед множників квадратів простих чисел
• чи містить послідовність Фібоначчі нескінченну кількість простих чисел?

Найбільші близнюки серед простих чисел – це 200 366 36 13 × 2 195 000 ± 1. Вони складаються з 58 711 цифр, і були знайдені в 2007 році.

Найбільше факторіальне просте число (виду n! ± 1) - це 147 855! - 1. Воно складається з 142891 цифр і було знайдено у 2002 році.

Найбільше прайморіальне просте число (число виду n ± 1) - це 1098133 # + 1.

Визначення 1. Просте число− це натуральне число більше одиниці, яке ділиться тільки на себе та на 1.

Тобто число є простим, якщо має тільки два різних натуральних дільника.

Визначення 2. Будь-яке натуральне число, яке, крім самого себе та одиниці, має й інших дільників, називається складовим числом.

Тобто натуральні числа, які не є простими числами, називаються складовими. З визначення 1 випливає, що складова кількість має більше двох натуральних дільників. Число 1 перестав бути ні простим, ні складовим т.к. має тільки один дільник 1 і, крім цього, багато теорем щодо простих чисел не мають місця для одиниці.

З визначень 1 та 2 випливає, що кожне ціле додатне числобільше 1 є чи простим, чи складовим числом.

Нижче представлена ​​програма для відображення простих чисел до 5000. Заповніть комірки, натисніть кнопку "Створити" і зачекайте кілька секунд.

Таблиця простих чисел

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

Справді. Якщо pпросте число, то воно ділиться тільки на себе і на 1, якщо aне ділиться на p, то найбільший спільний дільник aі pдорівнює 1. Тоді pі aвзаємно прості числа.

Твердження 2. Якщо добуток кількох чисел чисел a 1 , a 2 , a 3 , ... ділиться на просте число p, то принаймні одне з чисел a 1 , a 2 , a 3 , ... ділиться на p.

Справді. Якби жодне з чисел не поділялося на p, то числа a 1 , a 2 , a 3 , ... були б взаємно прості числа щодо p. Але зі слідства 3 () випливає, що їхній твір a 1 , a 2 , a 3 , ... також взаємно просте по відношенню до pщо суперечить умові затвердження. Отже, принаймні один з чисел ділиться на p.

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

Доведення. Нехай kскладова кількість, і нехай aОдин з його дільників відмінний від одного і самого себе. Якщо a 1 складове, то має крім 1 і a 1 та інший дільник a 2 . Якщо a 2 число складене, то має крім 1 a 2 та інший дільник a 3 . Розмірковуючи таким чином і враховуючи, що числа a 1 , a 2 , a 3 , ... спадають і цей ряд містить кінцеве числочленів, ми дійдемо якогось простого числа p 1 . Тоді kможна уявити у вигляді

Допустимо існує два розкладання числа k:

Так як k=p 1 p 2 p 3 ... ділиться на просте число q 1 , то принаймні один із множників, наприклад p 1 ділиться на q 1 . Але p 1 проста кількість і ділиться тільки на 1 і на себе. Отже p 1 =q 1 (т.к. q 1 ≠1)

Тоді із (2) можна виключити p 1 та q 1:

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

Розкладання складового числа kможна записати у наступному вигляді

(3)

де p 1 , p 2 , ... різні прості числа, α, β, γ ... цілі позитивні числа.

Розкладання (3) називається канонічним розкладаннямчисла.

Прості числа серед натуральних чисел зустрічаються нерівномірно. В одних частинах ряду їх більше, в інших – менше. Чим далі ми просуваємося числовому ряду, Тим рідше зустрічаються прості числа. Виникає питання, чи існує найбільше просте число? Давньогрецький математик Евклід довів, що простих чисел дуже багато. Нижче ми представимо цей доказ.

Теорема 2. Кількість простих чисел дуже багато.

Доведення. Припустимо, що існує кінцева кількість простих чисел, і нехай найбільш проста кількість дорівнює p. Розглянемо всі числа більше p. За припущенням затвердження, ці числа повинні бути складовими і повинні ділитися принаймні на один із простих чисел. Виберемо число, що є добутком всіх цих простих чисел плюс 1:

Число zбільше pтак як 2pвже більше p. pне ділиться на жодну з цих простих чисел, т.к. при розподілі на кожне з них дає залишок 1. Таким чином ми приходимо до суперечності. Отже існує безліч простих чисел.

Ця теорема є окремим випадком більш загальної теореми:

Теорема 3. Нехай задана арифметична прогресія

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

Справедливе та протилежне. Якщо кожен простий множник числа nвходить принаймні стільки ж разів у число m, то mділиться на n.

Твердження 3. Нехай a 1 ,a 2 ,a 3 ,... різні прості числа, що входять до mтак що

де i=0,1,...α , j=0,1,...,β , k=0,1,..., γ . Зауважимо, що α iприймає α +1 значень, β j приймає β +1 значень, γ k приймає γ +1 значень, ... .