初等数论：模m的完全剩余系及其应用

定义2 从模m的每个剩余类中各取一个数，这m个数所组成的集合叫作模m的一个完全剩余系.

下面是几个常用的完全剩余系.

（1)把{0，1，2，…，m-1}叫作模m的最小非负完全剩余系；

（2)把{1，2，…，m-1，m}叫作模m的最小正完全剩余系；

（3)把{-（m-1)，-（m-2)，…，-1，0}叫作模m的最大非正完全剩余系；

（4)把{-m，-（m-1)，-（m-2)，…，-1}叫作模m的最大负完全剩余系；

定理3 m个数a1，a2，…，am构成模m的完全剩余系⇔这m个数中的任意两个对模m两两不同余.

证明 必要性.

若m个数a1，a2，…，am构成模m的完全剩余系，则这m个数一定是模m的不同剩余类中的代表，因此，这m个数中的任意两个对模m两两不同余.

充分性.

这m个数中的任意两个对模m两两不同余.因为模m有且仅有m个不同的剩余类，这m个数必落在m个不同的剩余类中，故m个数a1，a2，…，am构成模m的完全剩余系.

例1 求证：{-11，-4，18，20，32}是模5的一个完全剩余系.

证明 由于-11≡4（mod5)，-4≡1（mod5)，18≡3（mod5)，20≡0（mod5)，32≡2（mod5)，所以，-11，-4，18，20，32这五个数对模5两两不同余，由定理3知，{-11，-4，18，20，32}是模5的一个完全剩余系.

例2 求证：任意整数n的12次方必为13k或13k＋1型数.

证明 设n=13m＋t（t∊Z，|t|≤6)，n12=（13m＋t)12=13M＋t12，则

定理4 设a1，a2，…，am是模m的一个完全剩余系，b是任意一个整数，则a1＋b，a2＋b，…，am＋b也是模m的一个完全剩余系.

证明 设a1＋b，a2＋b，…，am＋b不是模m的一个完全剩余系，则这m个数中至少有某两个来自模m的一个剩余类，即对模m同余.(www.xing528.com)

不妨设a1＋b≡a2＋b（modm)，则由同余可加性可知a1≡a2（modm)，这与已知矛盾.

故a1＋b，a2＋b，…，am＋b也是模m的一个完全剩余系.

定理5 设a1，a2，…，am是模m的一个完全剩余系，（a，m)=1，则aa1，aa2，…，aam也是模m的一个完全剩余系.

证明 设aa1，aa2，…，aam不是模m的一个完全剩余系，则这m个数中至少有某两个来自模m的一个剩余类，即对模m同余，不妨设aa1≡aa2（modm).

因为（a，m)=1，由同余可约性知a1≡a2（modm)，与已知矛盾.

故aa1，aa2，…，aam也是模m的一个完全剩余系.

由定理4和定理5不难得到以下推论.

推论 设a1，a2，…，am是模m的一个完全剩余系，（a，m)=1，b是任一整数，则aa1＋b，aa2＋b，…，aam＋b是模m的一个完全剩余系.

例3 求证：{7，12，17，22，27，32}是模6的一个完全剩余系.

证明 因为{0，1，2，3，4，5}是模6的一个完全剩余系，（5，6)=1，由定理5知{0，5，10，15，20，25}是模6的一个完全剩余系.

由定理4知

是模6的一个完全剩余系.

例4 一个圆形水塘周围有2018个树桩，一只青蛙从某树桩起沿逆时针方向跳跃，每次跳跃到下面的第5个桩上.试说明：当青蛙连跳2018次后，又回到原来的树桩上，而且，其余2017个树桩上都曾停留过一次.

解 从起跳的那个树桩开始，沿逆时针方向，每个树桩标号0至2017，两桩之间叫作一步.因为从0号桩起跳，每跳一次过5步，所以依次跳过的总步数为1×5，2×5，…，2017×5，因为（5，2018)=1，所以，这些总步数是模2018的一个完全剩余系，即这些总步数与2018个树桩标号可以建立一一对应，所以，青蛙出发后，在每个树桩上停留一次.

又因为2018×5≡0（mod2018)，所以，最后一次又跳回到起跳时的那个树桩上.