Метод пробних ділень

На цій теоремі базується також метод пробних ділень, або метод Леонардо Фібоначчі. Опишемо алгоритм цього метода.

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

1. Знайти .

2. Виписати всі прості числа, які не перевищують .

3. Перевірити, чи ділиться n на виписані прості числа. Якщо n ділиться хоча б на одне з виписаних простих чисел, то n буде складеним, якщо не ділиться – простим.

Приклад 2. Визначити, простим чи складеним є число: а) 247; б) 397.

а) Знаходимо і виписуємо всі прості числа, які не перевищують 15: 2, 3, 5, 7, 11, 13.

247: 13 = 19, отже, число 247 = 13 × 19 – складене.

б) , виписуємо всі прості числа до 19 включно:

2, 3, 5, 7, 11, 13, 17, 19.

Число 397 не ділиться на жодне з виписаних простих чисел, тому воно просте.

Теорема (Основна теорема аріфметики). Кожне, відмінне від 1, натуральне число n можна записати у вигляді добутку простих чисел єдиним способом, якщо не брати до уваги порядку розміщення співмножників.

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

У розкладі n = р ₁× р ₂×…× р_s (2) натурального числа n на прості множники р ₁, р ₂,…, р_s деякі з цих множників можуть повторюватись. Якщо простий множник р_і повторюється у розкладі k раз, то його називають k -кратним множником числа n, або кажуть, що множник р_і має кратність k.

Позначимо символами р ₁, р ₂, …, р_m (m Î N) попарно різні множники у розкладі (2). Нехай множник р_і (і = 1,…, m) має відповідну кратність k_i. Тоді розклад числа n у добуток простих множників можна записати так:

n = р ₁ ^k1 × р ₂ ^k2 ×…× р_m ^km , де k_i >0, і = 1,…, m.

Цей запис називають канонічним розкладом числа n на прості множники. Канонічний запис натурального числа єдиний. Процес розкладу числа на прості множники називають факторизацією.

Приклад 1. Знайти канонічний розклад числа12600, 3887.

а) Застосуємо ознаки подільності:

12600 = 126×100 = 2×63×25×4 = 2×3²×5² ×2² = 2³×3²×5²×7.

б) Дане число не має малих дільників (2,3,5,7), тому використаємо метод пробних ділень:

»62;

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 49, 53, 59,61;

3887=13×299

» 17

2, 3, 5, 7, 11, 13, 17

3887=13×299=13∙13∙23= 13²∙23.

Наслідок. Якщо натуральні числа а і b, відмінні від 1, записано в формі

а = р ₁ ^{k 1} ×р ₂ ^{k 2} ×…×р_m ^km, k_i ≥0,

b = р ₁ ^{t 1}× р ₂ ^{t 2}×…× р_m^tm, t_i ≥0,

то а b тоді і тільки тоді, коли k_i ≥ t_i, і = 1,…, m.

Цей наслідок іноді називають загальною ознакою подільності натуральних чисел.