When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

shpvb's blog

By shpvb, history, 5 years ago, In English

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?

  • Vote: I like it
  • -10
  • Vote: I do not like it

»
5 years ago, # |
Rev. 5   Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          just multiply with the muliplicative inverse? which can easily be found with the extended euclidean algorithm

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            The problem is the denominator and modulus are co prime so there is no multiplicative inverse.

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              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'$$$

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it +5 Vote: I do not like it

                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.".

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  and i said how to get the result fast if $$$gcd(b, m)= 1$$$ ?! just use the extended euclidean algorithm

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it +5 Vote: I do not like it

                  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$$$.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          Hey SPatrik can you please explain this approach a bit formally?

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Which approach? I mentioned a few.

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it -8 Vote: I do not like it

              This one where we divide by gcd(a, b).

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Don't ask solutions to problems from ongoing contests.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          What kind of ongoing contest are you talking about?

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Hackerearth's June Circuits

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Totally unaware buddy, it was just a generic discussion with no propaganda of discussing problems.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.