整除和取余

前言

数学是很多其他学科的基础，同样，在程序设计中，数学也扮演着重要的角色。良好的数学基础能够使我们在写程序的时候得心应手，尤其在程序设计竞赛中。这节课我们简单复习复习一些基础的数学概念，帮一些同学回忆回忆。

整除

概念

定义 ：设 a,b∈Z，a≠0，如果存在 q∈Z 使得 b=aq，那么就说 b 可被 a 整除， 记做 a∣b，且称 b 是 a 的 倍数，a 是 b 的 约数（也称为除数、因数）。

性质

关于整除有下面的一些性质

1. 若 a∣b 且 a∣c，则 ∀x,y，有 a∣xb+yc

2. 若 a∣b 且 b∣c，则 a∣c.

3. 设 m≠0，则 a∣b，当且仅当 ma∣mb.

4. 若 a∣b 且 b∣a，则 a=±b.

5. 若 a∣b 且 b≠0，则 ∣a∣≤∣b∣.

带余数除法

概念

设 a,b 是 2 个正整数，且 b≠0，则存在唯一整数 q 和 r，使 a = qb +r，0 ≤ r < ∣b∣。这个式子叫做带余数除法，并记余数 r=a mod b。例如 13 mod 5=3，10 mod 2=0。当 r=0 的时候，就出现了整除，b 是 a 的约数。

如果 n 被 2 除的余数为 0，称 n 为偶数，如果 n 被 2 除的余数为 1，则称 n 为奇数。

性质

关于余数的一些性质

1. (a+b) mod p=(a mod p+b mod p) mod p
2. (a×b) mod p=(a mod p×b mod p) mod p

返回目录，查看更多