C语言求余运算的剩余系原理

戴力澄，吴巨龙

(1. 山东大学信息科学与工程学院,山东 济南 250100；2. 华中师范大学第一附属中学,湖北 武汉 430223)



C语言求余运算的剩余系原理

戴力澄1，吴巨龙2

(1. 山东大学信息科学与工程学院,山东 济南 250100；2. 华中师范大学第一附属中学,湖北 武汉 430223)

摘要：C语言求余运算的结果有正有负，与余数概念有很大区别.对初等数论中的余数和同余概念进行推广，使得任意非零整数都有一个最小非负完全剩余系，一个最小非正完全剩余系.并且证明C语言求余运算本质上是不同剩余系下的带余数除法运算.

关键词：求余运算；剩余系；带余数除法

0引言

求余运算(运算符%)是C语言[1]、Python语言[2]、Matlab语言[3]等多种计算机程序设计语言支持的一种基本运算.若a，b是两个整数，则a%b计算a除以b所得的余数.运算法则规定，求余运算的结果与a同符号，结果的绝对值为a的绝对值除以b的绝对值所得的余数.这样，求余的结果有正有负，例如，8%5=3,8%(-5)=3,(-8)%5=-3,(-8)%(-5)=-3.这个结果与我们的思维习惯是有出入的，在初等数论教科书[4]或者软件开发实践过程中[5]一般都要求整数除法的余数是非负数,因为-8=(-2)*5+2，一般我们认为余数是2. 剩余类是初等数论中的一个基本概念，在代数学领域，整数n的剩余类Zn具有环的代数结构[6]和群的代数结构[7]，剩余类环在编码等方面也有广泛应用，比如设计不规则重复累计码和低密度奇偶校验码等[8].事实上程序设计语言中的求余运算法则设计原理也是剩余系概念.下面从剩余系的概念和C语言设计角度来研究上述问题.

1剩余系

求余离不开整数除法，整数除法有一个基本定理，称为带余数除法定理，转述如下：

引理1[4](带余数除法)若a,b是两个整数，其中b>0，则存在两个整数q及r，使得a=bq+r,0≤r

引理要求b>0，引理说明，除数为正时，存在小于除数的非负余数.对于b<0也有类似结果.

定理1若a，b是两个整数，其中b<0，则存在两个整数q及r，使得

a=bq+r,0≤r<|b|

(1)

成立，且q及r是唯一的.

定理1的证明作整数序列…,3b,2b,b,0,-b,-2b,-3b,…,则存在一个整数q使得qb≤a<(q-1)b成立.

令r=a-qb，则a=qb+r,显然r≥0，又因为r+b=a-qb+b=a-(q-1)b<0,所以r<-b=|b|.

下面证明q及r的唯一性.

设q1和r1是满足(1)式的两个整数，则a=bq1+r1，

所以bq+r=bq1+r1，则b(q-q1)=r1-r，|b||q-q1|=|r1-r|，

由于

|r1-r|<|b|,

所以q=q1,r=r1.证毕.

同样地，我们称r为a除以b得到的余数.

定理1说明，除数为负数时，存在小于除数绝对值的非负余数.

定理2若a，b是两个整数，其中b<0，则存在两个整数q及r，使得a=bq+r,b

定理2的证明作整数序列…,3b,2b,b,0,-b,-2b,-3b,…

则存在一个整数q使得(q+1)b

令r=a-qb，则

a=qb+r,

显然

r≤0，

又

r-b=a-qb-b=a-(q+1)b>0，

所以

b

q及r的唯一性证明同定理1.证毕.

我们仍称r为a除以b得到的余数.定理2说明，除数为负数时，存在大于除数的非正余数.

定理3若a，b是两个整数，其中b>0，则存在两个整数q及r，使得a=bq+r,-b

定理3的证明作整数序列

…,-3b,-2b,-b,0,b,2b,3b,…

则存在一个整数q使得(q-1)b

令r=a-qb，则

r≤0.

又因为

r+b=a-qb+b=a-(q-1)b>0,

则r>-b，所以

-b

q及r的唯一性证明同定理1.证毕.

我们称r为a除以b得到的余数.定理3说明，除数为正数时，存在大于除数相反数的非正余数.

综合引理1和定理1.3可知，做整数除法时，不论除数是正数还是负数，都存在非负余数或非正余数.

现有数论教材对模为正整数时给出了同余的概念，余数的概念可以推广到非正余数，也可以将模推广到负整数，从而任意非零整数都有同余概念.

定义1 给定一个非零整数m，如果m能整除任意两个整数a和b的差，称a和b对模m同余，记作a≡b(modm). 否则称a和b对模m不同余.

定理4若m是一个给定的非零整数，令Ki={qm+i|q∈Z}，i=0,1,…,|m|-1，或i=0,-1,…,-|m|+1，则1) 每一整数必包含在而且仅在上述的一个集合里；2) 两个整数在同一个集合的充要条件是这两个整数对模m同余.

定理4的证明1) 若i=0,1,…,|m|-1，结论可由引理1和定理1得证；

若i=0,-1,…-|m|+1，结论可由定理2和定理3得证.

2) 仅对i=0,-1,…,-|m|+1情况给出证明，其他情况证明方法类似.

若a，b是两个整数，且都在Ki内，则

a=mq1+i，b=mq2+i，

故a-b=m(q1-q2)能被m整除，a和b对模m同余.

反之，若a和b对模m同余，即m能整除(a-b)，不妨设a=mq1+i，b=mq2+j，其中

i,j∈{0,-1,-2,…,-|m|+1}，

则

a-b=m(q1-q2)+(i-j),

从而m能整除(i-j)，所以i=j，即a和b在同一个某集合Ki内.证毕.

定义2定理4中的K0,K1,…,K|m|-1，或者K0,K-1,…,K-|m|+1叫做模m的剩余类.称{0,1,2,…,|m|-1}为m的最小非负完全剩余系，{0,-1,…,-|m|+1}为m的最小非正完全剩余系.

本质上，模m剩余类惟一，不难证明，集合{K0,K-1,…,K-|m|+1}={K0,K1,…,K|m|-1}.

2求余运算与除法运算

一般情况下，我们会用已知的简单的运算来定义新的或复杂的运算.比如用加法定义乘法，C语言就是用除法来定义求余运算的，即对a，b两个整数,

按规定，a/b取整数，其符号为正(a,b同号)，为负(a,b异号)，其绝对值为a的绝对值除以b的绝对值所得的商，例如：8/5=1,8/(-5)=-1,(-8)/5=-1,(-8)/(-5)=1.

定义3设a，b为两个整数，b不为0，则a/b=q，其中(q-1)b0).

定义3说明，整数除法是一个不断试商的过程，逐步寻找整数m直到区间[mb,(m+1)b,(a>0)]或者[(m-1)b,mb],(a<0)包含a,此时选择绝对值最小的端点对应的倍数作为a/b的值.比如：1*5≤8<2*5,故8/5=1；2*(-5)<-8≤1*(-5)，故(-8)/(-5).

定理5的证明下面针对两个非零整数a，b的符号组合分别计算a/b，a%b，结果如表1所示.

表1　整数a，b的不同符号组合下a/b，a%b的计算结果

由表1可知，a%b与a同号，结论得证.

将整数除法中的余数和同余中的模概念推广到负数，任意非零整数都有一个最小非负完全剩余系，一个最小非正完全剩余系.根据C语言求余运算定义和剩余系原理科学解释了C语言求余运算法则，C语言求余运算是多种剩余系下的带余除法运算.

3参考文献

[1] 秦友淑,曹化工.C语言程序设计教程[M].2版.武汉:华中科技大学出版社,2002:33-34.

[2] 马辉.Python语言中模运算的特点与应用[J].安阳师范学院学报,2013(2):43-45.

[3] 张德丰.MATLAB实用数值分析[M].北京：清华大学出版社，2012.

[4] 闵嗣鹤,严士健.初等数论[M].3版.北京:高等教育出版社,2003:2-58.

[5] 白鸿武.C语言中整数除法取商和取余运算的实现[J].咸阳师范学院学报,2010,25(2):4-6.

[6] 居腾霞,王立周.模n的剩余类环的单位群U(Zn)[J].南通大学学报：自然科学版, 2011,10(4):83-86.

[7] 张影,曹炜. 单位群阶为2pqr的模n剩余类环[J].宁波大学学报：理工版,2014,27(3):59-62.

[8] 彭立.张琦. 针对IRA-LDPC码类的半随机半代数结构设计[J].通信学报,2014,35(3):77-84.

(责任编辑赵燕)

The complete system of residues theory for the remainder operator of C language

DAI Licheng1, WU Julong2

(1.School of Information Science and Engineering,Shandong University,Jinan 250100,China;

(2. No.1 Middle School Attached to CCNU, Wuhan 430223，China)

Abstract:C language modulo operation has both positive and negative results, which is very different from the concept of remainder. The concept of remainder and congruence in elementary number theory is extended in this paper, so any nonzero integer has a minimum non-negative complete system of residues and a minimum non-positive complete system of residues. Finally a conclusion is proved that C language modulo operation is a division computation with remainder under different systems in essence.

Key words:remainder operator; complete system of residues; division with remainder

中图分类号:O156.1，TP301.2

文献标志码:A

DOI:10.3969/j.issn.1000-2375.2016.02.014

文章编号:1000-2375(2016)01-0168-04

作者简介:戴力澄(1998-)，女，本科生，E-mail：1020173839@qq.com

收稿日期:2015-08-19