### shpvb's blog

By shpvb, history, 7 months ago, ,

I looked for it and got a source: Link

But this method may not work when the denominator is a multiple of modulus.

For example, (8/8) % 4 should be 1, but applying this approach it gets gcd(4, 8) = 4 and hence find ((8/4)/(8/4))%(4/4) which results in 0.

Similarly for (80/8) % 4 should be 2 but this results in 0.

So what can be a generalized approach towards this?

• -10

 » 7 months ago, # | ← Rev. 5 →   +3 Modular division only works when the modulo is prime, because it uses Fermat's little theorem: If p is a prime, then: (a^p)%p=a%p, so a^(p-1)%p=1, then (1/a)%p=a^(p-2)%p, but if the modulo is not a prime, then this equation is not always true, therefore (1/a)%m is not equal to a^(m-2)%m. Imagine if we gave an integer value of (1/2) % 4. Let's denote it with x. Then: 1%4=(2*(1/2))%4=(2*x)%4. But x is an integer, and 2*x is always even, therefore it can't be 1. So you can't define these modular divisions.
•  » » 7 months ago, # ^ |   0 Yes, you are right that the result does not always exist. But as stated in the link that if the division is possible and the numerator is divisible by gcd(denominator, modulus) then it is always possible to achieve the answer.Like in (8/8) & 4.
•  » » » 7 months ago, # ^ |   0 Also my main motive is to get sum of a GP modulo m. So I know the sum of gp always comes out to be an integer by the formula of sum, but how to take modulus.Given the division is valid and modulus exists.
•  » » » » 7 months ago, # ^ |   +3 I see what is the problem. I think the link says a wrong solution (or at least I misunderstand it). Here is what you should do: You have to divide both a and b with gcd(a, b), then a and b becomes coprimes. Now if gcd(b, m)!=1, then there is no solution. Otherwise, I don't know how to get the result fast.
•  » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 just multiply with the muliplicative inverse? which can easily be found with the extended euclidean algorithm
•  » » » » » » 7 months ago, # ^ |   0 The problem is the denominator and modulus are co prime so there is no multiplicative inverse.
•  » » » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 as SPatrik mentioned if you want to calculate $a/b \bmod c$ you first calculate $g=gcd(a, b)$, then $a'=a/g$ and $b'=b/g$ if $gcd(b', c) \neq 1$ the result does not exists but if it is $1$ you can just use the multiplicative inverse of $b'$
•  » » » » » » » » 7 months ago, # ^ |   +5 I didn't say that. I said that: "Now if gcd(b, m)!=1, then there is no solution. Otherwise, I don't know how to get the result fast.".
•  » » » » » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 and i said how to get the result fast if $gcd(b, m)= 1$ ?! just use the extended euclidean algorithm
•  » » » » » » » » » 7 months ago, # ^ |   0 You can't use that. You can only use if the modulo is prime. Actually this system is used to determine if a very big number is a prime. Take some random (about 100) numbers, count a^(m-1)%m. If it isn't 1, then m is not a prime. If it was 1 at all test cases, then m is a probable prime. Your algorithm supposes that b^(m-1)%m=1, and this is wrong if m is not a prime (even if b and m are coprimes).
•  » » » » » » » » » 6 months ago, # ^ |   +5 I think there's a misconception here. According to Euler's theorem, if $b$ and $m$ are co-primes, then $b^{\phi(m)} = 1 \mod m$.
•  » » » » » » 7 months ago, # ^ |   0 That's what we are discussing. It is only good if modulo is prime. For example: (1/5)%9 is not 5^7%9 (5^7)%9 is 5, but (5*(1/5))%9=1, (5*5)%9=7
•  » » » » » » » 7 months ago, # ^ |   0 NO! you don't need the modulus to be prime! this is only required if you use fermat! if you use the extended euclidean algorithm instead the modulus can be any number as long as $gcd(b', c)=1$
•  » » » » » 7 months ago, # ^ |   -8 Hey SPatrik can you please explain this approach a bit formally?
•  » » » » » » 7 months ago, # ^ |   0 Which approach? I mentioned a few.
•  » » » » » » » 7 months ago, # ^ |   -8 This one where we divide by gcd(a, b).
•  » » » » » » » » 7 months ago, # ^ |   0 That division makes the problem easier. g=gcd(a, b), then a/b=(a/g)/(b/g), because we divided both with g. It is easier to work with them, because now we can suppose that they are coprimes.
•  » » » » 7 months ago, # ^ |   0 Don't ask solutions to problems from ongoing contests.
•  » » » » » 7 months ago, # ^ |   0 What kind of ongoing contest are you talking about?
•  » » » » » » 7 months ago, # ^ |   0 Hackerearth's June Circuits
•  » » » » » » » 7 months ago, # ^ |   0 Totally unaware buddy, it was just a generic discussion with no propaganda of discussing problems.
 » 7 months ago, # |   +3 Yup. It doesn't make sense to compute for example $x=1/2$ modulo $2$, since there's no integer solution of $2x=1$ modulo $2$. The most we can do is make sure to reduce the fractions so that gcd(numerator, denominator, modulo) is 1, and when gcd(denominator, modulo) is still greater than 1, then just work modulo lcm(denominator, modulo) if it's small enough.