# 算法设计：模划分详细实现

2021年5月3日17:07:29 发表评论 763 次浏览

## 本文概述

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

, 如果" a"和" m"是互质的, 则它们的模数" m"下的数字为" a"的倒数, 即它们的GCD为1。

``````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;
}``````

## Python 3

``````# Python3 program to do modular division
import math

# Function to find modulo inverse of b. It returns
# -1 when inverse doesn't
# modInverse works for prime m
def modInverse(b, m):
g = math.gcd(b, m)
if (g ! = 1 ):
# print("Inverse doesn't exist")
return - 1
else :
# If b and m are relatively prime, # then modulo inverse is b^(m-2) mode m
return pow (b, m - 2 , m)

# Function to compute a/b under modulo m
def modDivide(a, b, m):
a = a % m
inv = modInverse(b, m)
if (inv = = - 1 ):
print ( "Division not defined" )
else :
print ( "Result of Division is " , (inv * a) % m)

# Driver Program
a = 8
b = 3
m = 5
modDivide(a, b, m)

# This code is Contributed by HarendraSingh22``````

## 的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
?>``````

``Result of division is 1``

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

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