Jump to content
• Advertisement

#### Archived

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

# Modulos

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

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

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

##### Share on other sites
I understand where the "none" answer would come in.

#### Share this 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

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

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5
frob
13
• Advertisement

• 9
• 15
• 10
• 9
• 17
• ### Forum Statistics

• Total Topics
632602
• Total Posts
3007363

×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!