Archived

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

Modulos

This topic is 5769 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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