2born (2born) wrote,
2born
2born

Categories:

Что такое mod

Никогда этого не понимал, и попросил разъяснить. Спасибо d_integral (вытащено из комментов к http://d-integral.livejournal.com/37870.html):

Попробую. В общем, есть какое-то число, по модулю которого мы хотим записывать обычные числа, что-то складывать, умножать, и прочее. Проще всего для начала взять 12, тогда сразу все понятно. И смотреть на часы. Например, 14 часов это на циферблате 2. Записывается: 14mod12 = 2. Аналогично, 21mod12 = 9. 10mod12 = 10 и так далее.
Потом, допустим, хотим сложить числа 8 и 9. Получается 17, что по модулю 12 означает 5. Записываем: (8+9)mod12 = 5.
Потом хотим вычесть 8-9. Получается -1, что означает, что стрелки часов крутим в обратную сторону, от 12, то есть получаем 11. Записываем: (8-9)mod12 = 11.
С умножением - совершенно аналогично. Допустим, 4*10. Получаем 40, крутим три полных оборота и остается еще 4 (вот в этом месте я как раз и поняла, причем тут остаток от деления). Записываем: (4*10)mod12=4.
С возведением в степень ровно так же - получаем сначала нормальный результат, потом считаем остаток от деления на 12, и оно и будет ответом.
А вот с делением чуть интереснее. Скажем, хотим мы 11 разделить на 7. Это значит, что мы должны умножить 11 на число х, обратное к числу 7, то есть такое, для которого было бы верно (7*х)mod12 = 1. Ищем такое число.
(7*2)mod12 = 14mod12 = 2,
(7*3)mod12 = 21mod12 = 9,
(7*4)mod12 = 4,
(7*5)mod12 = 11,
(7*6)mod12 = 6,
(7*7)mod12 = 49mod12 = 1 - ура, мы его нашли! Значит, искомое обратное х - это 7. Значит, нам предстоит умножить 11 на 7. Умножаем, получаем 77, отматываем полных 6 кругов, остается число 5. Итак, (11/7)mod12 = 5.

В завершение можно сказать, что лучше чтобы все же это N, по которому будет модуль, было простым. Тогда не получится некоторых неприятных вещей... Например, с числом 12. В нашем случае мы в принципе не можем разделить на 2. Потому что не существует числа, обратного к 2, то есть такого, для которого бы (2*х)mod12=1.
(2*1)mod12 = 2,
(2*2)mod12 = 4,
(2*3)mod12 = 6,
(2*4)mod12 = 8,
(2*5)mod12 = 10,
(2*6)mod12 = 12 (или 0, что то же самое, тут вот не уяснила, как правильно писать)
(2*7)mod12 = 2...
Это совсем не сложно видеть: так как в 12-ти укладывается целое число двоек, то что бы мы не умножали на 2, у нас всегда будет получаться что-то четное, и никак не 1.
И на 3 тоже разделить нельзя, по той же причине.

Вот так, если где что непонятно, или неверно - корректируйте! :)
Tags: Мегаучебник или Что я читал и похвалил, наука, образование
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 58 comments