整数与整除

整除关系

先理解什么叫

1
a | b

读作 a 整除 b，意思是存在整数 k，使得

1
b = ak

例如

1
3 | 12

带余除法

任意整数 a，对于正整数 m，则存在唯一的一对整数 q（商）和 r（余数），使得

1
a = qm + r

其中余数满足约束条件

1
0 ≤ r < m

我们通常将这个唯一的余数 r 记作

1
a mod m = r

例如

1
17 mod 5 = 2