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

как (а = 6 )(mod/?). В том случае, когда перед Z>(mod/>) стоит знак = или знак арифметической операции, то Z>(mod/>) означает оста­ ток. Для доказательства неэквивалентности выражений о = £(mod/j) (сравнение) и а = b(modp) (равенство) заметим, что в сравнении а = b(modp) а и b симметричны. Если их поменять местами, то сравнение b =a(modp) будет иметь место и будет полностью эк ­ вивалентно исходному: a s£ (m od /> ) <=> Z>= a(mod/?). Этого свой­ ства нет в выражении а = Z>(modp). Например, 4 = 12(mod8), 12 * 4(mod8). Отношение сравнимости = рефлективно, симметрично и тран- зитивно, следовательно, является отношением эквивалентности. Отдельные классы эквивалентности для отношения сравнимо­ сти (по модулю р) называют вы четами п о м одулю р и обозначают Z р, а раздел математики, изучающий вычеты по модулю, — ал­ геброй вычетов, теорией вычетов или модулярной арифметикой. С в ой с тв а ср а вн ен ий . 1. Два числа, сравнимые с третьим по одному модулю, сравни­ мы между собой: (а =b(modp), b =c(modp)) =>а = c(mod/?). 2. Сравнения можно почленно складывать и вычитать: {а = = 6 (mod/?); с = rf(mod/j)) (а ± с) = (Ь ± Д)(тоб/>). Действительно, если а = £(mod/>) и с = d(modp), то по опреде­ лению (а - b ) \р и (c -d ) \р. Тогда разность (а +c ) - ( b +d) = (а-Ь) + + ( с - d) равна сумме двух слагаемых, каждое из которых делится на р. Значит, (а ± c) =(b ± d)(modp). Поэтому слагаемые можно переносить из одной части сравне­ ния в другую с противоположным знаком. 3. Сравнения можно почленно перемножать: (а =b(modp), с = - d(modp)) => (ас = bd(modp)). 4. Обе части сравнения можно умножить на одно и то же число k € Z: (а = i(m odp )) => (ак = bk (mod р)). Действительно, ак - Ьк = = (а - Ь)к | р. 5. Обе части сравнения и модуль можно умножить на одно и то же число: (а =b(modp)) (ак= bk (modpk)). Действительно, если а =b(modp), то Эк: а = b + кр, умножим на число т, тогда ат = Ьт + ктр, т.е. am = bm (modрт). 6 . Обе части сравнения можно возвести в степень (следствие свойства 3): (а = 6 (mod/?)) => (я" = A"(mod/*)). Впервые понятие сравнения ввел К. Ф. Гаусс в работе «Ариф­ метические исследования» (1802). Алгебра вычетов возникает в тех случаях, когда рассматриваются некоторые циклически повторя­ ющиеся события, например время в течение дня, повторяющееся каждые 24 часа, углы по окружности, повторяющиеся через пе­ риод 2 л, и т.д. Алгебра вычетов —один из тех удивительных разделов матема­ тики, которые рождались в мыслях ученых как некоторые фор­ 329