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?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 134 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
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.
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.
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.
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.
just multiply with the muliplicative inverse? which can easily be found with the extended euclidean algorithm
The problem is the denominator and modulus are co prime so there is no multiplicative inverse.
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'$$$
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.".
and i said how to get the result fast if $$$gcd(b, m)= 1$$$ ?! just use the extended euclidean algorithm
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).
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$$$.
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
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$$$
Hey SPatrik can you please explain this approach a bit formally?
Which approach? I mentioned a few.
This one where we divide by gcd(a, b).
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.
Don't ask solutions to problems from ongoing contests.
What kind of ongoing contest are you talking about?
Hackerearth's June Circuits
Totally unaware buddy, it was just a generic discussion with no propaganda of discussing problems.
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.