CODEWITHSUNDEEP
algorithmmathmodulo
devsda
devsda

Reputation: 4222

Modulo operator and divide operator

Two numbers A and B given to us.

It is given that A is exactly divisible by B.

I need to calculate (A/B)%MOD.

We only know two things A%MOD, B. How can we calculate this from above two things.

REAL PROBLEM

num = (1*2*3.....*262143)%MOD, is known to us.

Now, my task is to calculate (2*3*4*...*262144)%MOD, then (3*4*5*....*262145)%MOD, so on.

where, MOD = 1000000009.

UPDATED :-

A = (2*3*4)%7 = ( 2%7 * 3%7 * 4%7)%7 = 3
B = ( (A*(5%7))%7 )/(2%7) = 0 .......................**THAT IS WRONG, ANSWER SHOULD BE 4**

Upvotes: 1

Views: 349

Answers (2)

IVlad
IVlad

Reputation: 43477

Since 1000000009 is prime, the problem is easy. You need to use modular multiplicative inverses.

(A / B) % MOD = ((A % MOD) * (B^-1 % MOD)) % MOD

You can use Fermat's little theorem for this, which says that, if p is prime, then 

a^(p - 1) % p = 1,

which leads to 

(a * a^(p - 2)) % p = 1,

meaning 

a^(p - 2)

is the modular inverse of a mod p.

A = (2 * 3 * 4 * ... * 262144) % MOD
B = (3 * 4 * 5 * ... * 262145) % MOD
  = (A * (2^1000000007 % MOD) * (262145 % MOD)) % MOD

Upvotes: 3

SomeWittyUsername
SomeWittyUsername

Reputation: 18358

(x * y) % mod = (x % mod) * (y % mod)

Given this identity, you can easily find the answer:

A = (1*2*3.....*262143)%MOD= (1 % MOD * 2 % MOD *3.....*262143 % MOD)

B = (2*3.....*262144)%MOD= (2 % MOD *3.....*262144 % MOD)

B = A * (262144 % MOD) = (A * 262144) % MOD.

Upvotes: -1

Related Questions