Спирина, М.С. Дискретная математика

получим то же решение для уравнения (9л + 2) j 11. Итак, л = 1 \р + 1 для любого целого р: п = .„-21, -10 , 1, 12, 23... Сравнение по модулю. Рассмотрим множество натуральных чисел. 9 . На какую цифру оканчивается число 22003? Как известно, натуральные степени числа 2 оканчиваются циф­ рами {2, 4, 8 , 6 }. Действительно: 2, 4, 8 , 16, 32, 64 и т.д. Опреде­ лим функцию / : N -» {2, 4, 8 , 6 }, которая ставит в соответствие каждому натуральному числу л последнюю цифру числа 2 ". Эта функция периодична с периодом 4, т .е . / (и ) = / ( л + 4) = / ( л + 4А). И обратно: / (л ) = / ( л - 4) = / ( л - 4А). Для любого л нужно найти минимальное натуральное т, такое, что f{m ) = f (m + 4к) - f(n). Но это задача на остаток: к —частное деления л на 4, лг —остаток. Поэтому последняя цифра числа 2" зависит от остатка деления f / («m o d 4 ) , если л mod 4 * 0 ; показателя на 4: / ( л ) = \ [ / (4 ) = 6 , если л т о б 4 = 0 (л:4). В таком случае, так как 2003 = 500 ■4 + 3, т о /(2003) = / (3 ) = 8 , и число 2 2003 оканчивается цифрой 8 . Таким образом, множество всех возможных показателей состоит из четырех подмножеств Уя е N: 4 к, 4 к+ 1, 4А+ 2, 4А+ 3. Тогда У л е N все целые числа разбиваются на р подмножеств, которые соответствуют числу, полученному в остатке при делении на р. Такие подмножества, зависящие от остатка деления на р, на­ зовем: 0 если а mod/г = 0 , т.е. а\р; 1 если ornodp= 1, т.е. (а - 1) \ р (или Эк:а - кр 2 если amodp- 2, т.е. (а - 2) \р (или Эк:а - кр р - 1 если amodp = р - 1, т.е. (а + 1) '■р (или Эк: а = кр + + (р - 1 )). Очевидно, что любое число а е Z принадлежит одному из этих р подмножеств. Причем разность любых двух чисел одного под­ множества делится на р, а разность чисел из разных множеств не должна делиться на р. Два целых числа, разность которых кратна натуральному числу р > 2 (а - b \р), называются сравнимыми п о м одулю р. Обозначе­ ние а = b(modp), если ЗА: е Z: а - b = кр. Это значит, что числа а и b сравнимы по модулю р тогда и только тогда, когда они принадлежат одному подмножеству, т.е. дают одинаковые остатки при делении на р. Например, 36 = = 16(mod 10); -24 = 6(mod30). Отметим, что в записи a =b(modp) выражение b(modp) озна­ чает не «остаток от деления b на р, который сравним с о», а если расставить логические скобки, то а = b (mod/)) следует понимать 328