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

Question about number theory
Автор Vicennial, история, 8 лет назад, По-английски

How would I check the divisibility of two numbers which are both taken under modulo M?
E.g I have calculated a very large sum modulo M and now I want to check if this sum is evenly divisible by a^b where a and b can be as large as 10^9.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

The only way I can spot is to calculate the sum modulo M * a ^ b (hope is not too big), and then check if the result is divisible by a ^ b.

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

You can't take them modulo and then check for divisibility, for ex. the numbers 8 and 3 are equal modulo 5, but 3 doesn't divide 8. On the other hand, 128 and 8 give remainders 3 modulo 5, and 8 divides 128. As per this example, you have no way to check whether two numbers(taken modulo) divide each other(examples can be found for every number)

→ Ответить