Archived

This topic is now archived and is closed to further replies.

Andrew Nguyen

Modulos

Recommended Posts

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?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites