[工学]第一讲--整数与同余理论.docVIP

第一讲 整数与同余理论 本讲介绍有关整数的一些基本概念、性质与定理.主要包括整数的整除性、奇偶性，以及依据整除性而产生的质数与合数、带余除法、最大公约数与最小公倍数. 同时简单介绍同余式的一些最基本的知识及有关重要定理，如欧拉定理、中国剩余定理(CTR). ______________________________________________________________________________ §1. 1 整 自然数和它的相反数，以及零均称为整数. 定义1. 1 设与是任意两整数且，若存在整数使得，则称整除或能被整除.记作；否则，称不能整除或不能被整除，此时记作. 如果，则称是的约数或因数，是的倍数；若是的约数但，则称是的真约数或真因数. 定理1. 1 设是整数, 则有 i) ； ii) 如果且，则； iii) 如果且，则； iv) 如果且，则. 定理1. 2（带余除法定理） 对任意两整数与且b0，则存在唯一的一对整数与，使得 ，其中. 称为被除得到的商，称为被除得到的余数. 我们借助自然数集的最小数原理来证明该定理: 自然数集的最小数原理 若是广义的自然数集的任一非空子集，则存在使得S，有成立，此称为的最小数. 定理1.2的证明 设，则是广义自然数集的非空子集，于是存在的最小数，即存在，使，亦即.下面证明且与是唯一的.（注：广义自然数集可包含零及正无穷大这两个元素.） 若，则且，这与是的最小数矛盾. 若存在两整数与，使得 ，, 则 , 即 . 若，则，这与矛盾，故，于是. ▋ 显然，被整除的充分且必要条件是其余数为. 例1. 1 设,, 则, . 练习1. 1 1. 证明对任意整数有. 2. 如果与中有一能被整除，那末另一数一定也能被17整除. 3. 证明：，其中表示一个四位数. §1. 2 整数的奇偶性 奇偶数的定义：能被整除的整数称为偶数；不能被整除的整数称为奇数. 基本性质： 1）两个整数的和与差具有相同的奇偶性. 2）奇数的平方被除余，被除也余，而偶数的平方能被整除. 3）如果若干个整数的乘积是奇数，则每个因数都是奇数；如果若干个整数之积是 偶数，则至少有一个因数是偶数. 例1. 2 在广场上有（奇数）个学生面向南方排成一行，命令其中（偶数）个学生向后转，称作一次“反向运动”，证明：无论作多少次“反向运动”（转向后的学生允许再转动），都不可能使所有的学生全部面向北方. 证 假设做次“反向运动”后，可使全体学生面向北方，又设各学生“向后转”的次数分别为, 而对每个学生来说，从面向南方变为面向北方，必须经过奇数次“向后转”，即均为奇数，又为奇数，所以是奇数.另一方面，每次“反向运动”均是个学生的“向后转”，所以次“反向运动”所作的“向后转”总次数应为，故有，但该等式左边是奇数，而右边是偶数，矛盾. ▋ 练习1. 2 1. 的方格纸上填着这四个数字，如图所示，问是否可能在余下的方格 内各填入一整数，使得方格纸上的每一行和每一列都构成等差数列 表1. 1 2. 已知多项式的系数均为整数，且是奇数，证明：此多项 式不可能分解成两个整系数多项式之积. 3. 将下图表1.2中任何一行或一列作全部变号操作，问可否经过若干次这样的操作使表1.2变为表1.3？ 表1.2 表1.3 4. 若是奇数，且,求证：. §1. 3 最大公约数与最小公倍数 是个整数.若整数是每个的因数，则称是 的一个公因数. 定义1.3 整数的公因数中的最大者称为它们的最大公因数，记作或. 显然，若中至少有一个非零.比如说，则，因而此时的最大公因数存在. 定义1. 4 如果，则称互素（或互质）；如果时有 ，则称两两互素（或互质）.显然，若后者成立，则前者也成立，反之则不然.如，但. 性质定理1.1 设是个不全为零的整数，则有 i) ，其中是的一个排列； ii) ； iii) 若中有一个为, 则它们互素； iv) 若是中全不为零的整数，则 . 以上性质的证明均显而易见. 定理1. 3 如果,则有. 证 设及，则一方面，，于是由得， 从而 . 另一方面，且，以及得. 从而 . 综合与即得 . ▋ 辗转相除法 设是任意两个正整数，多次利用带余除法，可得下