Блог пользователя yahooo

Деление по модулю
Автор yahooo, 13 лет назад, По-русски
Кто-нибудь может объяснить, как делить по модулю (простому) и почему нельзя не по простому? 
  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 5   Проголосовать: нравится +5 Проголосовать: не нравится

По простому модулю можно просто домножить на обратный элемент к данному (xMOD-2 ). Касательно же не простого модуля, то сравнение a*x = b (mod c) вообще говоря может быть не разрешимо. А в случае если разрешимо может иметь не единственное решение (напрмер a*2 = 2 (mod 10). У него очевидно подходят a=1,6).

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    >>>По простому модулю можно просто домножить на обратный элемент к данному

    1) чему равен обратный элемент?

    2) не могли бы вы написать это формулой?

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Про обратный я написал в скобках  (то чему он равен). Это следует в частности из теоремы Эйлера. А именно:

      aφ(m) = 1(mod m), при условии что (a, m) = 1, а φ(m) - функция Эйлера. Откуда обратный равен  aφ(m) - 1.

      → Ответить
      • 13 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        более менее понятно, только, мы же ведь делим на что-то, это число роли не играет?

        P.S. и если вам не составит труда, показать код

        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну вообще говоря мы свели задачу деления к задаче умножения на обратный. Касательно кода я не понимаю что именно вас интересует? Поиск обратного? Если да то это по сути просто возведение того на что надо делить в степень P-2 (где P простой модуль).
          → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

          Деление на число a эквивалентно умножению на a - 1.

          Вот оказывается в поле чисел по простому модулю p для любого числа x из отрезка [1..p - 1] существует элемент y = x - 1, принадлежащий отрезку [1..p - 1]. Тогда если надо поделить на число a, надо просто найти такой элемент b = a - 1 и умножить на b. Также это обобщается на случай не простого модуля, правда и с некоторыми ограничениями.
          О том, как такое число искать, можно почитать здесь

          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится
            спасибо за развернутый ответ, разобрался)
            → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            кст, вроде в отрезке [0..p - 1], а не в [1..p - 1], или я что то путаю
            → Ответить
            • 13 лет назад, # ^ |
              ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

              Для 0 нет обратного. И 0 не является ни чьим обратным, так как (a - 1) - 1 = a

              → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    подходят a = 1, 6
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если a, c взаимно простые, то тогда решение единственное.
    → Ответить