Що таке просте число

Що таке просте число

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

Інструкція

  1. Згідно з основною теоремою арифметики, будь-яке натуральне число, яке більше одиниці, може бути розкладено на твір простих чисел. Виходячи з цього, можна зробити висновок про те, що прості числа є певні «блоки» для натуральних чисел.
  2. Операцію подання натурального числа у вигляді добутку простих називають факторизації або розкладанням на прості множники. Поліноміальні алгоритми розкладання чисел невідомі, але також немає доказів того, що в природі вони не існують.
  3. На складності обчислень, пов’язаних з факторизації чисел, засновані деякі криптосистеми, наприклад, однією з відомих є RSA. Для квантових комп’ютерів існує алгоритм Шора, який дозволяє здійснювати факторизацию чисел з поліноміальною складністю.
  4. Існують алгоритми, за допомогою яких можна здійснювати пошук, а також розпізнавати прості числа. Найпростішими з них є решето Ератосфена, решето Аткіна, решето Сундарама. На ділі ж часто постає завдання не отримання простих чисел, а перевірити, скільки на те, чи є воно простим. Алгоритми, покликані вирішувати подібні завдання, іменуються тестами простоти.
  5. Ще Евклідом був доведений той факт, що простих чисел існує нескінченно багато. Суть його докази, представленого в книзі «Начала», полягає в наступному. Нехай існує кінцеве число простих чисел. Перемножимо їх, після чого додамо до них одиницю. Число, яке вийшло, не може бути розділене на жодне просте число з кінцевого набору без залишку (він буде дорівнює 1). У такому випадку це число ділиться на просте число, яке не входить до складу представленого кінцевого набору. Крім цього, існують також й інші математичні докази нескінченності простих чисел.