Vicennial's blog

Question about number theory
By Vicennial, history, 8 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why not calculate the sum just modulo a^b and check if it's zero?

    → Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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)

→ Reply