前言

免责声明：！！！此文确确实实是博主一字一词地敲出来的，但是此文是博主在 ”青春懵懂时期“ 所写的一篇 ”杂文“，因为这个也不属于我的主专业方向，所以出现任何错误，欢迎各位大佬在评论区指出，小的一定认真修改！（还请大佬们嘴下留情）

一. 整除、算术基本定理、同余、同余类、剩余系的基本定义

1.整除

若整数 $b$ 除以非零整数 $a$，商为整数，且余数为零，$b$ 为被除数，$a$ 为除数，即 $a\mid b$（“$\mid$”是整除符号），读作“a整除b”或“b能被a整除”。

例如：4整除16写作”4 $\mid$ 16“。（注意：“$\mid$” 之前的数为除数，之后的为被除数，别搞反了。）

2.算数基本定理

• 内容：设整数 $N>1$，那么必有 $N=p_1{p}_2\cdots p_n$，其中 $p_1，p_2，\cdots ，p_n$ 是素数，且在不计次序的意义下，这个分解式是唯一的。

  也就是说，任何一个自然数都可以表示为有限个素数的乘积（当然，素数就等于它本身），并且这种分解是唯一的，除非你改变素数的排列顺序。例如：$520=2^3\times 5\times 13$。在这里，520可以被分解为3个2、1个5和1个13的乘积，这样的分解是固定的，只是乘数的顺序可以交换。

• 如果把分解式中的相同素数合并，即得到：
  $$N={p_1}^{a_1}{p_2}^{a_2}\cdots {p_s}^{a_s}$$
  其中$a_1+a_2+\cdots +a_s=n$，$p_1<p_2<\cdots <p_s$（这里的$p_1，p_2，\cdots ，p_s$ 互不相同），称为$N$的标准素因子分解式。

• 证明：对于这个问题，有两个关键点需要证明，一是这个整数$N$凭什么一定能被这样分解？二是为什么这个分解是唯一的？
  前者我把它称作存在性，后者我把它称作唯一性。

  首先证明存在性：

  • 如果这个数是素数，那太好了，素数就是它本身，已经可以看作是素数的乘积了。
  • 如果这个数是合数，那么根据合数的定义，它一定可以分解成为两个更小的因数的乘积，那么如果这两个数都是素数，则满足题意；如果这两个数中存在合数，那么可以继续将其分解为两个更小的数。以此往复，最后得到的一定会都是素数，因为一旦有合数，它就会被分解，分解出的数不会是1，那么剩下的就只能是素数了。

  其次证明唯一性：

  • 预备知识——欧几里得引理

    • 内容：$p$是素数，若 $p\mid ab$，那么有 $p\mid a$ 或 $p\mid b$ 。

    • 证明：（反证）
      显然，当 $p=a$ 或 $p=b$ 时直接可得出该结论。
      当 $p\ne a$ 且 $p\ne b$，现在假设 $p\nmid a$ 且 $p\nmid b$。
      由前面讲存在性的内容可知，这里的 $ab$ 一定可以分解成若干个素数的乘积的形式（注意这里我并没有使用算数基本定理，我只是说可以这样分解，至于是不是唯一的并不重要）。由于 $ab$ 是 $a$ 与 $b$ 的乘积，则 $ab$ 的素因数分解是 $a$ 和 $b$ 的素因数分解的组合（乘积）。而现在 $p\nmid a$ 且 $p\nmid b$，那么 $ab$ 的素因数分解中也一定不会包含 $p$ 这个因子。但是由于 $p\mid ab$，这意味着 $ab$ 一定可以分解出一组含 $p$ 的素因数的乘积的形式（事实上只有一组），即 $ab$ 肯定可以分解出 $p$ 这个因子。于是推出矛盾。即若 $p\mid ab$，那么有 $p\mid a$ 或 $p\mid b$ 证毕。

  • 引入欧几里得引理证明唯一性：
    假设 $N$ 存在两种不同素数分解：
    $$N_1=p_1\times p_2\times \cdots p_m$$
    以及
    $$N_2=q_1\times q_2\times \cdots q_n$$
    由于 $N_1$ 和 $N_2$ 是一样的，所以在 $N_1=p_1，p_2，\cdots p_m$ 这 $m$ 个素数中任意一个素数 $p_i$ 都满足 $p_i\mid N_2$，即
    $$p_i\mid (q_1\times q_2\times \cdots q_n)$$
    那么由上述的欧几里得引理可知，对于这个素数 $p_i$ 来说，一定有
    $$p_i\mid (q_1\times q_2\times \cdots q_j)$$
    或者
    $$p_i\mid (q_{j+1}\times \cdots \times q_{n-1}\times q_n)$$
    而无论是 $p$ 还是 $q$，它们都是素数，意味着 $q$ 不能被任何除 $1$ 和自身的其他数整除辣！那如果 $p_i$ 能整除上面两个式子之一的话，真相只有一个：$p_i=q_k$，即对于一个 $p$，总能找到一个 $q$ 与之对应相等。
    这也就证明了 $N_1$ 和 $N_2$ 所谓的两种分解方式实际上是相等的，因此不存在两种不同的分解方式。换言之，这样的分解是唯一的，证毕。

3.同余

• 基本定义：设 $m$ 是正整数，如果 $a，b$ 的差 $a-b$ 被 $m$ 整除即 $a-b=qm$，就称 $a，b$ 关于模 $m$ 同余，或简称同余。记为：
  $$a\equiv b(\mathrm{mod}m)$$

• 一些性质：(”*“表示比较重要的性质)

  • （反身性）$a\equiv a(\mathrm{mod}m)$.

  • （对称性）若 $a\equiv b(\mathrm{mod}m)$，则 $b\equiv a(\mathrm{mod}m).$

  • （传递性）若 $a\equiv b(\mathrm{mod}m)$，$b\equiv c(\mathrm{mod}m)$，则 $a\equiv c(\mathrm{mod}m).$

  • *若 $a\equiv b(\mathrm{mod}m)$，$c\equiv d(\mathrm{mod}m)$，则 $a\pm c\equiv b\pm d(\mathrm{mod}m)$.

  • *若 $a\equiv b(\mathrm{mod}m)$，$c\equiv d(\mathrm{mod}m)$，则 $ac\equiv bd(\mathrm{mod}m)$.

  • *若 $a\equiv b(\mathrm{mod}m)$，$n\in N$，则 $a^n\equiv b^n(\mathrm{mod}m)$.

  • *$a\equiv b(\mathrm{mod}m)$ $\iff$ $a-b=km$

4.同余类（也叫剩余类）

• 基本定义：同余是一种运算，它反映了两个数之间的某种联系，比如说$16$和$9$除以$7$的余数都为$2$，即 $16\equiv 9(\mathrm{mod}7)$。
  在这种层面上，同余可以理解为一种等价关系。因此，我们可以把整数集 $Z$ 根据模 $m$ 进行分类：

  如果 $a，b$ 同余，则 $a，b$ 属于同一类，否则不属于同一类，这样我们就会得到 $m$ 个类，即：
  M i = { i + k m   ∣   k ∈ Z } , i = 0 , 1 , 2 , ⋯   , m − 1 , M_i=\{i+km\ |\ k\in Z\},i=0,1,2,\cdots,m-1, Mi​={i+km ∣ k∈Z},i=0,1,2,⋯,m−1,
  它们称为模 $m$ 的同余类（或剩余类）。

• 也就是说，同余类（剩余类）是一个集合，而它的其中任意一个元素叫做剩余，或叫代表元。

5.剩余系

• 基本定义：从不同剩余类中选取一个数，也就是代表元，这些代表元形成的一个集合，叫做剩余系。也就是说剩余系中的每个数都是不同剩余类的代表元。

• 剩余系中存在两种情况：完全剩余系和简化剩余系

  • **完全剩余系：**如果我们把每个不同的剩余系中的一个代表元都取出来作为这个剩余系中的元素，那这个剩余系就是完全剩余系。举个例子，对于模$5$来说，它的完全剩余系就是： { 0 , 1 , 2 , 3 , 4 } \{0,1,2,3,4\} {0,1,2,3,4}。
    当然，像 { 1 , 2 , 3 , 4 , 5 } \{1,2,3,4,5\} {1,2,3,4,5}， { 0 , 6 , 2 , 3 , 4 } \{0,6,2,3,4\} {0,6,2,3,4}，$\cdots$这样的其实和上面的本质上是等价的，但为了方便一般都写成是上面的那种。

  • 简化剩余系：对于模 $m$ 来说，在它的完全剩余系中去掉几个数就是简化剩余系。而去掉的这几个数就是与 $m$ 不互素的数。
    举个例子，对于模$8$来说，它的完全剩余系是： { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 } \{0,1,2,3,4,5,6,7\} {0,1,2,3,4,5,6,7}，其中$0,2,4,6$都和$8$不互素（注意$0$和$8$的最小公因数是8），因此从中去掉，剩下的 { 1 , 3 , 5 , 7 } \{1,3,5,7\} {1,3,5,7}就是对于模$8$的简化剩余系

二. 费马小定理的内容及其证明

1.费马小定理基本内容

• 内容：如果 $p$ 是一个质数，$a$ 不能被 $p$ 整除，那么有：

$$a^{p-1}\equiv 1(\mathrm{mod}p)$$

• 除此之外还有一个变形形式：如果 $p$ 是一个质数，对于任意整数 $a$，都有：

$$a^p\equiv a(\mathrm{mod}p)$$

​ 根据前面说到的同余的性质，实际上就是同余两边同时乘以 $a$ 得到的。那为什么这个公式可以对任意整数 $a$ 都成立呢？
​ 也就是说这个公式在 $a$ 能被 $p$ 整除的情况下依然成立，来看一下：
​ 当 $p\mid a$ 时，即 $a$ 是 $p$ 的倍数，即$a=pk$。此时
$$a^p-a=(pk{)}^p-pk=p(p^{p-1}k-k)$$
​ 这个式子含了 $p$，说明它可以被 $p$ 整除。即 $a^p-a\equiv 0(\mathrm{mod}p)$，而由同余的性质：
$$a^p-a\equiv 0(\mathrm{mod}p)\iff a^p\equiv a(\mathrm{mod}p)$$

2.费马小定理的证明（interesting 版）

• 证明：定理的证明千篇一律，有趣的思维万里挑一。这里我想用一种有趣的方式进行证明，过程如下：

  假设现在有一串珠子形成了一个环，环上珠子的数量是 $p$（$p$是素数），现在我有 $a$ 种颜色，我要给这个环上的每一个珠子进行上色。根据小学知识，每个珠子的上色情况都有 $a$ 种，因此总共有 $a^p$ 种上色方式。

  假如我要用至少两种颜色进行上色，总共就有 $(a^p-a)$ 种上色方式。我们现在要证明的是 $a^p-a\equiv 0(\mathrm{mod}p)$，也就是证明 $a^p-a$ 这个式子能够被 $p$ 整除，即证明 $a^p-a=kp$ 。

  又回到这个给环上色问题上，问题就可以转化为：如果我们可以把至少用两种颜色这一情况分成 $k$ 组，每组都刚好有 $p$ 种上色方式
  那我们就可以证明 $a^p-a$ 是 $p$ 的 $k$ 倍了！

总共 $a^p$ 种上色方式 $\{\begin{array}{l}一种颜色:a\\ \\ \\ 至少两种颜色：a^p-a\{\begin{array}{l}p种\\ p种\\ ⋮\\ p种\end{array}\end{array}$
为了方便，我们把可以通过旋转得到一模一样的两种上色方式称为”同款“，如下：

现在我们把”同款“的上色方式放在一组里面，由上图不难发现，当我们关注红色的珠子时，当它绕着旋转一圈后，它把每个位置都经过了一边。也就是说，当我们把这个环进行旋转时，它所出现的不同上色方式恰好就是这个环上的珠子的个数，也就是 $p$。也就说明了”同款“里不同的上色方式就是 $p$ 种。即我们确实可以把 $(a^p-a)$ 种上色方式分成若干个 $p$ 种上色方式。

BUT！这好像有个bug啊…万一在旋转过程中出现了两个一模一样的上色咋办？请看VCR：

别急！这个时候，$p$ 是素数的条件就很关键了。既然是素数，就说明它只能被1和它本身整除，所以说实际上是不可能出现像上面那样有几个完整周期排列的。只要不是由几个完整的周期依次排列成环的，就不会出现像上面那样转了不到一圈就完全重合的现象。

综上，我们就说明了在 $(a^p-a)$ 种上色方式中，我们可以把它分成 $k$ 组，每组都恰好有 $p$ 种上色方式。即
$$\begin{gathered} a^p-a=kp \\ \Updownarrow \\ {a}^p-a\equiv 0(\mathrm{mod}p) \\ \Updownarrow \\ {a}^p\equiv a(\mathrm{mod}p) \\ \Updownarrow \\ {a}^{p-1}\equiv 1(\mathrm{mod}p) \end{gathered}$$
费马小定理，证毕！

三. 欧拉函数

1.欧拉函数的定义

• 欧拉函数：对于一个正整数 $m$，小于 $m$ 的正整数中与 $n$ 互素的数（包括1）的个数为 $s$，并定义 $\phi (m)=s$，$\phi (m)$ 称为欧拉函数。

2.欧拉函数的性质

• 性质 1：若 $a$ 和 $b$ 互素，则
  $$\phi (ab)=\phi (a)\phi (b)\text{\hspace{1em}(1)}$$

• 性质 2：若 $m,n$ 满足 $m\mid n$，则
  $$\phi (m)\mid \phi (n)\text{\hspace{1em}(2)}$$

• 性质 3： 如果 $p$ 是一个素数，则

$$\phi (p)=p-1\text{\hspace{1em}(3)}$$

• 性质 4： 如果 $p$ 是素数，$k$ 是正整数，则

$$\phi (p^k)=p^k-p^{k-1}=p^{k-1}(p-1)\text{\hspace{1em}(4)}$$

证明：

设 $\phi (n)=\phi (p^k)$，即 $n=p^k$。

那么由于 $p$ 是一个素数，所以只要一个数的素因数里不包含 $p$，那么这个数就能与 $n$ 互素。反之只要含 $p$ 这个素因数，那么就不和 $n$ 互素。也就是说像 $p,2p,\cdots p^{k-1}p$ 这些数都不与 $n=p^k$ 互素。那么与 $n$ 互素的就有 $p^k-p^{k-1}$ 个了，即
$$\phi (n)=\phi (p^k)=p^k-p^{k-1}=p^{k-1}(p-1)$$

• 性质 5： 对于 $n$ 的质因数分解 $n=p_1^{k_1}{p}_2^{k_2}\cdots p_m^{k_m}$，则
  $$\phi (n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_m}\right)\text{\hspace{1em}(5)}$$

证明：利用性质 1，$\phi (n)$ 可以表示为各素因数的积，即
$$\phi (n)=\phi (p_1^{k_1})\cdot \phi (p_2^{k_2})\cdots \phi (p_m^{k_m})$$
对此，我来说明几点：

由于 $p_1,p_2,\cdots p_m$ 都是不同的素数，因此无论它们乘了多少次方，又或者把它们乘方之后拿其中几个相乘，它们之间一定不会有相同的因数的。换句话说，$p_1^{k_1},p_2^{k_2},\cdots p_m^{k_m}$ 这些数两两之间都是互素的。因此满足性质 1 的条件——“若 $a$ 和 $b$ 互素”。

那为什么性质 1 的（1）式里面只拆成了两项，而这里可以拆成这么多项？
其实仔细想想就知道，我假设就拆成两项，这两项都是由不同的素数相乘得到的，这两项肯定互素，因此还可以再拆，直到最后就只剩下单独的一个 $\phi (p_i^{k_i})$。

于是，我们根据性质 4 进一步展开为：
$$\phi (n)=p_1^{k_1}\left(1-\frac{1}{p_1}\right)\cdot p_2^{k_2}\left(1-\frac{1}{p_2}\right)\cdots p_m^{k_m}\left(1-\frac{1}{p_m}\right)$$

把括号外的所有 $p_i^{k_i}$ 合并起来，会发现 $p_1^{k_1}{p}_2^{k_2}\cdots p_m^{k_m}$ 就是 $n$。于是
$$\phi (n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_m}\right)$$
证毕！

3.欧拉函数的求法

• 根据定义进行求解

  例如，我们求解 $\phi (10)$，可以把所有小于10的正整数全部列出来： { 1 , 2 , ⋯ 9 , 10 } \{1,2,\cdots9,10\} {1,2,⋯9,10}，再去掉与10不互素的数，最后 $\phi (10)=4$。
  当然这个方法确实挺万能的，前提是你有时间…

• 若 $m$ 是一个素数，可以直接根据上面提到的（3）式进行求解
  例如，$\phi (7)=7-1=6$。

• 若 $m$ 不是一个素数，我们可以根据性质1将其拆分为两个欧拉函数的乘积的形式，再通过性质2，也就是（3）式进行求解
  例如，$\phi (66)=\phi (6)\phi (11)=\phi (2)\phi (3)\phi (11)=(2-1)\times (3-1)\times (11-1)=20$

  （注意拆出的两个数一定要是互素的，否则不能这样拆）

• 若 $m=p^k$，

• *当然，欧拉函数的求法有一个通式，也就是我们上面提到的（5）式：
  $$\phi (n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots \left(1-\frac{1}{p_m}\right)$$

四. 欧拉定理

1.欧拉定理的内容

• 欧拉定理：若 $a,n$ 均为正整数，且 $\gcd (a,n)=1$，则

$$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$$

​ 不是，这个式子怎么这么眼熟…看看之前的费马小定理：
$$a^{p-1}\equiv 1(\mathrm{mod}p)$$
​ 其中 $p$ 是素数，又根据我们欧拉函数的性质 3可知，这个费马小定理实际上就是欧拉定理的一种特殊情况。

2.欧拉定理的证明

证：设小于 $n$ 且与 $n$ 互素的所有正整数构成一个集合 Z n = { x 1 , x 2 , ⋯ x φ ( n ) } \Z_n=\{x_1,x_2,\cdots x_{\varphi(n)}\} Zn​={x1​,x2​,⋯xφ(n)​}，共 $\phi (n)$ 个元素。

现在，我将把 ${\mathbb{Z}}_n$ 中的每个元素进行一个运算得到另一个值 $m$：
$$\begin{gathered} a{x}_1\mathrm{mod}n=m_1 \\ a{x}_2\mathrm{mod}n=m_2 \\ ⋮ \\ a{x}_{\phi (n)}\mathrm{mod}n=m_{\phi (n)} \end{gathered}$$

知道 $m$ 是怎么来的之后，现在我把这所有的 $m$ 组成一个新的集合 S = { m 1 , m 2 , ⋯ m φ ( x ) } S=\{m_1,m_2,\cdots m_{\varphi(x)}\} S={m1​,m2​,⋯mφ(x)​}，共 $\phi (n)$ 个元素。

现在我说 ${\mathbb{Z}}_n=S$ 你信吗？不妨来证明一下：

由最开始的条件可知，$a$ 与 $n$ 互素，集合 ${\mathbb{Z}}_n$ 中的任意一个元素 $x_i$ 也与 $n$ 互素。那么易知它们的乘积 $a{x}_i$ 同样也与 $n$ 互素。这是因为 $a$ 和 $x_i$ 都无法拆分出一个 $n$ 的约数，那它们的乘积当然也就拆不出这么一个数，因此互素。又因为 $m$ 的值是通过 $a{x}_i$ 模 $n$ 得到的，我们都知道模运算并不会改变数与模数之间的最大公约数，所以可以推出 $m$ 与 $n$ 互素。

简而言之就是
$$(a,n)=1,(x_i,n)=1\Rightarrow (a{x}_i,n)=1\Rightarrow (m_i,n)=1\text{\hspace{1em}(7)}$$
又由于 ${\mathbb{Z}}_n$ 中的元素介于 $n$ 之间，任意两个元素之间互不相等，于是无论它们模 $n$ 还是乘以 $a$ 之后模 $n$，都是不相等的：
$$\begin{gathered} x_i\ne x_j\Rightarrow (x_i\mathrm{mod}n)\ne (x_j\mathrm{mod}n)\Rightarrow (a{x}_i\mathrm{mod}n)\ne (a{x}_j\mathrm{mod}n) \\ \Downarrow \\ {m}_i\ne m_j\text{\hspace{1em}(8)} \end{gathered}$$
因此，（7）和（8）就说明了一件事情：集合 $S$ 中的元素与 $n$ 互素且与互不相等。那我们都知道，这样的集合肯定是唯一确定的，那这不就是集合 ${\mathbb{Z}}_n$ 吗？因此我们得出了 一个很重要的结论：
$${\mathbb{Z}}_n=S$$
于是这两个集合内的每个元素相乘最后的结果肯定相等，即
$$\prod _{n=1}^{\phi (n)}{x}_i=\prod _{n=1}^{\phi (n)}{m}_i$$
因此它们模 $n$ 之后也相等，即
$$\prod _{n=1}^{\phi (n)}{x}_i\mathrm{mod}n=\prod _{n=1}^{\phi (n)}{m}_i\mathrm{mod}n$$
我们对这个这个等式做进一步分析
$$\begin{array}{rl}\prod _{n=1}^{\phi (n)}{x}_i\mathrm{mod}n& =\prod _{n=1}^{\phi (n)}{m}_i\mathrm{mod}n\\ & =(m_1\cdot m_2\cdot \cdots m_{\phi (n)})\mathrm{mod}n\\ & =[(a{x}_1\mathrm{mod}n)\cdots (a{x}_{\phi (n)}\mathrm{mod}n)]\mathrm{mod}n\end{array}$$
由模运算的性质可知，该等式可以进一步转化为
$$=(a{x}_1\cdot a{x}_2\cdot \cdots a{x}_{\phi (n)})\mathrm{mod}n$$
将所有的 $a$ 合并，即
$$\begin{array}{rl}& =(a^{\phi (n)}\cdot x_1\cdot x_2\cdots x_{\phi (n)})\mathrm{mod}n\\ & =(a^{\phi (n)}\prod _{n=1}^{\phi (n)}{x}_i)\mathrm{mod}n\end{array}$$
好家伙，这好长一串等式… 但是最后我们看看首尾都得到了什么
$$(a^{\phi (n)}\prod _{n=1}^{\phi (n)}{x}_i)\mathrm{mod}n=\prod _{n=1}^{\phi (n)}{x}_i\mathrm{mod}n$$
根据瞪眼法，emm…其实是同余的性质啦，我们可以两边同时去除以 ${\prod }_{n=1}^{\phi (n)}{x}_i$，最终得到
$$\begin{gathered} a^{\phi (n)}\mathrm{mod}n=1\mathrm{mod}n \\ \Downarrow \\ {a}^{\phi (n)}\equiv 1(\mathrm{mod}n) \end{gathered}$$
欧拉定理，证毕！

五. 扩展欧拉定理

1.扩展欧拉定理的内容

• 顾名思义，这是欧拉定理的拓展，也就是一般形式。

• 对于任意的正整数 $a,b,n$，若 $b\ge \phi (n)$ ，则有

  $$\begin{gathered} a^b\equiv a^{b\mathrm{mod}\phi (n)+\phi (n)}(\mathrm{mod}n) \\ (b\ge \phi (n)) \end{gathered}$$

2.扩展欧拉定理的证明

• 引理 1：
  $$a^b\equiv a^{b\mathrm{mod}\phi (n)}(\mathrm{mod}n)$$
  证：我们都知道欧拉定理，即当 $\gcd (a,n)=1$，有
  $$a^{\phi (n)}\equiv 1(\mathrm{mod}n)$$
  现在不妨设 $b=k\phi (n)+t，t=b\mathrm{mod}\phi (n)$，其中 $k\in \mathbb{Z}$。

  那么就有
  $$\begin{array}{rl}{a}^b\mathrm{mod}n& =a^{k\phi (n)+t}\mathrm{mod}n\\ & =(a^{\phi (n)}{)}^k\cdot a^t\mathrm{mod}n\end{array}$$
  根据欧拉定理以及模运算的性质，可得
  $$\begin{array}{rl}& =1^k\cdot a^t\mathrm{mod}n\\ & =a^{b\mathrm{mod}\phi (n)}\mathrm{mod}n\end{array}$$
  综上，我们就得到了
  $$\begin{gathered} a^b\mathrm{mod}n=a^{b\mathrm{mod}\phi (n)}\mathrm{mod}n \\ \Downarrow \\ {a}^b\equiv a^{b\mathrm{mod}\phi (n)}(\mathrm{mod}n) \end{gathered}$$
  而这个式子，就是欧拉定理的推，这里把它叫做引理 1。

• 引理 2：

  若 $p$ 是素数，$q$ 是正整数且 $q>1$，则
  $$\phi (p^q)\ge q$$
  证：由前面提到的欧拉函数的性质 4，也就是（5）式可知
  $$\phi (p^q)=p^q-p^{q-1}=p^{q-1}(p-1)$$

  • 当 $p,q$ 都为2时，易知 $\phi (4)=2\ge 2$ 没毛病。

  • 当 $p=2,q>2$ 时，$q$ 每增加1，$\phi (p^q)$ 都是成倍成倍地增加，所以肯定不等式右边比左边增加快得多，因此成立。

  • 当 $q=2,p>2$ 时，$p$ 在增加的时候，$\phi (p^q)$ 自然也在增加，而不等式右边的值不变，因此同样成立。

• 扩展欧拉定理的证明

  • 当 $\gcd (a,n)=1$ 时，由同余的性质
    $$\begin{gathered} a^{\phi (n)}\equiv 1(\mathrm{mod}n),a^b\equiv a^{b\mathrm{mod}\phi (n)}(\mathrm{mod}n) \\ \Downarrow \\ {a}^b\equiv a^{b\mathrm{mod}\phi (n)+\phi (n)}(\mathrm{mod}n) \end{gathered}$$

  ​ 显然成立。

  • 当 $\gcd (a,n)\ne 1$ 时，我们对 $n$ 进行标准素因子分解，可得
    $$n={p_1}^{q_1}{p_2}^{q_2}\cdots {p_s}^{q_s}=\prod _{i=1}^s{p}_i^{q_i}$$

  这个时候我们只需要证明对于任意一个 $p_i^{q_i}$，都有 $a^b\equiv a^{b\mathrm{mod}\phi (n)+\phi (n)}(\mathrm{mod}{p}_i^{q_i})$ 成立即可。何以见得？因为根据同余的一个很重要的性质，若

$$\begin{gathered} x\equiv y(\mathrm{mod}{n}_1),x\equiv y(\mathrm{mod}{n}_2) \\ \Downarrow \\ x\equiv y(\mathrm{mod}\mathrm{Lcm}[n_1,n_2]) \end{gathered}$$

而由于我们这里的 $p_i^{q_i}$ 之间一定是互素的，因此当所有的 $p_i^{q_i}$ 都满足条件时，他们的最小公倍数也就是他们全部乘起来，即 $n$。

由于 $\gcd (a,n)\ne 1$ ，说明 $a$ 肯定是至少是某一个 $p_i^{q_i}$ 的倍数。这个时候我们再分类讨论一下：

(Ⅰ)当 $\gcd (a,p_i^{q_i})=1$ 时

由引理 1我们知道 $a^b\equiv a^{b\mathrm{mod}\phi (n)}(\mathrm{mod}n)$，而这个 $n$ 是 $p_i^{q_i}$ 的倍数，不难发现，如果我把这里的模数 $n$ 缩小一定的倍数，即缩小到 $p_i^{q_i}$，这个引理 1的式子依旧是成立的，于是有：
$$a^b\equiv a^{b\mathrm{mod}\phi (n)}(\mathrm{mod}{p}_i^{q_i})$$
同理有：
$$a^{\phi (n)}\equiv 1(\mathrm{mod}{p}_i^{q_i})$$
两边相乘即有：
$$a^b\equiv a^{b\mathrm{mod}\phi (n)+\phi (n)}(\mathrm{mod}{p}_i^{q_i})$$
情况 (Ⅰ)证明完毕。

(Ⅱ) 当 $\gcd (a,p_i^{q_i})\ne 1$ 时

这种情况下，$a$ 必然是 $p_i$ 的倍数，假设 $a=kp$

这时就要用到我们的引理 2了，我们都知道前提条件 $b\ge \phi (n)$ 以及引理 2证明过的 $\phi (p_i^{q_i})\ge q_i$，因此有：
$$b\ge \phi (n)\ge \phi (p_i^{q_i})\ge q_i$$
我们得到了 $b\ge q_i$，这可不得了了，那么我们就注意到此时 $a^b=(kp{)}^b=k^b{p}^b$ 一定是 $p_i^{q_i}$ 的倍数

而 $a^{b\mathrm{mod}\phi (n)+\phi (n)}$ 也一定是 $p_i^{q_i}$ 的倍数！

因此既然这样，我们也就可以写出：
$$a^b\equiv a^{b\mathrm{mod}\phi (n)+\phi (n)}\equiv 0(\mathrm{mod}{p}_i^{q_i})$$
证毕！

六. 快速幂的算法

1.快速幂算法的概述

• 快速幂算法是一种用于计算幂运算的高效算法。它通过将指数进行二进制拆分，并利用指数的二进制表示形式来减少乘法和幂运算的次数，从而提高计算速度。

2.快速幂的算法

• level 1

  当我们要计算 $a^{64}$ 时，我们可以一个一个算的方式即：$a\times a\times \cdots a$，这样算64次即可得出答案，但是这样显然太复杂了

• level 2

  我们可以利用幂运算的性质，即：

$$\begin{gathered} a^1\times a^1=a^2 \\ {a}^2\times a^2=a^4 \\ ⋮ \\ {a}^{32}\times a^{32}=a^{64} \end{gathered}$$

​ 这样的话，我们就只需要算6次就可以啦。

• level 3

  但是，$a^{64}$ 这个例子有点特殊了，我们发现它的指数，也就死 $a^n$ 中的 $n$，恰好是2的幂。那如果不是呢？比如 $a^{105}$。
  注意到，虽然105不是2的幂，但是它可以拆解成几个2的幂的和的形式：
  $$105=1+8+32+64$$
  于是
  $$\begin{array}{rl}{a}^{105}& =a^{1+8+32+64}\\ & =a^1\times a^8\times a^{32}\times a^{64}\end{array}$$
  接下来再用上面 level 2 中讲到的方法计算就可以了。

  问题的关键就在于，如何把一个数分解称为2的 $n$ 次幂之和呢？

• level 4

  这时候就要用到我们的二进制了，我们高中的时候都学过一个数表示成二进制的转换方法。例如：二进制数1011，它的值在10进制中可以表示为 $1\times 2^0+1\times 2^1+0\times 2^2+1\times 2^3$，也就是11.

  通过这个转换方法，我们就可以把指数 $n$ 转换称为 $2^k$ 的序列之和的形式，通过一次或多次这样的转换之后，这样我们就只需要计算 $a,a^2,a^4\cdots a^{(2^k)}$ 这样的数的值，然后再将它们相乘，即可完成整个幂运算。

七. 裴蜀定理（贝祖定理）

1.内容：设 $d$ 是 $(a,b)$ 的最大公约数（通常记作 $(a,b)$），则有整数 $u,v$，使得 $ua+vb=d$。

2.证明：
我们可以通过小学就学过的辗转相除法来证明这一结果。

• 设 $a$ 和 $b$ 是两个整数，且假设 $a>b$（不满足无所谓，可以交换它们）。我们通过辗转相除法的原理，可以把 $a$ 写成：

$$a=b{q}_1+r_1$$

其中，$q_1$是商，$r_1$ 是余数。
如果 $r_1=0$，那么 $\gcd (a,b)=b$。此时裴蜀定理是显然成立的，取 $u=0$ 和 $v=1$ 即可。
如果 $r_1\ne 0$，则继续进行辗转相除法：
$$b=r_1{q}_2+r_2$$
重复这一过程，直到余数为 0。设最后一次余数为 $r_k$，那么：
$$\begin{gathered} ⋮ \\ {r}_{k-3}=r_{k-2}{q}_{k-1}+r_{k-1} \\ {r}_{k-2}=r_{k-1}{q}_k+r_k \end{gathered}$$
当我们结束时，那么最后的 $r_k=0$，此时根据辗转相除法的结果，$ r_{k-1}$ 就是 $a$ 和 $b$ 的最大公因数，即 $\gcd (a,b)=r_{k-1}$。

• 一步步往回代

  通过上面的算法，我们得到了 $\gcd (a,b)=r_{k-1}$。接下来，我们从最后一步逐步回代，找到 $x$ 和 $y$，使得：

$$r_{k-1}=ax+by$$

现在我们从最后一步开始，由上面的式子我们可以得到：
$$r_k=r_{k-2}-r_{k-1}{q}_k$$
将 $r_{k-1}$ 用前一步的表达式代入可得：
$$r_{k-1}=r_{k-3}-(r_{k-4}-r_{k-3}{q}_{k-2})q_{k-1}=\dots$$
每次都将上一步得到的余数表达式代入，最终我们会得到 $r_{k-1}=(一坨表达式)a+(另一坨表达式)b$ 的形式，而我们这两坨表达式里面的数都是若干个整数通过加法减法运算得到的，因此最后的结果也一定是整数。

因此，我们也就通过这样一步步回代的方式最终找到了对应的 $u,v$，使得
$$r_{k-1}=\gcd (a,b)=ua+vb$$
上面的字母太多了…看着烦，我们通过一个例子来感受一下这个过程。

• 示例：

（累了，让我偷个懒吧。。。）

八. 扩展欧几里得算法

1.内容：

• 对于一个不定方程

$$ax+by=\gcd (a,b)$$

来说，由裴祖定理我们知道这个方程一定是有解的，那么我们去求一组非零整数解 $(x,y)$ 的过程，叫做扩展欧几里得算法。

它的基本原理，也就是我们上面证明裴祖定理用到的回代的方法。具体是怎么实现的？后续会给出代码。

• To be continue…

九. 群论基础知识

1.群的定义

• 设 $G$ 是一个非空集合，“$\cdot$”是上的 $G$ 上的一个代数运算（注意这里的这个 “$\cdot$” 运算是广义的，并不是小学学的普通的乘法，它可以是任意一种运算，只要它满足这样的几个条件，它就可以作为群定义中的一种运算），如果该运算满足以下条件：

  ①（封闭性）对任意的 $a,b\in G$ 都有 $a\cdot b\in G$
  ②（结合律）对任意的 $a,b,c\in G$，都有 $(a\cdot b)\cdot c=a\cdot (b\cdot c)$
  ③（单位元）存在 $e\in G$，使得对任意的 $a\in G$，都有 $e\cdot a=a\cdot e=a$，此时 $e$ 称为单位元
  ④（逆的存在性）对任意的 $a\in G$，存在 $b\in G$，使得 $a\cdot b=b\cdot a=e$，此时称 $a$ 与 $b$ 互为逆元

满足以上条件，则称 $G$ 关于“$\cdot$”构成一个群，记作 $(G,\cdot )$

例如：所有实数在普通加法运算下构成群 $R^{+}$。

• 有限群：如果群中的元素个数有限，则称群 $G$ 为有限群
• 阿贝尔群：如果一个群的这种运算满足了交换律，即：$g_1\cdot g_2=g_2\cdot g_1$，则称这个群为阿贝尔群或交换群

2.群的幂运算

对于群中的任意元素 $a$，定义 $a$ 的 $n$ 次幂为：
$$a^n=(a\cdot a\cdot \cdots a),n\in N$$
其中 $a$ 在括号里出现 $n$ 次。
注意：这里的 “$\cdot$” 依然是定义在群中的运算，以下在群论基础这一大类中提到的 $a^n$ 均为群的幂运算。

3.群论中的”阶"

• 当群的元素个数是有限多个时，群这个集合中的元素个数就是群的阶。

• 对于群中的一个元素 $a$，使得 $a^n=e$（$e$ 为单位元）的最小正整数 $n$，叫做元素的阶。

4.子群与陪集

• 子群：设 $G$ 是一个群，$H$ 是其非空子集，若 $H$ 对 $G$ 的运算也构成一个群，则称 $H$ 为 $G$ 的子群。

• 子群的判定

  判定定理 1：

  设 $G$ 是一个群，$H$ 是其非空子集，则 $H$ 是 $G$ 的子群当且仅当——

  • $\forall a,b\in H$，都有 $a\cdot b\in H$（封闭）
  • $\forall a\in H$ 有 $a^{-1}\in H$（逆元）

  证：必要性是显然成立的，那么对于充分性，只需证明 $e\in H$。

  因为 $H$ 非空，则存在 $a\in H$，由条件可知，$a^{-1}\in H$，因此根据已知的封闭性可得 $a\cdot a^{-1}=e\in H$。

  判定定理 2：

  设 $G$ 是一个群，$H$ 是其非空子集，则 $H$ 是 $G$ 的子群当且仅当—— $a{b}^{-1}\in H$

  证：To be added…

• 陪集：设 H = { e , h 2 , … h m } H=\{e,h_2,\ldots h_m\} H={e,h2​,…hm​} 是 $G$ 的一个子群，对与某个元素 $g\in G$，集合 g H = { g e , g h 2 , … g h m } gH=\{ge,gh_2,\ldots gh_m\} gH={ge,gh2​,…ghm​}称为 $H$ 的一个左陪集

  同理， H g = { e g , h 2 g , … h m g } Hg=\{eg,h_2g,\ldots h_mg\} Hg={eg,h2​g,…hm​g} 称为 $H$ 的一个右陪集。

5.同态和同构

• 单射，满射，双射

在高中阶段我们都学过映射，它反映了非空集合 $X$ 的元素 $x$ 到非空集合 $Y$ 的元素 $y$ 的关系。

单射：每一个 $x$ 都有唯一的 $y$ 与之对应；

满射：每一个 $y$ 都必有至少一个 $x$ 与之对应；

双射（又叫一一对应）：每一个 $x$ 都有 $y$ 与之对应，每一个 $y$ 都有 $x$ 与之对应。

• 同构

设有群 $(G,\ast )$ 和群 $(H,\cdot )$，同构指 $G$ 和 $H$ 存在函数：$f:G\to H$，使得对于 $G$ 中的所有 $a$ 和 $b$ 以及 $H$ 中的所有 $A$ 和 $B$，有 $f(a\ast b)=A\cdot B$，其中 $f(a)=A$，$f(b)=B$。记作 $G\cong H$。

例如：整数加法群 $(Z,+)$ 与偶数加法群 $(2Z,+)$ 是同构的。映射 $Z\to 2Z$ 定义为 $f(x)=2x$。

• 同态

设有群 $(G,\ast )$ 和群 $(H,\cdot )$，同态指 $G$ 和 $H$ 存在函数：$f:G\to H$，使得对于 $G$ 中的所有 $a$ 和 $b$，有 $f(a\ast b)=A\cdot B$，其中 $f(a)=A$且 $f(b)=B$。

可见，同态并没有要求 $f$ 是一个双射，是一个单射或满射，单射时称为单同态，满射时称为满同态。

例如：群 $G(R,+)$ 和群 $H(R^{+},\times )$ 是同构的。映射方法为 $f(x)=e^x$。因为 $f(x+y)=e^x{e}^y=f(x)f(y)$，因此它们是同态的。

6.循环群与生成元

如果集合 { a , a 2 , a 3 , ⋯   , a k } \{a,a^2,a^3,\cdots,a^k\} {a,a2,a3,⋯,ak} 包含了 $G$ 的所有元素，称 $a$ 生成群 $(G,\ast )$，且群 $(G,\ast )$ 的阶等于 $a$ 的阶。
能够以这种方式生成的群叫做循环群。$a$ 称为 $(G,\ast )$ 的生成元。

例如：模 $6$ 意义下的加法群 $(G,+(\mathrm{mod}6))$ 是一个循环群，它包含 $6$ 个元素： { 0 , 1 , 2 , 3 , 4 , 5 } \{0,1,2,3,4,5\} {0,1,2,3,4,5}。
整数 $1$ 可以作为它的一个生成元，因为由 $1$ 便可以通过群的幂运算以及这个群中定义的运算来得到其他元素，比如 $(1+1)\mathrm{mod}6=2$。

十. 阶与原根

• 阶

设 $m>1$ 且 $\gcd (a,m)=1$，则使得
$$a^t\equiv 1(\mathrm{mod}m)$$
成立的最小正整数 $t$ 称为 $a$ 对模 $m$ 的阶，记为 ${\delta }_m(a)$ 或 $\mathrm{or}{\mathrm{d}}_{\mathrm{m}}a$

例如：$m=9$ 时，与 $9$ 互质的数有 $1,2,4,5,7,8$，就拿 $2$ 来讲，它在幂运算下模 $9$ 的结果如下：（定义这里的幂运算为乘法）
$$\begin{gathered} 2^1\mathrm{mod}9=2 \\ {2}^2\mathrm{mod}9=4 \\ {2}^3\mathrm{mod}9=8 \\ {2}^4\mathrm{mod}9=7 \\ {2}^5\mathrm{mod}9=5 \\ {2}^6\mathrm{mod}9=1 \end{gathered}$$
可以看到当运算到第 $6$ 次的时候第一次出现了模 $9$ 余 $1$ 的情况，那么我们就说 $2$ 对模 $9$ 的阶是 $6$。

• 原根

设 $m$ 是正整数，$a$ 是整数，若 $a$ 对模 $m$ 的阶等于 $\phi (m)$，则称 $a$ 为模 $m$ 的一个原根。（$\phi (m)$ 表示欧拉函数）

就拿上面提到的例子来说，不难发现 $\phi (9)=6$，而 $2$ 对模 $9$ 的阶恰好是 $6$，那么这时 $2$ 就是模 $9$ 的原根。

• 关于原根的一些性质

性质 1：模 $n$ 有原根的冲要条件是 $n=2,,4,p^k,2p^k$，其中 $p$ 为奇素数，$k$ 为正整数。

性质 2：当正整数 $n$ 有原根时，那么 $m$ 有 $\phi (\phi (m))$ 个原根。

性质 2（推广）：当我们得知了最小原根为 $a$ 的情况下，我们如何得知其他的原根呢？

我们只需要找出在 $[1,\phi (m))$ 内与 $\phi (m)$ 互质的数，将其作为 $a$ 的指数，再对其取模便可求出另外的原根。

例如：我们知道 $m=9$ 时的最小原根为 $2$，$\phi (9)=6$，而 $\phi (6)=2$，由性质 1 可知它有 $2$ 个原根，在 $[1,6)$ 之中与 $6$ 互质的数有 $1$ 和 $5$
$$\begin{gathered} 2^1\mathrm{mod}9=2 \\ {2}^5\mathrm{mod}9=5 \end{gathered}$$
可知，模 $9$ 的原根有两个，分别是 $2$ 和 $5$。

十一. 模数意义下的乘法群

• 给定一个正整数 $n$，那么模 $n$ 意义下的乘法群是在模运算和乘法运算定义下的群。具体来说，在这个群中的任意两个数相乘再对 $n$ 取余后的数一定是这个群中的元素，这便是模 $n$ 意义下的乘法群，通常记作 ${\mathbb{Z}}_n^{\ast }$

例如，就 $n=12$ 来讲，模 $12$ 的乘法群 ${\mathbb{Z}}_{12}^{\ast }$ 为 { 1 , 5 , 7 , 11 } \{1,5,7,11\} {1,5,7,11}，
$$\begin{gathered} 5\times 7\mathrm{mod}12=11 \\ 5\times 11\mathrm{mod}12=7 \\ 7\times 11\mathrm{mod}12=5 \\ ⋮ \end{gathered}$$
可见，在这个群中的任意两个元素相乘再模 $12$，都是这个群中的元素。

• 群中的元素：模 $n$ 的乘法群中的元素一定与 $n$ 互素

  简单说明：这可以用裴蜀定理来说明，根据裴蜀定理 $\gcd (a,n)=1$ 时，方程 $ax+ny=1$ 一定有解，而这个"$1$"恰好是这个群的单位元，这保证了构成群的基本条件。

• 单位元：易知在模数意义下的乘法群中的单位元就是 $1$。因为任何一个数乘以 $1$ 再模 $n$ 之后的结果一定是这个数本身。

• 逆元：该群中的每个元素都有逆元。例如上面 $n=12$ 的例子，每个元素的逆元都恰好是它们自身。

十二. 逆元及逆元的求解方法

• 逆元（inv）

①（模乘的）逆元：进一步讲一下逆元，逆元又叫数论倒数，和普通倒数不同，数论倒数一定是一个整数。
其定义为：对于正整数 $a$ 和 $p$，若有 $ax\equiv 1(\mathrm{mod}p)$，那么把这个同余方程中的 $x$ 的解叫做 $a$ 模 $p$ 的逆元。

② $a$ 存在模乘逆元的充要条件是 $a$ 与 $p$ 互质
简单说明：要想说明 $ax\equiv 1(\mathrm{mod}p)$ 有这么一个 $x$ ，可以进行一个简单的变形，因为是对 $ax$ 取模，相当于是把 $ax$ 减掉了 $k$ 个 $p$ 最终余下了 $1$，相当于可以写成 $ax-kp=1$。而根据裴蜀定理，方程 $ax+py=1$ 有解的充要条件时 $\gcd (a,p)=1$，由于参数无所谓正负，所以这和前面的 $ax-kp=1$ 时等价的，因此便说明了只有当 $a$ 和模数 $p$ 互质时 $a$ 才存在逆元。

• 逆元的求解方法

①费马小定理求解逆元：$a$ 存在乘法逆元的充要条件是 $a$ 与 $p$ 互质，当模数 $p$ 是素数时，由费马小定理：
$$a^{p-1}\equiv 1(\mathrm{mod}p)$$
提出一个 $a$ 出来，可以得到
$$a\cdot a^{p-2}\equiv 1(\mathrm{mod}p)$$
而这个式子就恰好满足了我们希望的形式，因此可以看出，$a$ 的逆元就是 $a^{p-2}$。

②扩展欧几里得算法求解逆元：我们都知道扩欧算法可以算出方程 $ax+py=\gcd (a,b)$ 的一组解（$a、p$ 为参数）。而我们又知道 $a$ 存在模乘逆元的充要条件是 $a$ 与 $p$ 互质，因此原方程等价于 $ax+py=1$。而刚刚我们说明 $a$ 存在模乘逆元的充要条件的时候提到过了，这个方程也就等价于
$$\begin{gathered} ax-kp=1 \\ \Downarrow \\ ax\equiv 1(\mathrm{mod}p) \end{gathered}$$
于是我们便可以通过扩展欧几里得算法求得逆元。

——代码区——

1.分解质因数

写了一段比较基础的代码，基本思路就是我只要找到一个质因数就把它print下来：

#include <stdio.h>
void number(int n);

int main() {
    int n;
    printf("请输入一个整数：");
    scanf_s("%d", &n);
    number(n);
    return 0;
}

void number(int n) {
    int i;
    printf("%d = ", n);

    for (i = 2; i <= n; i++) {

        while (n % i == 0) {
            printf("%d", i);
            n /= i;

            if (n > 1) {
                printf(" * ");
            }
        }
    }
}

我就默认1不在这个讨论的范围内哈，如果非要考虑的话，加一个判断说n是否为1就行了。

2.计算一个数的欧拉函数

#include<stdio.h>
#include<math.h>
int eular(int n);

int main() {
    int n;
    printf("请输入一个正整数：");
    scanf_s("%d", &n);
    printf("该正整数的欧拉函数值为：%d", eular(n));
    return 0;
}

int eular(int n) {
    int result = n;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            result = result / i * (i - 1);
        }
        while (n % i == 0) {
            n /= i;
        }
    }
    if (n > 1) {
        result = result / n * (n - 1);
    }
    return result;
}

3.快速幂算法

#include <stdio.h>
long long fastpower(long long base, long long power);

int main() {
    int a, b;
    printf("请分别输入底数和指数：");
        scanf_s("%d %d", &a ,&b);
        long long result=fastpower(a,b);
        printf("%lld", result);
        return 0;
}

long long fastpower(long long base, long long power) {
    long long result = 1;
    while (power > 0) {
        if (power % 2 == 0) {
            power = power / 2;
            base = base * base % 1000;
        }
        else {
            power = power - 1;
            result = result * base % 1000;
            power = power / 2;
            base = base * base % 1000;
        }
    }
    return result;
}

4.扩展欧几里得算法

具体函数会在下面题中给到

5.求解同余方程 $ax\equiv 1(\mathrm{mod}b)$ 的最小正整数解

#include <stdio.h>
int extgcd(int a, int b, int* x, int* y);
int mod_inverse(int a, int b);

int main() {
    int a, b;
    printf("请输入a和b的值:");
    scanf_s("%d %d", &a, &b);
    int result = mod_inverse(a, b);
    if (result == -1) {
        printf("方程 %dx ≡ 1 (mod %d)无解。\n", a, b);
    }
    else {
        printf("最小正整数解是: %d\n", result);
    }
    return 0;
}

int extgcd(int a, int b, int* x, int* y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int x1, y1;
    int gcd = extgcd(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return gcd;
}

int mod_inverse(int a, int b) {
    int x, y;
    int gcd = extgcd(a, b, &x, &y);
    if (gcd != 1) {
        return -1;
    }
    else {
        return (x % b + b) % b;
    }
}

谢谢你能看到这里，你一定是个数学巨佬！