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

.

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.

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

.

Або