百科知识网

模运算的概念及性质

发布时间：2025-10-12 | 来源：互联网转载和整理

本文以c++语言为载体，对基本的模运算应用进行了分析和程序设计，以理论和实际相结合的方法向大家介绍模运算的基本应用。给定一个正整数，任意一个整数，一定存在等式；其中、是整数，且，称为除以的商，为除以的余数。对于正整数和整数,，定义如下运算：取模运算：a%p（或amodp），表示a除以p的余数。模p加法：(a+b)%p，其结果是a+b算术和除以p的余数，也就是说，(a+b)=kp+r，则(a+b)%p=r。模p减法：(a-b)%p，其结果是a-b算术差除以p的余数。模p乘法：(a*b)%p，其结果是a*b算术乘法除以p的余数。说明：1.同余式：正整数a，b对p取模，它们的余数相同，记做a≡b%p或者a≡b(modp)。2.n%p得到结果的正负由被除数n决定,与p无关。例如：7%4=3，-7%4=-3，7%-4=3，-7%-4=-3。（1）若p|(a-b)，则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)模运算与基本四则运算有些相似，但是除法例外。其规则如下：(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）