What is the formula for modular division? I know that for addition it is (x+y)/mod and multiplication is (x*y)/mod. But what is it for division? Can you give me a formula?

Is this

x - y*floor(x/y) (for y!=0)

what you were after?

Timkin

Edited by - Timkin on February 19, 2002 11:40:07 PM

if n isn't prime, there is no division in the Z/n Z ring (i.e. integers modulo n )

example : in Z/8Z, both 4*2 = 0 and 0*2 = 0 so what would 0/2 be ?

Having a multiplication doesn't imply the existence of a division. (e.g. matrices)

Edited by - Fruny on February 20, 2002 3:03:25 AM

I understand where the "none" answer would come in.

Perhaps it is (X * 1/y)/mod. That''s based off the multiplication rule. I don''t really know though.

So you''re trying to find x/y (mod n), and as Fruny said in order for this to make sense you need gcd(y,n) = 1. The inverse of y in this case is given by y^phi(n) (mod n) where phi is Euler''s totient function. phi(n) is the number of numbers less than n which are coprime to n. For prime numbers p it is phi(p) = p-1, and for composite numbers n = p*q*...*r it is phi(n) = (p-1)*(q-1)*...*(r-1). (p,q,r are all primes)

Exponentiation modulo n is easy using something like the Russian Peasant Algorithm, and once you''ve done so you get

x/y = x*(y^phi(n)) mod n