Арифметичні застосування теорії конгруенцій (стр. 2 из 6)

П. Ферма для простого модуля, а Л. Ейлеру для будь-якого модуля вдалося вказати значення

, при яких має місце рівність . Відповідні теореми, ми їх називатимемо теоремами Ферма - Ейлера, є основою всієї теорії порівнянь і широко використовуються як в теоретичних дослідженнях, так і в арифметичних застосуваннях.

Теорема Ферма. Для будь-якого простого

і будь-якого , що не ділиться на , справедливе порівняння

.

Теорема Ейлера. Для будь-якого модуля

і будь-якого , взаємно простого з , справедливе порівняння

.

2. Ознаки подільності

Розрізняють загальні ознаки, що мають силу для будь-якого m і власні - для окремих значень m.

Загальну ознаку подільності виражає правило, за допомогою якого по цифрах числа N записаного в системі числення з основою g, можна судити про подільність його на інше число m.

Французький математик Блез Паскаль (1623-1662) знайшов загальну ознаку подільності. Її можна сформулювати наступним чином:

Теорема 7 (загальна ознака подільності Паскаля). Для того, щоб число N, записане в довільній g-ітій системі числення у вигляді:

,

ділилося на число m, необхідно і достатньо, щоб число

ділилося на m (де - цифри числа N, а - абсолютно найменші вирахування відповідних степенів по модулю m, і = 1, 2.,n). Доведення. Нехай , де - абсолютно найменше вирахування числа по модулю m, (i = 1, 2., n). Тоді

(1)

Число N ділиться на m тоді і тільки тоді, коли

(2)

З рівнянь (1) і (2) і їх транзитивності отримуємо умову, рівносильну умові (2):

. (3)

З доведеного випливає: для того, щоб N ділилося на т, необхідно і достатньо, щоб Q ділилося на m.

Теорема доведена.

Як наслідок із загальної ознаки Паскаля витікають різні ознаки подільності. Розглянемо деякі з них (найчастіше використовувані на практиці).

Наслідок 1. Нехай m - дільник числа g - 1. Для того, щоб число, записане в g-ітій системі числення, ділилося на m, необхідно і достатньо, щоб сума його цифр ділилася на m.

Доведення. В даному випадку

, а ; тоді , тобто, а тому:

.

Таким чином, для того, щоб N ділилося на m, необхідно і достатньо, щоб сума цифр цього числа ділилася на m.

Для чисел, записаних в десятковій системі, з формульованої ознаки випливають відомі ознаки подільності на 9 і 3.

Наслідок 2. Нехай m - дільник числа g + I. Для того, щоб число, записане в g-ітій системі числення, ділилося на m, необхідно і достатньо, щоб різниця між сумами цифр на парних і непарних місцях ділилася на m.

Доведення. В даному випадку Звідси витікає затвердження слідства. Для чисел, записаних в десятковій системі, отримуємо

а ; тоді , тобто , а тому .

Для чисел, записаних в десятковій системі, отримуємо відому ознаку подільності на 11: для того, щоб число ділилося на 11, необхідно і достатньо, щоб різниця між сумами цифр на парних і непарних місцях ділилася на 11. Наприклад, число 25 697 058 не ділиться на 11, оскільки різниця (2 + 6 + 7 + 5) - (5 + 9 + 0 + 8) = 20-22 == - 2 не ділиться на 11.

Число 905 784 ділиться на 11.

Наслідок 3. Нехай m - дільник числа

. Для того, щоб число, записане в g-ітій системі числення, ділилося на m, необхідно і достатньо, щоб число, записане останніми k цифрами даного числа, ділилося на m.

Доведення. В даному випадку

для до, а тому

.

Або

. (*)

З (*) витікає твердження наслідку.

Для чисел, записаних в десятковій системі, із наслідку 3 випливає цілий ряд ознак подільності.

1) Основа

(де ) ділиться на 2, 5, 10.

В цьому випадку отримаємо ознаки подільності на 2, 5, 10.

а) Для подільності числа на 2 необхідно і достатньо, щоб остання цифра була парною.

б) Для подільності числа на 5 необхідно і достатньо, щоб остання цифра ділилася на 5 (остання цифра 0 або 5).

в) Для подільності числа на 10 необхідно і достатньо, щоб воно закінчувалося нулем.

2) Дільником числа

(де ) є числа 4, 25, 50, 100.

Застосовуючи наслідок 3, отримуємо ознаки подільності на 4, 25, 50, 100.

Зокрема, для того, щоб число ділилося на 4, необхідно і достатньо, щоб число, записане останніми двома (

) цифрами, ділилося на 4.

3) Аналогічно можна вивести ознаки подільності на дільників числа

, тобто на числа 8, 125,. Тут потрібно розглядати число, записане останніми трьома цифрами даного числа.

Теорема 8. Для того, щоб число ділилося на 7, або на 11, або на 13, необхідно і достатньо, щоб різниця між числом записаним останніми трьома цифрами, і числом, записаним цифрами, які залишилися даного числа (або навпаки), ділилася на 7, або на 11, або на 13.

Доведення. Будь-яке число N можна представити у вигляді

де - число, записане останніми трьома цифрами числа N, а n - цифрами, які залишилися (приклад: 829 296 = 829 1000 + 296).