Теория делимости

Теперь кратко обсудим теорию делимости — тема, с которой мы часто сталкиваемся в криптографии. Если a не равно нулю, а r = 0, в равенстве деления мы имеем

a = q × n

Мы тогда говорим, что a делится на n (или n — делитель a). Мы можем также сказать, что a делится без остатка на n. Когда мы не интересуемся значением q, мы можем записать вышеупомянутые отношения как a|n. Если остаток не является нулевым, то n не делится, и мы можем записать отношения как a†n.

Целое число 4 делит целое число 32, потому что . Это можно отобразить как 4|32. Число 8 не делит число 42, потому что . В этом уравнении число 2 — остаток. Это можно отобразить как 8†42.

а. Отображение делимости 13|78, 7|98, –6|24, 4|44, и 11 | (–33).

б. Отображение неделимости 13†27, 7†50, – 6†23, 4†41, и 11†(–32).

Свойство 1: если a|1, то a=±1.

Свойство 2: если a|b и b|a, то a=±b

Свойство 3: если a|b и b|c, то a|c

Свойство 4: если a|b и a|c, то a|(m × b + n × c), где m и n — произвольные целые числа.

а. Если 3|15 и 15|45 то, согласно третьему свойству, 3|45.

б. Если 3|15 и 3|9, то, согласно четвертому свойству, , что означает 3|66.