数数论

初等数论知识体系

字数统计: 1k字   |   阅读时长: 3分
,

摘要: 介绍两本初等数论的书

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

介绍两本初等数论的书书，其中第一本与编程中常见的知识，第二本有一些应用的内容。有需要的时候可以参考。

(1) 初等数论

《初等数论》主要内容

整除理论

  • 自然数与整数
  • 整除的基本性质
  • 带余数除法
  • 最大公约数理论
  • 算术基本定理
  • 整除理论小结
  • n! 的素因数分解式

不定方程1

  • 一次不定方程
  • $x^{2} + y^{2} = z^{2}$ 及其应用

同余的基本知识

  • 同余的定义及基本性质
  • 同余类与剩余系
  • Euler 函数与 $\Phi(m)$
  • Welson定理

同余方程

  • 同余方程的基本概念
  • 一元一次同余方程
  • 一元一次同余方程组(孙子定理)
  • 一元同余方程的一般解法
  • 模为素数的二次剩余
  • Gauss二次互反律
  • Jacobi符号
  • 模为素数的一元高次同余方程
  • 多元同余方程, Chevalley定理

指数与原根

  • 指数
  • 原根
  • 指标,指标组,既约剩余系的构造
  • 二项同余方程

不定方程2

  • $x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + x_{4}^{2} = n$
  • $x^{2} + y^{2} = n$
  • $ax^{2} + by^{2} + cz^{2} = 0$
  • $x^{3} + y ^{3} = z^{3}$

连分数

  • 连分数定义
  • 有限简单连分数
  • 无限简单连分数
  • 无理数的最佳有理逼近
  • 二次无理数与循环连分数
  • $x^{2} - dy^{2} = 1$

素数分布的初等结果

  • Eratosthenes筛法与 $\pi(N)$
  • $\pi(N)$ 的上下界估计
  • Euler恒等式

数论函数

  • 积性函数
  • Mobius变换及其反转公式
  • 数论函数的均值
  • Dirichlet特征

(2) 初等数论及其应用

《初等数论及其应用》主要内容

整数

  • 数和序列
  • 和与积
  • 数学归纳法
  • 斐波那契数
  • 整除性

整数的表示法和运算

  • 整数的表示法
  • 整数的计算机运算
  • 整数运算的复杂度

素数和最大公因子

  • 素数
  • 素数的分布
  • 最大公因子
  • 欧几里得算法
  • 算术基本定理
  • 因子分解法和费马数
  • 线性丢番图方程

同余

  • 同余引言
  • 线性同余方程
  • 中国剩余定理
  • 求解多项式同余方程
  • 线性同余方程组
  • 利用波拉德p方法分解整数

同余的应用

  • 整除性检验
  • 万年历
  • 循环赛赛程
  • 散列函数
  • 校验位

特殊的同余式

  • 威尔逊定理和费马小定理
  • 伪素数
  • 欧拉定理

乘性函数

  • 欧拉φ函数
  • 因子和与因子个数
  • 完全数和梅森素数
  • 莫比乌斯反演

密码学

  • 字符密码
  • 分组密码和流密码
  • 取幂密码
  • 公钥密码
  • 背包密码
  • 密码协议及应用

原根

  • 整数的阶和原根
  • 素数的原根
  • 原根的存在性
  • 指数的算术
  • 用整数的阶和原根进行素性检验
  • 通用指数

原根与整数的阶的应用

  • 伪随机数
  • 埃尔伽莫密码系统
  • 电话线缆绞接中的一个应用

二次剩余

  • 二次剩余与二次非剩余
  • 二次互反律
  • 雅可比符号
  • 欧拉伪素数
  • 零知识证明

十进制分数与连分数

  • 十进制分数
  • 有限连分数
  • 无限连分数
  • 循环连分数
  • 用连分数进行因子分解

某些非线性丢番图方程

  • 毕达哥拉斯三元组
  • 费马大定理
  • 平方和
  • 佩尔方程

高斯整数

  • 高斯整数和高斯素数
  • 最大公因子和唯一因子分解
  • 高斯整数与平方和
Share