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

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

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

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

Приклади:

а) число 9 має три дільники (1, 3 і 9), значить, воно складене;
б) число 17 має два дільники, значить, воно просте;
в) число 1 має лише один дільник - саме це число, тому воно не є ні простим, ні складеним.

Правило: Розкласти складене число на прості множники означає записати дане число у вигляді добутку простих чисел - дільників даного числа.

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

Приклади:

а) 180 = 2 · 2 · 3 · 3 · 5;

б) 1368 = 2 · 2 · 2 · 3 · 3 · 19.

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

РОЛЬ ПРОСТИХ ЧИСЕЛ У МАТЕМАТИКЕ

Кожне натуральне число, більше одиниці, ділиться принаймні на два числа: на 1 і на саме себе. Якщо ні на яке інше натуральне число воно на ціле не ділиться, то називається простим, а якщо у нього є ще якісь цілі дільники, то складеним. Не про всякий числі можна відразу сказати, просте воно чи складене. Візьмемо, наприклад, число 1999. Якщо немає під рукою спеціальних довідкових таблиць або помічника комп'ютера, то доведеться згадати про старе, але надійному решеті Ератосфена. Старовинний спосіб, придуманий ще в 3 ст.До н. е.. Ератосфеном Кіренським, зберігачем знаменитої Олександрійської бібліотеки.

Випишемо кілька поспіль чисел, починаючи з 2. Двійку відберемо в свою колекцію, а інші числа, кратні 2, закреслимо. Найближчим не закресленим числом буде 3. Візьмемо до колекції і його, а всі інші числа, кратні 3, закреслимо. При цьому виявиться, що деякі числа вже були викреслені раніше, як, наприклад, 6, 12 та інші.Наступне найменше не закреслено число-це 5. Беремо п'ятірку, а інші числа, кратні 5, перекреслюємо.Повторюючи цю процедуру знову і знову, ми врешті-решт досягнемо того, що не закресленими залишаться одні лише прості числа-вони немов просіяти крізь решето. Тому такий спосіб і отримав назву решето Ератосфена. Чи можна, повторювати поетові, сказати, що простих чисел стільки, "скільки зірок на небі, скільки риб у воді"? Відповідь знаходимо в дев'ятій книзі знаменитого твору Евкліда "Начала" - нетлінного пам'ятника Стародавнього світу. Двадцята теорема в цій книзі стверджує: "Перших (простих) чисел існує більше будь-якого вказаного числа їх".

Ось доказ цієї теореми. Припустимо, що існує якесь найбільше просте число P. Тоді перемножимо всі прості числа, починаючи з 2 і закінчуючи P, і збільшимо отримане твір на одиницю: 2 3 5 7 * ... P + 1 = M.Якщо число М складене, то вона повинна мати принаймні один простий дільник. Але цим дільником не може бути ні одне з простих чисел 2, 3, 5, ..., Р, оскільки при розподілі М на кожне з них отримуємо в залишку 1.Отже, число М або саме просте, або ділиться на просте число, більше Р. Значить, припущення, що існує найбільша просте число Р, напевно й безліч простих чисел нескінченно.

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

Першу відому нам таблицю простих чисел склав італійський математик П'єтро Антоніо Катальді в 1603 р. Вона захоплювала всі прості числа від 2 до 743

У 1770 р. Німецький математик Йоганн Генріх Ламберт опублікував таблицю найменших дільників всіх чисел, не переважаючих 102000 і не діляться на 2, 3, 5. Вклавши в цю працю воістину колосальні зусилля, Ламберт гарантував безсмертя тому, хто доведе таблицю дільників до мільйона. На його заклик відгукнулися багато обчислювачі.

До середини 19 століття вже були складені таблиці найменших дільників не тільки першого мільйона, а й наступних, в плоть до 9. В цей же час в пресі з'явилися повідомлення, що подавалися абсолютно фантастичними: у Віденську академію надійшло 7 великих томів рукописних таблиць "Великий канон дільників всіх чисел, які не діляться на 2, 3 і 5, і простих чисел між ними до 100 330 201". Автором цієї праці був Якуб Філіп Кулик, професор вищої математики Празького університету.

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

Деякі уявлення про розподілу простих чисел мали вже стародавні греки. З докази Евкліда випливає, наприклад, що вони не зібрані разом, а розкидані по всій числовій осі. Але як часто?

У 1845 р французький математик Жозеф Бертан, досліджуючи таблицю простих чисел у проміжку від 1 до 6000000, виявив, що між числами n і n 2 - 2, де n> 3, міститься принаймні одне просте число. Надалі це властивість отримало назву постулату Бертрана, хоча самому Бертані обгрунтувати його так і не вдалося.Довів його в 1852 г російський математик Пафнутій Львович Чебишев. З результату Чебишева слідувала і більш точна оцінка. Таким чином, навіть серед дуже великих чисел прості числа не так вже й рідкісні.

З іншого боку, існують проміжки, що включають тисячі, мільйони, мільярди і взагалі яке завгодно велику кількість поспіль стоять натуральних чисел, серед яких не можна знайти жодного простого! Справді, задавшись довільним великим натуральним числом к, побудуємо ряд чисел к! +2, К! +3, ..., К! + К (тут до! = 1 * 2 * 3 * ... * к). Кожне з цих чисел складене. Наприклад, число к! + М ділиться на м, оскільки до! ділиться нам і саме м ділиться на м.

Прості числа, що діляться тільки на одиницю і на самих себе (2,3,5,7,11,13,17, ...), з давніх часів привертають увагу математиків. Більше двох тисяч років тому великий давньогрецький математик Евклід довів, що ряд простих чисел нескінченний. Прості числа слідують одне за одним по закону, який ще не знайдений. Ці числа то на довго зникають з натурального ряду, то по є в ньому часто, а іноді і по сусідству: 11,13,; 5971847,5971849.

Професор І.К. Андронов в книзі <<Арифметика натуральних чисел>> наводить розповідь про уявному подорож по нескінченній дорозі простих чисел: <<Подумки візьмемо прямо лінійний провід, що виходить з класної кімнати в світовий простір, що пробиває земну атмосферу, що минає туди, де Місяць здійснює обертання, і далі за вогненна куля Сонце, в світову нескінченність.

Подумки підвісимо на провід через кожен метр електричні лампочки, нумеруючи їх, починаючи з ближньої: 1,2,3, ..., 1 000, ..., 1 000 000, ..., включимо струм з таким розрахунком, щоб спалахнули всі лампочки з простими номерами, і полетимо у районі дроти>>.

Разом з автором цієї книги ми починаємо рух з першої електричної лампочки, яка не освітила нам старту, вона не горить, так як її номер (одиниця) не є простим числом. Відразу за нею дві лампочки з номерами 2 і 3 включені, ці числа прості. Залишимо позаду гарячі лампочки 5 і 7. Вони пронумеровані простими числами. На нашому довгому шляху дуже рідко будуть потрапляти числа-близнюки. Ось промайнули наступні числа-близнюки: 11 і 13, 17 і 19. Ми швидко набираємо швидкість; залишаючи позаду лампочки 101 і 103, 827 і 829; тепер рідше і рідше зустрічаються освітлені острівці з лампочок, пронумеровані простими числами-близнюками. Ось на тлі темряви і мороку засяяли лампочки з номерами 10   016   957 і 10  016   959; це остання пара відомих простих чисел-близнюків. Можливо, десь у нескінченних просторах порадують наш погляд ще пара світяться лампочок, або такі близнюки зникнуть на завжди. Нам зустрічаються ділянки, досить часто освітлювані лампочками, але частіше шлях проходить в темряві. З першого мільйона промайнуло всього 78   498 палаючих лампочок, 921   502 не горіли.

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

Як і простір, безліч простих чисел нескінченно. Нескінченний ряд чисел, який ми в результаті рахунку предметів, називається натуральним рядом чисел: 1,2,3,4,5, .... Серед натурального ряду чисел ми виділяємо прості числа. Простими числами називаються такі, які діляться на 1 і на самих себе. Найменше просте число2.

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

Спосіб Ератосфена складання таблиць простих чисел надзвичайно простий і не вимагає перевірки чисел на подільність. Він скористався особливим методом, який був названий на честь вченого <<Решето Ератосфена>>. Щоб очистити зерно, ми його просіваємо. Подібно до цього Ератосфен <<просівали>> числа натурального ряду, користуючись особливим прийомом.

Припустимо, що були виписані (в таблиці з 10рядов) все по отже від 1 до 100. Перш за все треба <<викинути>> всі парні числа, крім 2. Підкресливши число2, інші числа, що діляться на 2, закреслимо. Після 2 в таблиці йде просте число 3. Підкреслимо число 3 як просте, а всі інші, що ділиться на 3, закреслимо. (Числа, кратні 3, стоять на місцях через два на третє.) Тепер наступне просте число 5, яке знову підкреслюємо; викидаємо всі числа, кратні 5, які розташовані на місцях через четверте на п'яте, вважаючи раніше закреслені.Далі підкреслюємо наступне число 7 і перекреслюємо числа, що діляться на 7, і т. д. Зауважте, що з усіх натуральних чисел не закресленими залишаються прості числа. Ератосфен у кожного складового числа прокладав отвір, і виходило щось на зразок решета, через яке ці складові числа <<просівали>>.

Давньо грецьких вчених зацікавило: скільки може бути простих чисел в натуральному ряді? Відповів на це питання Евклід, довівши, що простих чисел нескінченна безліч.

Однак спосіб Ератосфена не зміг задовольнити вчених, і вони намагалися знайти формулу простих чисел. Протягом багатьох сторіч це зробити не вдавалося. У ряду простих чисел було знайдено багато цікаві закономірності, але поставлена ​​задача залишалася без відповіді. Першим наблизився до вирішення проблем простих чисел П.Л. Чебишев.

У 1750 р. Леонард Ейлер встановив, що число 2 ³ ¹ - 1 є простим. Воно залишалося найбільшим з відомих простих чисел більше ста років. У 1876 р. Французький математик Лукас встановив, що величезна кількість

2127 - 1 = 170   141   183   560   469   231   731   687   303   715   884   105727 
також просте. Воно містить 39 цифр. Для його обчислення були механічні настільні рахункові машини. У 1957 р. було знайдено наступне просте число: 23217 - 1. А просте число 244   497 - 1 складається з 13 000 цифр.