取模运算

余数在数学上的定义始终是大于等于零，即按照Euclidean division的定义：

给定两个整数 $a$ 和 $b$, 其中 $b \neq 0$，存在唯一的整数 $q$ 和 $r$使得：

$a = bq + r$ 和

$0 \leq r < |b|$ 成立

取模运算(Modulo operation)类似数学上求余数（reminder)的过程，但丁略有不同，一般满足下面的式子：

$q \in Z$

$a = nq + r$

$|r| < |n|$

对比数学上的定义，由于最后一个约束的不同，会造成两种计算结果：

truncate

截断小数部分，取整数部分，C/C++，JAVA， C#等语言中，”%”是取余运算。

$r = a - n\ \textrm{trunc}(\frac{a}{n})$

比如3/2 = 1 , -3/2 = -1

C 和 JAVA 使用的是 truncate 的方式，所以计算 -6 % 5如下：

-6 - (5trunc(-6/5))= -6 - (5 -1) = -1

floor

向下取整，在正数的时候和truncate一样，但是在负数的时候，向下取整就会出现和truncate不一样的结果。

Python 中 “%” 是取模运算。

$ r = a - n\lfloor \frac{a}{n} \rfloor$

比如：3/2 = 1 -3/2 = -2

python使用的floor除法的方式

-6 - (5floor(-6/5))= -6 - (5 -2) = 4

注：

简单来说，求余的结果应该与a的符号保持一致；而取模的结果应该与b的符号保持一致。

1
2
3

python　　　　a%n的符号与n相同
-11//4          #值为-3
-11%4  ->  (-11) -4*(-11//4) =1     #值为1

1
2
3

C语言　　　　　　a%n的符号与a相同
-11/4         //值为-2
-11%4      (-11) - 4*(-11/4) =-3   //值为-3

辗转相除法

辗转相除法是用来计算两个整数的最大公约数。假设两个整数为a和b，他们的公约数可以表示为gcd(a,b)。如果gcd(a,b) = c,则必然a = mc和b = nc。a除以b得商和余数，余数r可以表示为r = a - bk，k这里是系数。因为c为 a和b的最大公约数，所以c也一定是r的最大公约数，因为r = mc - nck = (m-nk)c。

因此gcd(a,b) = gcd(b,r)，相当于把较大的一个整数用一个较小的余数替换了，这样不断地迭代，直到余数为0，则找到最大公约数。

[1].https://blog.csdn.net/hk2291976/article/details/52775299

[2].https://www.jianshu.com/p/7876eb2dff89