模运算

2021年2月6日发(作者：转炉)

模运算

“

模

”

是

“Mod”

的音译 ，模运算多应用于程序编写中。

Mod

的含义为求余。模运算 在

数论

和程序设计中都有着

广泛的应用 ，从奇偶数的判别到素数的判别，从模

幂运算

到

最大公约数

的求法，从孙子问题到

凯撒密码

< p>
问

题，无不充斥着模运算的身影。虽然很多数论教材上对模运算都有一定的 介绍，但多数都是以纯理论为主，

对于模运算在程序设计中的应用涉及不多。

< p>

?

?

?

?

?

中文名

模运算

外文名

Mod

概述

计算机编写程序

领域

数论和程序设计

类型

以纯理论为主

举例

11 Mod 2

，值为

1

上述模运算多用于程序编写，举一例来说明模运算的原理：

Turbo Pascal

对

mod< /p>

的解释是这样的：

[1]

A Mod B=A-(A

div

B) * B

（

div

含义为整除）

概念及性质

本文以

< br>c++

语言为载体，对基本的模运算应用进行了分析和程序设计，以理论和实际相 结合的方法向大家

介绍模运算的基本应用。

基本概念

给定一个

正整数

，任意一个整数

，一定存在等式

；其中

、

是整数，且

，称

为

除以

的商，

为

除以

的

余数

。

对于

正整数

和整数

,

，定义如下运算：

取模运算

：

a % p

（或

a mod p

），表示

a

除以

p

的

余数

。

模

< p>
p

加法

：

(a + b) % p

，其结果是

a+b

算术和除以

p

的余数，也就是说，

(a+b) = kp +r

，则

(a + b) % p = r

。

模

p< /p>

减法：

(a-b) % p

，其结果是

a-b

算术差除以

p

< br>的余数。

模

p

乘法

：

(a * b) % p

，其结果是

a * b

算术乘法除 以

p

的余数。

说明：

1.

同余式

：正整数

a

，

< br>b

对

p

取模，它们的余数相同， 记做

a ≡ b % p

或者

a ≡ b (mod p)

。

2. n % p

< p>
得到结果的正负由

被除数

n

决定

,

与

p

无关。例如：

7%4 = 3

，

-7%4 = -3

，

7%-4 = 3

，

-7%-4 = -

3(

在

java

、

C/C ++

中

%

是取余，在

< br>python

是模运算，此处

%

按取余处理

)

。

基本性质

（

1

）若

p|(a-b)

，则

< p>
a≡b (% p)

。例如

11 ≡ 4 (% 7)

，

18 ≡ 4(% 7)

（

2

）

(a % p)=(b % p)

意味

a≡b (% p)

（

3

）

对称性

：

a≡b (% p)

等价于

b≡a (% p)

（

4

）传递性：若

a≡b (% p)

且

b≡c (% p)

，则

a≡c (% p)

1

运算规则

模运算与基本四则运算有些相似，但是除法例外。其规则如下：

(a + b) % p = (a % p + b % p) % p

（

1

）

(a - b) % p = (a % p - b % p) % p

（

2

）

(a * b) % p = (a % p * b % p) % p

（

3

）

(a^b) % p = ((a % p)^b) % p

（

4

）

结合律：

((a+b) % p + c) % p = (a + (b+c) % p) % p

（

5

）

((a*b) % p * c)% p = (a * b*c) % p

（

6

）

// (a%p*b)%p=(a*b)%p

交换律：

(a + b) % p = (b+a) % p

（

7

）

(a * b) % p = (b * a) % p

（

8

）

分配律：

((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p

（

9

）

重要定理：

若

a≡b (% p)

，则对于任意的

c

，都有

(a + c) ≡ (b + c) (%p)

；（

10

）

若

a≡b (% p)

，则对于任意的

c

，都有

(a * c) ≡ (b * c) (%p)

；（

11

）

若

a≡b (% p)

，

c≡d (% p)

，则

(a + c) ≡ (b + d) (%p)

，

(a -

c) ≡ (b

- d) (%p)

，

(a * c) ≡ (b * d) (%p)

，

(a / c) ≡ (b / d) (%p)

；

（

12

）

基本应用

判别奇偶数

奇

偶数

的判别是模运算最基本的应用，也非常简单。易知一个整数

n

对

2

取模，如果

< br>余数

为

0

，则表示

n

为偶数，否则

n

为奇数。

C++

实现功能函数：

/*

函数名：

IsEven

函数功能：判别整数

n

的奇偶性。能被

2

整除为偶数，否则为奇数

输入值：

int n

，整数

n

返回值：

bool

，若整数

n

是偶数， 返回

true

，否则返回

false

*/

bool IsEven(int n)

{

return !(n%2);

}

判别素数

一个数，如果只有

1

和它本身两个因数，这样的数叫做

质数

（或素数）。例如

2

< br>，

3

，

5

，

7

是质数，而

4

，

6

，

8

< br>，

9

则不是，后者称为合成数或

合数

。

判断某个自然数是否是素数 最常用的方法就是

试除法

：用比该自然数的平方根小的

正整数

去除这个自然数，

若该自然数能被整除， 则说明其非素数。

C++

实现功能函数：

/*

函数名：

IsPrime

函数功能：判别自然数

n

是否为素数。

2