数论基础知识：整除、带余数除法及其性质

ACM算法与程序设计（十二）课程中介绍了数论和基础数学的相关知识。其中，整除和取余是本节课的主要内容。整除的定义是，如果存在一个整数q使得b=aq，那么就说b可以被a整除，并将b称为a的倍数，a称为b的约数。 带余数除法是指对于两个正整数a和b（b≠0），存在唯一的整数q和r，使得a=qb+r，其中0≤r<|b|。余数r可以通过a mod b来计算，例如13 mod 5=3，10 mod 2=0。当余数为0时，即r=0，表示b是a的约数。 根据以上的定义和性质，可以总结出以下关于整除的性质： 1. 若a可以整除b，并且a也可以整除c，则对于任意的整数x和y，a也可以整除xb和yc。 这是因为可以将b表示为b=ax和c表示为c=ay，将这两个等式代入a可以整除b和a可以整除c的定义中，可以得到b=ax是a的倍数，c=ay是a的倍数。而根据整除的定义，a的倍数的乘积仍然是a的倍数，所以对于任意的整数x和y，a也可以整除xb和yc。 2. 若a可以整除b，并且b可以整除c，则a可以整除c。 这是因为可以将b表示为b=ax，将c表示为c=by，然后将b=axy代入c=by中，得到c=a(xy)，即c也是a的倍数。 3. 若m不等于0，则a可以整除b当且仅当ma可以整除mb。 这是因为可以将b表示为b=ax，然后将ma代入ma=mb中，得到ma=axm，即ma也是a的倍数，所以a可以整除b当且仅当ma可以整除mb。 4. 若a可以整除b，并且b可以整除a，则a等于±b。 这是因为a可以整除b表示为b=ax，b可以整除a表示为a=by，将b=ax代入a=by中，得到ax=by，即a和b成比例。因为a和b都是整数，所以a和b相差一个整数倍，即a=±b。 除了整除和取余，本节课还介绍了一些矩阵的应用，例如矩阵二分快速幂用来求解递推问题。这些内容都是数论和基础数学中的重要知识点，对于算法的设计和程序的编写有很大的帮助。通过学习这些知识，可以提高对整数运算的理解和应用能力。