4. Теорема про подільність добутку

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

Доведення: Нехай множник а добутку аb ділиться на число n, тобто а = nq. Тоді аb = (nq)b = n (qb). Теорему доведено.

Аналогічно доводиться твердження для більшого числа множників.

Наслідок:Якщо в добутку аb множник а ділиться на m, а множник b ділиться на n, то добуток аb ділиться на mn.

Наприклад, 24∙36 ділиться на 108, бо 108 = 12∙9.

5. Загальна ознака подільності б.Паскаля.

Теорема (ознака Паскаля): Будь-яке число а, задане в позиційній системі числення з основою q у вигляді (1) ділиться на натуральне число bÎN тоді і тільки тоді, коли на нього ділиться сума добутків цифр цього числа на остачі, утворені при діленні на число b, відповідних степенів основи числення q.

Символічно теорема запишеться так:  (ІІ). У записі (ІІ)  ,…, - це цифри числа а.  - це остачі від ділення на число b степенів основи системи числення q, тобто чисел  .

Доведення: Розглянемо ціле невід’ємне число а, яке ділиться на натуральне число в і представлене у вигляді  (І). Для доведення теореми нам потрібно довести, що виконується твердження:  (ІІ), де  ...  - це цифри числа а, а  - це остачі від ділення на число b степенів основи системи числення q, тобто чисел  . Оскільки в умові теореми є слова тоді і тільки тоді, то доведення складається із двох частин. У першій частині доведемо необхідну умову: «якщо  , то сума добутків цифр цього числа на остачі від ділення на число b степенів основи системи числення ділиться націло на b» (див. ІІ), а у другій – достатню умову: «якщо  , то  ”. Справедливість цієї теореми приймемо без доведення.

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

Ознака 1: для того, щоб ціле невід’ємне число a ділилося на 2 необхідно і достатньо, щоб воно закінчувалось парною цифрою.

Доведення: розглянемо aє . Представимо його у такому вигляді:  (ІІІ). Щоб використати для доведення теореми ознаку подільності Паскаля, знайдемо остачі від ділення степенів основи числа 10 на число 2. Оскільки  , то  , а тому добутки  . Отже, число a буде ділитися націло на 2, тоді, коли  , а це буде тоді , коли  або 2, або 4, або 6, або 8. Теорема доведена.

Попередню теорему можна довести і не використовуючи ознаку подільності Б.Паскаля. При цьому доведеться доводити необхідну та достатню умови. Доведемо необхідну умову: „якщо число закінчується парною цифрою, то воно ділиться націло на 2”. За умовою теореми число закінчується парною цифрою, а тому число можна представити у вигляді суми двох доданків так: а=10в+0, а=10с+2, а=10d+4, а=10f+6 і а=10e+8. За теоремами про подільність суми і добутку кожна сума ділиться націло на 2, а тому і число а ділиться націло на 2. Отже, необхідну умову доведено.

Доведемо достатню умову: „якщо число а ділиться націло на два, то воно закінчується парною цифрою”. Представимо число а у вигляді суми а=10b+r. Звідси r=a-10b. Оскільки за умовою a 2, а 10b 2 (за теоремою про подільність добутку), то і різниця (a-10b)  2, тобто r 2. r – це одноцифрове число, яке може ділитися націло на 2, якщо воно дорівнює одному з чисел 0, 2, 4, 6, 8. Це означає, що дане число а закінчується парною цифрою. Таким чином, достатню умову доведено. Отже, теорему доведено повністю (пропонуємо студентам довести цим способом самостійно ознаки подільності на 5, на 4 і на 25!).

Ознака 2:для того, щоб ціле невід’ємне число a ділилося на 5 необхідно і достатньо, щоб воно закінчувалося цифрами 0 або 5.

Ознака 3: для того, щоб ціле невід’ємне число а ділилося націло на 3, необхідно і достатньо, щоб сума цифр цього числа ділилася на 3.

Доведення: використаємо ознаку подільності Паскаля. Представимо число a у вигляді:  і знайдемо остачі від ділення степенів числа 10 на 3. Маємо: 10:3=3(ост.1), 100:3=33(ост.1), тобто легко бачити, що  , а тому сума добутків цифр числа a на остачі від ділення на 3 степенів числа 10 перетвориться в суму цифр числа, тобто:  . Якщо ця сума ділиться на 3, то й число поділиться на 3. Теорема доведена.

Ознака 4: для того, щоб ціле невід’ємне число а ділилося націло на 9, необхідно і достатньо, щоб сума цифр цього числа ділилася на 9.

Ознака 5: для того, щоб ціле невід’ємне число а ділилося націло на 4, необхідно і достатньо, щоб число, утворене двома останніми цифрами числа a, ділилося націло на 4.

Доведення: представимо число a у вигляді:  . і знайдемо остачі від ділення степенів числа 10 на 4. Легко бачити, що  . Тому сума добутків цифр числа a і остач від ділення степенів числа 10 на 4 перетвориться у суму  , а це означає, що число a можна представити у вигляді суми двох доданків. Оскільки перший доданок ділиться на 4, то для подільності даного числа a на 4 необхідно і достатньо, щоб виконалась умова  . Таким чином, теорема доведена.

Ознака 6: для того, щоб ціле невід’ємне число а ділилося націло на 25, необхідно і достатньо, щоб число, утворене двома останніми цифрами числа a, ділилося націло на 25.

Покажемо застосування доведених ознак до розв’язування прикладів на наступній вправі.

Вправа: з’ясувати, чи ділиться на 2, 3, 4, 5, 9, 25 число 9876501342.

Розв’язання: а) це число ділиться на 2, бо закінчується цифрою 2. Оскільки дане число закінчується цифрою 2, то воно не поділиться на 5.

б) дане число за ознакою подільності ділиться на 3, оскільки сума його цифр (9+8+6+5+7+0+1+3+4+2=45) 3. Оскільки  , то дане число також кратне 9.

в) щоб з’ясувати, чи ділиться дане число на 4, утворимо число із двох останніх цифр, тобто число 42. Оскільки  , то дане число не ділиться на 4. Оскільки число, утворене двома останніми цифрами 42 не ділиться націло на 25, то число 9876501342 не ділиться на 25.

6. Найбі́льший спі́льний дільни́к (НСД) двох або більше невід'ємних цілих чисел — найбільше натуральне число, на яке ці числа діляться без остачі.

Найбільший спільний дільник двох чисел a і b позначається як НСД(a, b), деколи (a, b). В англомовній літературі прийнято вживати позначення gcd(a, b).

Число 54 може бути виражене як добуток двох інших цілих чисел кількома способами:

54х1=27х2=19х3=9х6

{\displaystyle 54\times 1=27\times 2=18\times 3=9\times 6.\,}Отже дільниками числа 54 є:

1,2,3,6,9,18,27,54.{\displaystyle 1,2,3,6,9,18,27,54.\,}

Аналогічно дільниками числа 24 є:

24 х 1 = 12 х 2 = 8 х 3 = 6 х 4.

1,2,3,4,6,8,12,24.

{\displaystyle 24\times 1=12\times 2=8\times 3=6\times 4.\,} {\displaystyle 1,2,3,4,6,8,12,24.\,}Числа, які знаходяться в обох цих списках, є спільними дільниками чисел 54 та 24:{\displaystyle 1,2,3,6.\,}

1,2,3,6

Найбільшим серед них є число 6. Воно є найбільшим спільним дільником чисел 54 та 24. Можна записати:{\displaystyle (54,24)=6.\,}

(54,24) = 6

Найбільший спільний дільник використовується для скорочення дробів. Наприклад, НСД(42, 56) = 14, тому,

Властивості:

• НСД є комутативною функцією: НСД(a, b)= НСД(b, a).

• 1≤ НСД(a, b)  min(|a|,|b|≤≤ min (│a│,│b│)

• НСД(a, b, c, d) = НСД(НСД(a, b), НСД(c, d))

• НСД(a, b) =|ab|/НСК(a, b), де НСК(a, b) найменше спільне кратне чисел a, b.

{\displaystyle b=2^{r_{2}}\cdot 3^{r_{3}}\cdot \dots \cdot p_{k}^{r_{p_{k}}}}Спільним кратним натуральних чисел а і b називається натуральне число, кратне кожному з даних чисел.

Найменшим спільним кратним натуральних чисел а і b називається найменше число з усіх спільних кратних даних чисел. Найменше спільне кратне позначається НСК (а, b) або К (а, b).

Візьмемо числа 12 і 18. Кратними числа 12 є: 12, 24, 36, …, а кратними числа 18 – 18, 36, 54, … Числа 12 і 18 мають спільні кратні 36, 72, …Серед них найменше – 36. Отже НСК(12, 18) = 36.

Найменше спільне кратне має такі найпростіші властивості:

1. Для будь-яких натуральних чисел а і b існує єдине НСК.

2. Найменше спільне кратне чисел а і b не менше більшого з даних чисел, тобто якщо а> b, то НСК(а, b) ≥ а.

3. Кожне спільне кратне даних чисел а і b ділиться на найменше спільне кратне цих чисел.

Теорема: НСД(а,b) є найменшим спільним кратним усіх спільних дільників чисел а і b.

 Cпосіб обчислення НСК і НСД за канонічним розкладом чисел

Знайдемо НСК і НСД чисел 360 і 525. Ці числа можна подати у канонічному вигляді: 360 = 2³ ∙ 3² ∙ 5; 525 = 3 ∙ 5² ∙ 7. У розклад на прості множники НСД цих чисел повинні ввійти всі спільні прості множники, причому кожний з них треба взяти з найменшим показником, з яким він входить в канонічні розклади даних чисел. Отже НСД(360, 525) = 3 ∙ 5 = 15.

У розлад на прості множники НСК (360, 525) повинні ввійти всі прості множники, які входять принаймні в один розклад, причому кожний з них треба взяти з найбільшим показником. НСК(360, 525) = 2³ ∙ 3² ∙ 5² ∙ 7 = 12 600.

Теорема:НСК (а, b) ∙ НСД (а, b) = а ∙ b.

Наслідок:Якщо НСК (а, b) = 1, то НСК (а, b) = а ∙ b .