数论基础 【第三讲】 第三讲我们要学习的概念有：  线性同余方程 逆元 费马小定理  一、线性同余方程 如下形式的方程我们称作线性同余方程  依据定义可知，该方程表示  模  等于  模  的值  将 模运算写成带余除法的形式  合并化简成线性不定方程  令   可以发现，线性同余方程和线性不定方程是可以相互转化的 回顾之前学过的 裴蜀定理 ，  是  有解的 充要条件 也就是说  也是线性同余方程  有解的 充要条件 那么代码实现和解线性不定方程一样 以  为例，等价于求解  C++： #include<bits/stdc++.h> using namespace std; in...

数论基础 【第二讲】 第二讲我们要学习的概念有：  欧几里得算法 裴蜀定理 扩展欧几里得算法  一、欧几里得算法 在第一讲中我们知道了 gcd 的概念，现在我们来介绍如何计算两个整数  的  首先我们需要知道  的一个重要性质，  证明：  （1）  设  是  和  的任意一个公约数，即  且  ，依据整除的性质： 若  且  ，则  反过来，设  是  和  的任意一个公约数，即  且  ， 同样根据整除的性质： 若  且  ，则  因此，由  和  可得到  这也说明  也是  和  的公约数 综上所述，  和  的所有公约数与  和  的所有公约数完全相同，由于  是公约数集合中最大的...

数论基础 【第一讲】 第一讲我们要学习的概念有：  算术基本定理 带余除法、整除 约数、倍数、质数、公约数、公倍数、 gcd、lcm 模运算 同余式  扩展知识：  同余类 完全剩余系 简化剩余系  一、算数基本定理 算术基本定理是数论中的核心定理之一，其内容可表述为： 每个大于1的正整数都可以唯一地表示为有限个质数的乘积，其中唯一性是指在不考虑质数的顺序的情况下。 具体来说，该定理包含两部分核心含义：   存在性：对于任意一个大于1的正整数 ，总存在至少一组质数 （允许重复），使得  此外，也可以写成如下形式：    唯一性：若  有两种不同的质数乘积表示形式 ，则这两组质数本质上是相同的（...