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

6.6. Основы алгебры вычетов и их приложение к простейшим криптографическим шифрам Все проблемы, в конечном счете, являются научными проблемами. Б. Шоу ? Подумайте, может ли квадрат некоторого целого числа равняться 1278075? Квадрат какого числа может оканчиваться цифрами 75? Деление с остатком. Разделить натуральное число а на нату­ ральное число b с остатком означает записать его в виде а = qb + г, где q и г — неотрицательные числа, причем г < Ь. При этом q называется частным, а г — остатком от деления а на Ь. Такое деление выполняется уголком. Например, 187 :12= 15(ост. 7). В такой записи сразу видно, что для делимого 187 и делителя 12 частным является число 15, а остаток от деления равен 7. Тог­ да 187 = 15-12 + 7, т.е. а - 187, Ь - 12, q = 15, г - 7. Это представле­ ние не требует, чтобы выполнялось условие а > Ъ. Если а < Ь, то а = О b + г, т.е. q = 0, г - а. Например, разделить 4 на 9 — значит представить его в виде 4 = 0 -9 + 4, где а = г = 4, b - 9, q = 0. Можно обобщить понятие «деление с остатком» на целые чис­ ла: разделить целое а на натуральное b с остатком — значит пред­ ставить а в виде а = qb + г, где q е Z, а 0 < г< Ь. Отметим, что это целиком соответствует операции «взятие целой части». Тогда, если а = qb + г, то = q. Остаток г от деления а на b с остатком будем записывать аналитически: г - amodb. Например, для а = -1 2 , b = 8 имеем -12 = ( -2 ) -8 + 4, для а = = -324, b = -15 имеем -324 = 22 (-15) + 6 . Число а делится нацело на Ь, если остаток г = 0: a - qb. Следствие. Если а и b делятся на с, то при любых целых к и / сумма ка + lb делится на с: т.е. ( а \ с ,Ь \ с , \/к, /, a, b е Z) => ((ка + + lb ) ; с). Действительно, если a - qxc, b = q2c, тогда ка+ lb = kqxc + + lq2c = c(kq\ + lq2). Задача 40. Найти такое число d ф 1, на которое делятся чис­ ла 6 я + 5 и 9л + 2. Найти л. Решение. Если сами числа 6 л + 5 и 9л + 2 делятся на d, то на d делится и разность 3(6л + 5) - 2 (9л + 2) = 15 - 4 = 11 — простое число, т.е. d - 11. Итак, 6 л + 5 = 11 к. Введем т = л - 1, / = к - 1, тогда 6т =111. Поскольку 6 и 11 — взаимно простые натуральные числа, общее решение: т = 11 р, I = 6р. Подставляя, получим л = =т + \ = \\р+ 1. Так как 9 и 11 так же взаимно просты, аналогично 327