eddycael's blog

By eddycael, 10 years ago, In English

Hi, I learned about modular multiplicative inverse with modulo M (M is a prime number) using: (a^(M-2) ) MOD M

Now I would like to learn how calculate modular multiplicative inverse with modulo no prime.

Could someone give me one or two examples how to calculate it? For example COMB(8,3) = 8! /(3! * (8-3)!) = 56 , then COMB(8,3) MOD 6 = 2.

Thanks in advance. (Sorry for my poor english)

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use DP to calculate C(n , r) ( C(n , r) = (C(n — 1 , r — 1) + C(n — 1 , r))% MOD ) in O(n * r) instead of using factorial.

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

    You are right... I didn't think about it... Thanks

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

CF community knows about this task. It's better to ask for help in two days.

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In fact, in this problem, you want to solve this question:

"Find t, that (x*t) mod M = y"

However when M is not prime, t may be not unique. In your example, M=6, y=8*7*6=0 (mod M), x=3*2*1=0 (mod M), certainly we have no way to find which number t is.

That means, multiply in mod-non-prime group can lead to losing of information and the lost information can not be recovery. If you change M in a problem to a non-prime, the problem may become not solvable.

»
10 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Have you try Euler Theorem ?