Прості і складені числа

ПРОСТІ І СКЛАДОВІ ЧИСЛА

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

З іншого боку, для будь-якого натурального n> 1 серед чисел n + 1, n + 2, ..., n. - 1 є просте число.

Дійсно, якщо числа n + 1, n + 2, ..., n. - 2 складові, то все їх подільники менше або дорівнюють n. Число n. - 1 не ділиться на 2, 3, ..., n. Якби воно поділялося на одне з чисел n + 1, n + 2, ..., n. - 2, то воно поділялося б і на число менше або рівне n. Отже, n. - 1 не ділиться ні на одне менше число, більше 1. Отже, n. - 1 - просте.

Найважливішими результатами в області розподілу простих чисел є результати Л. Ейлера, П.Л. Чебишева і Ж. Адамара.


Теорема Ейлера стверджує, що відношення числа простих чисел, що не перевершують n. до самого числа n прагне до нуля при n прагне до нескінченності.
Теореми Чебишева і Адамара уточнюють теорему Ейлера. Зокрема, теорема Адамара (1894 г.) стверджує, що число простих чисел, що не перевершують n. прямує до нескінченності так само, як і ставлення
Протягом століть велися пошуки формул для знаходження простих чисел. Багато прагнули до відкриття нових простих чисел. Одним з них був французький математик М. Мерсенн (1588-1648), який шукав прості числа виду 2 p- 1, і в честь якого ці числа називаються простими числами Мерсенна.
Зауважимо, що числа виду an - 1, де a - натуральне число, більше 2, не є простим. Це випливає з формули

яка доводиться перемножением виразів, що стоять в дужках.

В даний час відомо 47 простих чисел Мерсенна. Останнє, 47-е число М42643801 має 12837064 цифр.
Числа Мерсенна безпосередньо пов'язані з досконалими числами - такими, які дорівнюють сумі всіх своїх дільників (включаючи 1, але виключаючи саме число). Вчинені числа були відомі ще в Стародавній Греції. Вони були у великій пошані вважалися еталоном гармонії і краси. Їм приписувалися містичні властивості.
Найменшим досконалим числом є число 6 = 1 + 2 + 3. За ним слідує число 28 = 1 + 2 + 4 + 7 + 14, далі число 496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 .
Зв'язок між досконалими числами і числами Мерсенна встановив Евклід.
Теорема. Якщо Mp = 2 p - 1 - просте число Мерсенна, то число 2 p- 1 (2 p - 1) є досконалим.
Доведення. Випишемо подільники числа 2 p- 1 Mp. менші самого числа: 1, 2, 2 2. ... 2 p- 1. Mp. 2Mp. 2 + 2 Mp. ... 2 p- 2 Mp. Порахуємо їх суму. маємо


Л. Ейлер довів, що числами виду 2 p- 1 (2 p - 1), де 2 p - 1 - просте число Мерсенна, вичерпуються всі парні досконалі числа. В даний час відомо 47 парних скоєних числа. Невідомо, нескінченно багато таких чисел чи ні. Питання про існування непарних досконалих чисел також залишається відкритим.
Розглянемо ще один тип чисел, введених французьким математиком П. Ферма (1601 - 1665). Це числа виду. Показник 2 n тут взятий не випадково. Доведемо, що числа виду 2 m +1 можуть бути простими лише в разі, коли m = 2 n. Для цього скористаємося формулою

яка доводиться безпосереднім перемножением дужок. З неї випливає, що числа виду a 2 k +1 +1 при натуральних k і a> 1 є складовими. Якщо m має непарний дільник, тобто m = l (2k + 1), то 2 m +1 = 2 l (2 k +1) +1 = (2 l) 2 k +1 +1 - складене число.

Ферма припускав, що все числа виду є простими. Дійсно, перші п'ять чисел Ферма F0 = = 3; F1 = = 5; F2 = = 17; F3 = = 257; F4 = = 65537 є простими. Однак Л. Ейлер довів, що наступне число Ферма є складовим F5 = 4 294 967 297 = 641 6 700 417.

До сих пір невідомо, чи існують інші прості числа Ферма. Невідомо також нескінченно чи ні безліч складових чисел Ферма.

Числа Ферма пов'язані з завданням побудови правильних багатокутників за допомогою циркуля і лінійки.
Ще стародавні греки займалися побудовою правильних багатокутників. Вони вміли будувати 2 n -угольнікі 3 2 n -угольнікі 5 2 n -угольнікі, 15 2 n -угольнікі.

Остаточне вирішення питання про те, які правильні багатокутники можна побудувати за допомогою циркуля і лінійки, було отримано лише в 1796 році німецьким математиком К.Ф. Гауссом (1777 - 1855). Він довів, що правильний n -угольнік може бути побудований за допомогою циркуля і лінійки тоді і тільки тоді, коли n = 2 mp1 ... pk. де числа p1, ..., pk - різні прості числа Ферма. Зокрема, з цієї теореми випливає, що правильні 7-кутник, 9-кутник, 11-кутник, 13-кутник не можуть бути побудовані циркулем і лінійкою.

Завдання.

  1. Доведіть, що число 1001 - складене.

  2. Доведіть, що число 9991 - складене.

  3. Доведіть, що числа виду 8 n + 1 - складові.

  4. Доведіть, що число 2 9 +5 12 - складене.

  5. Доведіть, що число 222 555 + 555 222 - складене.

  6. Доведіть, що числа виду n 4 + 4 - складові при n> 1.

  7. Знайдіть всі прості числа p. для яких p + 10 і p + 14 - прості.

  8. Знайдіть всі прості числа p. для яких 2p + 1 і 4p + 1 - прості.

  9. Знайдіть всі прості числа p. для яких 8p 2 + 1 - просте.

  10. Знайдіть всі прості числа p. для яких 4p 2 + 1 і 6p 2 + 1 - прості.

  11. Числа p і p 2 +2 - прості. Доведіть, що число p 3 + 2 - просте.

  12. Знайдіть всі натуральні n. при яких 2 n - 1 і 2 n + 1 - прості.


1. Гарднер М. Математичні дозвілля. - М. Мир, 1972.
2. Гарднер М. Математичні новели. - М. Мир, 1974.