• Advertisement

Archived

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

Modulos

This topic is 5842 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

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
Advertisement
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

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
Perhaps it is (X * 1/y)/mod. That''s based off the multiplication rule. I don''t really know though.

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

  • Advertisement