初等数论 李同贤

初等数论，高等院校小学教育专业教材，复旦大学出版社。深入浅出地解析了数论的基础概念、定理证明、同余理论及在密码学等领域的应用。

初等数论

• 整数的整除性
  • 进制计数法
    • 十进制
    • 一般进位制
  • 四则运算及其封闭性
    • 自然数的四则运算及其性质
    • 整数四则运算的定义
    • 带余除法
  • 整除及其性质
    • 整数的整除性
      • 定义
        • 略（0不是因数）
      • 性质
        • 1⃣（传递性）若c|b，b|a，则c|a
        • 2⃣（可加性）若c|a，c|b，c|(a+b)
        • 3⃣（可乘性）若b|a，d|c，则bd|ac
        • 4⃣若b|a↔️|b| | |a|
      • 1.能被11整除：奇数位之和与偶数位之和，的差能被11整除 2.能被9整除：舍倍判断，舍数位上的3.6.9剩余之和能否被9整除 3.能被7整除：末三位数与末三位之前的数字组成的数之差，能被7整除
    • 整数的奇偶性
      • 定义
      • 性质
        • 1.偶数之和之差为偶数；奇数之和之差也为偶数；奇数与偶数之和之差为奇数
        • 2.奇数×奇数＝奇数；偶数×偶数＝偶数
          • 若干奇数之积为奇数；若干整数相乘，其中有一个偶数，则积为偶数
        • 3.a为整数，n为正整数，则a的n次方与a的奇偶性相同
  • 分解质因数
    • 质数与合数
    • 质数的判定
      • 方法
        • 筛法；整除的特征；用小于根号a的所有质数试除；因式分解
      • 定理
        • 定理1⃣ 设a＞1的正整数，若p是a大于1的最小正因数，则p必为质数
        • 定理2⃣ （判定定理）设a是大于1的正整数，若所有不超过根号a的质数都不能整除a，则a是质数
        • 定理3⃣ 质数有无限个
    • 分解质因数
      • 定义
        • 标准分解式
      • 定理
        • 4⃣（算术基本定理）任一大于1的正整数均可分解质因数；不计较顺序，则分解结果唯一
        • 5⃣在n！的标准分解式中，质因数p的质数为，，，，，
  • 最大公因数
    • 概念
    • 性质
      • 定理
        • 1⃣若a＝bq+r（0≤r≤b），则（a,b）＝（b,r）
        • 2⃣若d＞0，d|a，d|b，则（a,b）＝d↔️存在整数s，t，使得d＝as+bt（贝祖等式）
        • 3⃣设q是a,b的任意一个公因数，d是a,b的一个公因数，则d＝（a,b）
          • 推论：（a，b）＝1↔️存在整数s，t，使得as+bt＝1
        • 4⃣设d|a，d|b，则d＝（a，b）↔️（a/d,b/d）＝1
        • 5⃣(ac,ba)＝c（a,b），常应用于短除法
        • 6⃣若a|bc，且（a，b）＝1，则a|c
          • 推论：设p为质数，若p|ab，则p|a或p|b
        • 7⃣若a|c，b|c，（a，b）＝1，则ab|c
        • 8⃣若（a，b）＝1，则(a，bc)＝(a，c)
          • 推论：a|m，b|m，c|m，且a，b，c两两互质，则abc|m
          • 若（a，b）＝1，则(a的n次方，bn次方)＝1
          • (a的n次方，b的n次方)＝(a，b)n次方，n是正整数
          • 如果一组数a中任意一个与一组数b中任意一个互质，则这两组数的积的互质
    • 求法
      • 分解质因数
        • 写出各数的标准分解式；找共同质因数及其最小次数方，再写成连乘的形式
      • 提取公因数法（短除法）
        • 用定理5⃣逐步提取
      • 辗转相除法
        • 更相减损术
      • 欧拉算法
  • 最小公倍数
    • 概念
    • 性质
      • 定理
        • 1⃣是一组数的一个公倍数，q是其中一个数的公倍数，则m＝这组数的最小公倍数↔️m|q
        • 2⃣设 一组数a|m(p＝1，2，....，n)，则m＝【这组数】↔️（m/a1，m/a2，m/an）＝1
        • 3⃣
    • 求法
      • 分解质因数
        • 写出各数的标准分解式；找出所有质因数及其最高次数，并把到的幂连乘起来
      • 提取公因数
        • 短除法，最外面一圈连乘起来
      • 先求最大公因数法
        • ab的最小公倍数：求得最大公因数，然后ab÷最大公因数
  • 整值函数的整除性
    • 按除数除函数自变量所得余数分类
      • 差为2的一对质数叫做孪生质数。除3和5以外，其他的每队孪生质数之和都能被12整除
      • a.b为整数，且a.b都不能被2和3整除，则24|（a的2次方-b的2次方）
    • 利用因式分解公式
      • 若a，b为整数，n为正整数，则（a-b）|（a的n次-b的n次）
        • 若n为正偶数，（a+b）|（a的n次-b的n次）
        • 若n为正奇数，（a+b）|（a的n次+b的n次）
    • 利用组合数公式的推广结论
      • r!＝n(n-1)(n-2)•••(n-r+1)
    • 利用数学归纳法
      • 当n＝0时，•••••； 设当n＝k时，结论成立，即•••••。当n＝k+1 时，f(k+1)＝••••• 由归纳假设（题目）可知，题目|f（k+1） 由步骤（1）（2）可知题目
    • 利用递推公式
      • 把整值函数式转化成递推公式，通过地推来判定一个整值函数能否被一个整数整除
    • 利用费马小定理
      • p为质数，n为整数，若（p，n）＝1，则p|（n的p-1次—1）
      • p为质数，(p，n)＝1，(p，m)＝1，则p|(n的p-1次——m的p-1次)
      • p为质数，n为正整数，则p|(n的p次—n)
  • 正整数的正因数个数与总和
    • 正整数正因数的个数
      • 定理
        • 若正整数的标准分解式为n＝p1的α1次×p2的α2次•••pm的αm次，则d(n)＝（α1+1）（α2+1）•••（αm+1）
        • 正整数n为完全平方数↔️d（n）为奇数
        • 正整数n的所有不同正因数之积＝n的d(n)/2次方
    • 正整数正因数的和
      • 对n分解质因数，得Sn
    • 完全数、梅森数、亲和数
      • 完全数
        • 正因数之和＝所有小于n的正因数之和➡️完全数➡️S(n)＝2n
        • 2的p-1次方（2的p次方-1）为完全数
      • 梅森数
        • 形如2的p次方-1，的数（p为质数）
      • 亲和数
        • S(n)＝S(m)＝n+m
    • (n,m)＝1➡️d(m,n)＝d(n)d(m)；S(nm)＝S(n)S(m)
• 同余和同余方程
  • 同余的概念及性质
    • 概念
    • 性质
      • 基本性质
      • 可加性
      • 可乘性
      • 可约性
        • • 1.若ac=bc(mod m)，(c,m)=1，则a三b(mod m) 2.若ac三bc(mod cm)，则A三b(Mdm) 3.若 a三b(modcm)，则a三b(mod m) 4.若ac三bc(mod m)，（c，m)=d,则a三b（mod m/d)
    • 被特殊数整除的数的特征
      • 被2或5
        • 末尾数字能被2或5整除
      • 被4或25整除
        • 末两位数字能被4或25整除
      • 能被3或9整除
        • 各位数字之和能被3或9整除
      • 能被11整除
        • 末三位数字与去掉末三位所得数之差，能否被11整除
  • 剩余类和剩余系
    • 剩余类
      • 剩余类/同余类：对模m同余的数的集合，用【r】m表示（模为m，r为余数）
      • 模m的一个剩余类中的一切数，与模m的最大公因数相等
    • 完全剩余系
      • 定义：从模m中的每个剩余类中各取一个数，这m个数组成的集合叫做模m的一个完全剩余系
      • 绝对最小完全剩余系：m为奇数，｛-（m-1)/2,…-1,0,1,…,(m-1)/2｝➡️全是奇数〰〰当m为偶数时，其集合中全是偶数
    • 欧拉函数和简化剩余系
      • 欧拉函数
        • 不超过正整数m又与m互质的正整数的个数记作➰m
      • 简化剩余系
        • 与模m互质的剩余类➰m个，从每类中各取一个数构成的集合
        • 模m的最小正简化剩余系：在模m的最小非负完全剩余系中取得的简化剩余系
  • 费马小定理和欧拉定理
  • 分数与小数的互化
    • 既约真分数与有限纯小数的互化
    • 既约真分数与纯循环小数的互化
    • 既约真分数与或循环小数的互化
  • 一元一次同余方程
    • 求法
      • 1⃣判断：(a,m)=d,d|b➡️有解，有d个解
      • 2⃣求法：
        • 1.欧拉算法
          • 适用于数字小，关系明显者
        • 2.欧拉定理
          • 写解比较容易，化简比较麻烦
        • 3.同解变形法
          • 加模的整数倍，再约系数得解
  • 一元一次同余方程组
    • 模两两互质的同余方程组的解
      • 中国剩余定理：有且仅有一个解（定理）
      • x与b1M1M2'......bnMnMn'关于M同余
    • 模不两两互质的同余方程组有解的判定和求法
      • 判断有无解：(m1,m2)|（b1-b2）
      • 求解方法
        • 代入法
        • 欧拉算法
        • 中国剩余定理
          • 模含有不同质因数时，将模化为标准分解式，即将方程组化为模两两互质的方程组求解
• 不定方程
  • 二元一次不定方程
    • 定理
      • ax+by＝c，（a，b）|c➡️有整数解
    • 求法
      • 1⃣判断有无解，多少个解。能化简的就化简
      • 2⃣求特解
        • 方法1.观察法
        • 方法2.欧拉算法
        • 方法3.辗转相除法
        • 法4.解同余方程法
      • 3⃣写通解
  • 多元一次不定方程
    • 三元一次不定方程
      • 判定：ax+by+cz=d，(a，b，c)|d➡️有解
      • 方法
        • 并项减元法
        • 辗转相除法
    • n元一次不定方程
      • 判定：不定方程中，(a1,a2....an)|d➡️有解
      • 方法
        • 并项减元法
        • 辗转相除法
  • 多元一次不定方程组
    • 求解思路
      • 通过消元减少未知数的个数，转化为一次方程，再把一次方程的通解逐步代回得到原方程的解
  • 特殊非线性不定方程组

初等数论

• 整数的整除性
  • 进制计数法
    • 十进制
    • 一般进位制
  • 四则运算及其封闭性
    • 自然数的四则运算及其性质
    • 整数四则运算的定义
    • 带余除法
  • 整除及其性质
    • 整数的整除性
      • 定义
        • 略（0不是因数）
      • 性质
        • 1⃣（传递性）若c|b，b|a，则c|a
        • 2⃣（可加性）若c|a，c|b，c|(a+b)
        • 3⃣（可乘性）若b|a，d|c，则bd|ac
        • 4⃣若b|a↔️|b| | |a|
      • 1.能被11整除：奇数位之和与偶数位之和，的差能被11整除 2.能被9整除：舍倍判断，舍数位上的3.6.9剩余之和能否被9整除 3.能被7整除：末三位数与末三位之前的数字组成的数之差，能被7整除
    • 整数的奇偶性
      • 定义
      • 性质
        • 1.偶数之和之差为偶数；奇数之和之差也为偶数；奇数与偶数之和之差为奇数
        • 2.奇数×奇数＝奇数；偶数×偶数＝偶数
          • 若干奇数之积为奇数；若干整数相乘，其中有一个偶数，则积为偶数
        • 3.a为整数，n为正整数，则a的n次方与a的奇偶性相同
  • 分解质因数
    • 质数与合数
    • 质数的判定
      • 方法
        • 筛法；整除的特征；用小于根号a的所有质数试除；因式分解
      • 定理
        • 定理1⃣ 设a＞1的正整数，若p是a大于1的最小正因数，则p必为质数
        • 定理2⃣ （判定定理）设a是大于1的正整数，若所有不超过根号a的质数都不能整除a，则a是质数
        • 定理3⃣ 质数有无限个
    • 分解质因数
      • 定义
        • 标准分解式
      • 定理
        • 4⃣（算术基本定理）任一大于1的正整数均可分解质因数；不计较顺序，则分解结果唯一
        • 5⃣在n！的标准分解式中，质因数p的质数为，，，，，
  • 最大公因数
    • 概念
    • 性质
      • 定理
        • 1⃣若a＝bq+r（0≤r≤b），则（a,b）＝（b,r）
        • 2⃣若d＞0，d|a，d|b，则（a,b）＝d↔️存在整数s，t，使得d＝as+bt（贝祖等式）
        • 3⃣设q是a,b的任意一个公因数，d是a,b的一个公因数，则d＝（a,b）
          • 推论：（a，b）＝1↔️存在整数s，t，使得as+bt＝1
        • 4⃣设d|a，d|b，则d＝（a，b）↔️（a/d,b/d）＝1
        • 5⃣(ac,ba)＝c（a,b），常应用于短除法
        • 6⃣若a|bc，且（a，b）＝1，则a|c
          • 推论：设p为质数，若p|ab，则p|a或p|b
        • 7⃣若a|c，b|c，（a，b）＝1，则ab|c
        • 8⃣若（a，b）＝1，则(a，bc)＝(a，c)
          • 推论：a|m，b|m，c|m，且a，b，c两两互质，则abc|m
          • 若（a，b）＝1，则(a的n次方，bn次方)＝1
          • (a的n次方，b的n次方)＝(a，b)n次方，n是正整数
          • 如果一组数a中任意一个与一组数b中任意一个互质，则这两组数的积的互质
    • 求法
      • 分解质因数
        • 写出各数的标准分解式；找共同质因数及其最小次数方，再写成连乘的形式
      • 提取公因数法（短除法）
        • 用定理5⃣逐步提取
      • 辗转相除法
        • 更相减损术
      • 欧拉算法
  • 最小公倍数
    • 概念
    • 性质
      • 定理
        • 1⃣是一组数的一个公倍数，q是其中一个数的公倍数，则m＝这组数的最小公倍数↔️m|q
        • 2⃣设 一组数a|m(p＝1，2，....，n)，则m＝【这组数】↔️（m/a1，m/a2，m/an）＝1
        • 3⃣
    • 求法
      • 分解质因数
        • 写出各数的标准分解式；找出所有质因数及其最高次数，并把到的幂连乘起来
      • 提取公因数
        • 短除法，最外面一圈连乘起来
      • 先求最大公因数法
        • ab的最小公倍数：求得最大公因数，然后ab÷最大公因数
  • 整值函数的整除性
    • 按除数除函数自变量所得余数分类
      • 差为2的一对质数叫做孪生质数。除3和5以外，其他的每队孪生质数之和都能被12整除
      • a.b为整数，且a.b都不能被2和3整除，则24|（a的2次方-b的2次方）
    • 利用因式分解公式
      • 若a，b为整数，n为正整数，则（a-b）|（a的n次-b的n次）
        • 若n为正偶数，（a+b）|（a的n次-b的n次）
        • 若n为正奇数，（a+b）|（a的n次+b的n次）
    • 利用组合数公式的推广结论
      • r!＝n(n-1)(n-2)•••(n-r+1)
    • 利用数学归纳法
      • 当n＝0时，•••••； 设当n＝k时，结论成立，即•••••。当n＝k+1 时，f(k+1)＝••••• 由归纳假设（题目）可知，题目|f（k+1） 由步骤（1）（2）可知题目
    • 利用递推公式
      • 把整值函数式转化成递推公式，通过地推来判定一个整值函数能否被一个整数整除
    • 利用费马小定理
      • p为质数，n为整数，若（p，n）＝1，则p|（n的p-1次—1）
      • p为质数，(p，n)＝1，(p，m)＝1，则p|(n的p-1次——m的p-1次)
      • p为质数，n为正整数，则p|(n的p次—n)
  • 正整数的正因数个数与总和
    • 正整数正因数的个数
      • 定理
        • 若正整数的标准分解式为n＝p1的α1次×p2的α2次•••pm的αm次，则d(n)＝（α1+1）（α2+1）•••（αm+1）
        • 正整数n为完全平方数↔️d（n）为奇数
        • 正整数n的所有不同正因数之积＝n的d(n)/2次方
    • 正整数正因数的和
      • 对n分解质因数，得Sn
    • 完全数、梅森数、亲和数
      • 完全数
        • 正因数之和＝所有小于n的正因数之和➡️完全数➡️S(n)＝2n
        • 2的p-1次方（2的p次方-1）为完全数
      • 梅森数
        • 形如2的p次方-1，的数（p为质数）
      • 亲和数
        • S(n)＝S(m)＝n+m
    • (n,m)＝1➡️d(m,n)＝d(n)d(m)；S(nm)＝S(n)S(m)
• 同余和同余方程
  • 同余的概念及性质
    • 概念
    • 性质
      • 基本性质
      • 可加性
      • 可乘性
      • 可约性
        • • 1.若ac=bc(mod m)，(c,m)=1，则a三b(mod m) 2.若ac三bc(mod cm)，则A三b(Mdm) 3.若 a三b(modcm)，则a三b(mod m) 4.若ac三bc(mod m)，（c，m)=d,则a三b（mod m/d)
    • 被特殊数整除的数的特征
      • 被2或5
        • 末尾数字能被2或5整除
      • 被4或25整除
        • 末两位数字能被4或25整除
      • 能被3或9整除
        • 各位数字之和能被3或9整除
      • 能被11整除
        • 末三位数字与去掉末三位所得数之差，能否被11整除
  • 剩余类和剩余系
    • 剩余类
      • 剩余类/同余类：对模m同余的数的集合，用【r】m表示（模为m，r为余数）
      • 模m的一个剩余类中的一切数，与模m的最大公因数相等
    • 完全剩余系
      • 定义：从模m中的每个剩余类中各取一个数，这m个数组成的集合叫做模m的一个完全剩余系
      • 绝对最小完全剩余系：m为奇数，｛-（m-1)/2,…-1,0,1,…,(m-1)/2｝➡️全是奇数〰〰当m为偶数时，其集合中全是偶数
    • 欧拉函数和简化剩余系
      • 欧拉函数
        • 不超过正整数m又与m互质的正整数的个数记作➰m
      • 简化剩余系
        • 与模m互质的剩余类➰m个，从每类中各取一个数构成的集合
        • 模m的最小正简化剩余系：在模m的最小非负完全剩余系中取得的简化剩余系
  • 费马小定理和欧拉定理
  • 分数与小数的互化
    • 既约真分数与有限纯小数的互化
    • 既约真分数与纯循环小数的互化
    • 既约真分数与或循环小数的互化
  • 一元一次同余方程
    • 求法
      • 1⃣判断：(a,m)=d,d|b➡️有解，有d个解
      • 2⃣求法：
        • 1.欧拉算法
          • 适用于数字小，关系明显者
        • 2.欧拉定理
          • 写解比较容易，化简比较麻烦
        • 3.同解变形法
          • 加模的整数倍，再约系数得解
  • 一元一次同余方程组
    • 模两两互质的同余方程组的解
      • 中国剩余定理：有且仅有一个解（定理）
      • x与b1M1M2'......bnMnMn'关于M同余
    • 模不两两互质的同余方程组有解的判定和求法
      • 判断有无解：(m1,m2)|（b1-b2）
      • 求解方法
        • 代入法
        • 欧拉算法
        • 中国剩余定理
          • 模含有不同质因数时，将模化为标准分解式，即将方程组化为模两两互质的方程组求解
• 不定方程
  • 二元一次不定方程
    • 定理
      • ax+by＝c，（a，b）|c➡️有整数解
    • 求法
      • 1⃣判断有无解，多少个解。能化简的就化简
      • 2⃣求特解
        • 方法1.观察法
        • 方法2.欧拉算法
        • 方法3.辗转相除法
        • 法4.解同余方程法
      • 3⃣写通解
  • 多元一次不定方程
    • 三元一次不定方程
      • 判定：ax+by+cz=d，(a，b，c)|d➡️有解
      • 方法
        • 并项减元法
        • 辗转相除法
    • n元一次不定方程
      • 判定：不定方程中，(a1,a2....an)|d➡️有解
      • 方法
        • 并项减元法
        • 辗转相除法
  • 多元一次不定方程组
    • 求解思路
      • 通过消元减少未知数的个数，转化为一次方程，再把一次方程的通解逐步代回得到原方程的解
  • 特殊非线性不定方程组