余数

整数
正整数，负整数，0统称为整数

同余定理
给定一个正整数m，两个整数x,y，如果满足（x-y）除以m等于一个整数，就称：x与y对正整数m同余；记作：x≡y(mod m)
举个例子：

17和5对3同余
(17-5)/3 == 4

同余定理在编程中的应用

• 分页
• 奇数，偶数
• 哈希

哈希
散列函数，把任意长度的输入，通过散列函数，转化成一定长度的输出，该输出就是散列值。
这种转化是压缩转化，也就是散列值的空间远远小于输入所占的空间；不同的输入可能会产生相同的散列值，所以不能根据散列值来说输入是一定的。
简单说：哈希就是将任意长度的消息压缩成某一固定长度消息的函数。