Tutorialspoint.dev

Modular Division

Given three positive numbers a, b and m. Compute a/b under modulo m. The task is basically to find a number c such that (b * c) % m = a % m.

Examples:

Input  : a  = 8, b = 4, m = 5
Output : 2

Input  : a  = 8, b = 3, m = 5
Output : 1
Note that (1*3)%5 is same as 8%5

Input  : a  = 11, b = 4, m = 5
Output : 4
Note that (4*4)%5 is same as 11%5

Following articles are prerequisite for this.
Modular multiplicative inverse
Extended Euclidean algorithms

Can we always do modular division?
The answer is “NO”. First of all, like ordinary arithmetic, division by 0 is not defined. For example, 4/0 is not allowed. In modular arithmetic, not only 4/0 is not allowed, but 4/12 under modulo 6 is also not allowed. The reason is, 12 is congruent to 0 when modulus is 6.

When is modular division defined?
Modular division is defined when modular inverse of the divisor exists. The inverse of an integer ‘x’ is a another integer ‘y’ such that (x*y) % m = 1 where m is the modulus.
When does inverse exist? As discussed here, inverse a number ‘a’ exists under modulo ‘m’ if ‘a’ and ‘m’ are co-prime, i.e., GCD of them is 1.



How to find modular division?

The task is to compute a/b under modulo m.
1) First check if inverse of b under modulo m exists or not. 
    a) If inverse doesn't exists (GCD of b and m is not 1), 
          print "Division not defined"
    b) Else return  "(inverse * a) % m" 

C

// C++ program to do modular division
#include<iostream>
using namespace std;
  
// C function for extended Euclidean Algorithm
int gcdExtended(int a, int b, int *x, int *y);
  
// Function to find modulo inverse of b. It returns
// -1 when inverse doesn't
int modInverse(int b, int m)
{
    int x, y; // used in extended GCD algorithm
    int g = gcdExtended(b, m, &x, &y);
  
    // Return -1 if b and m are not co-prime
    if (g != 1)
        return -1;
  
    // m is added to handle negative x
    return (x%m + m) % m;
}
  
// Function to compute a/b under modlo m
void modDivide(int a, int b, int m)
{
    a = a % m;
    int inv = modInverse(b, m);
    if (inv == -1)
       cout << "Division not defined";
    else
       cout << "Result of division is " << (inv * a) % m;
}
  
// C function for extended Euclidean Algorithm (used to
// find modular inverse.
int gcdExtended(int a, int b, int *x, int *y)
{
    // Base Case
    if (a == 0)
    {
        *x = 0, *y = 1;
        return b;
    }
  
    int x1, y1; // To store results of recursive call
    int gcd = gcdExtended(b%a, a, &x1, &y1);
  
    // Update x and y using results of recursive
    // call
    *x = y1 - (b/a) * x1;
    *y = x1;
  
    return gcd;
}
  
// Driver Program
int main()
{
    int  a  = 8, b = 3, m = 5;
    modDivide(a, b, m);
    return 0;
}

PHP

<?php
// PHP program to do modular division
  
// Function to find modulo inverse of b. 
// It returns -1 when inverse doesn't
function modInverse($b, $m)
{
    $x = 0;
    $y = 0; // used in extended GCD algorithm
    $g = gcdExtended($b, $m, $x, $y);
  
    // Return -1 if b and m are not co-prime
    if ($g != 1)
        return -1;
  
    // m is added to handle negative x
    return ($x % $m + $m) % $m;
}
  
// Function to compute a/b under modlo m
function modDivide($a, $b, $m)
{
    $a = $a % $m;
    $inv = modInverse($b, $m);
    if ($inv == -1)
        echo "Division not defined";
    else
        echo "Result of division is "
                      ($inv * $a) % $m;
}
  
// function for extended Euclidean Algorithm 
// (used to find modular inverse.
function gcdExtended($a, $b, &$x, &$y)
{
    // Base Case
    if ($a == 0)
    {
        $x = 0;
        $y = 1;
        return $b;
    }
  
    $x1 = 0;
    $y1 = 0; // To store results of recursive call
    $gcd = gcdExtended($b % $a, $a, $x1, $y1);
  
    // Update x and y using results of 
    // recursive call
    $x = $y1 - (int)($b / $a) * $x1;
    $y = $x1;
  
    return $gcd;
}
  
// Driver Code
$a = 8;
$b = 3;
$m = 5;
modDivide($a, $b, $m);
  
// This code is contributed by mits 
?>


Output:

Result of division is 1

Modular division is different from addition, subtraction and multiplication.
One difference is division doesn’t always exist (as discussed above). Following is another difference.

Below equations are valid
(a * b) % m = ((a % m) * (b % m)) % m
(a + b) % m = ((a % m) + (b % m)) % m

// m is added to handle negative numbers
(a - b + m) % m = ((a % m) - (b % m) + m) % m 

But, 
(a / b) % m may NOT be same as ((a % m)/(b % m)) % m

For example, a = 10, b = 5, m = 5. 
   (a / b) % m is 2, but ((a % m) / (b % m)) % m 
                          is not defined.

References:
http://www.doc.ic.ac.uk/~mrh/330tutor/ch03.html



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter