让我们从整除开始，这样对吧

定义：

设 $a,b\in Z,a \neq 0$。如果 $\exists q \in Z$，使得 $b=aq$ ，那么就说 $b$ 可被 $a$ 整除，记作 $a \mid b$ ，且称 $b$ 是 $a$ 的倍数， $a$ 是 $b$ 的约数（因数）。

$b$ 不被 $a$ 整除记作 $a \nmid b$ 。

性质：

• $a \mid b \Longleftrightarrow -a \mid b \Longleftrightarrow a \mid -b \Longleftrightarrow |a| \mid |b|$
• $a \mid b \space \wedge b \mid c \Longrightarrow a \mid c$
• $a \mid b \space \wedge a \mid c \Longleftrightarrow \forall x,y \in Z ,a \mid (xb+yc)$
• $a \mid b \wedge b \mid a \Longrightarrow b = \pm a$
• 设 $m \neq 0$ ，那么 $a \mid b \Longleftrightarrow ma \mid mb$
• 设 $b \neq 0$ ，那么 $a \mid b \Longleftrightarrow |a| \le |b|$
• 设 $a \neq b,b = qa + c$ ，那么 $a \mid b \Longleftrightarrow a \mid c$

0 是所有非零整数的倍数。对于任意非零整数，其约数只有有限个。

显然约数（显然因数） ： 对于整数 $b \neq 0$，$\pm 1,\pm b$ 是 $b$ 的显然约数，当 $b = \pm 1$ 时， $b$ 只有两个显然约数。

对于整数 $b \neq 0$ ,$b$ 的其他约数称为真约数（真因数、非显然约数、非显然因数）。

约数的性质 ：

• 设整数 $b \neq 0$ .当 $d$ 遍历 $b$ 的全体约数的时候，$\frac{b}{d}$ 也遍历 $b$ 的全体约数。
• 设整数 $b > 0$，则当$d$ 遍历 $b$ 的全体约数的时候，$\frac{b}{d}$ 也遍历 $b$ 的全体正约数。

gcd与lcm

最大公约数（gcd）

Greatest Common Divisor (gcd)

一组数的公约数就是指同时是这组数中每一个数的约数的数. $\pm 1$ 是任意一组整数的公约数.

最大公约数就是最大的公约数.

定义 $\gcd(0,0) = 0$

性质 ：

• $\gcd(a,b) = \gcd(a,a-b) = \gcd(b,a-b)$(更相减损)
• $\gcd(2a,2b) = 2\gcd(a,b)$

下一个例题似乎不很简单（实际不然），所以有了这题：P6068 『MdOI R1』GCD? GCD!

题解枚举一手 $n$ 的因数作为 $\gcd$，如果 $n$ 是 $\gcd$ 的不小于 $6$ 倍则合法，与答案取 max

例题是UVA11426(经典七倍经验题)

题解那就推一下这个例题的式子罢 ：

$$\begin{split} \sum_{i=1}^n \sum_{j = i+1}^n &= \sum_{j = 2}^n \sum_{i = 1}^{j-1}\gcd(i,j)\\ &= \sum_{d=1}^n d \times \sum_{j=2}^n \sum_{i = 1}^{j-1}[\gcd(i,j) = d] \\ &= \sum_{d=1}^n d \times \sum_{j=2}^{\lfloor \frac{n}{d} \rfloor} \sum_{i=1}^{j-1}[i \bot j]\\ &= \sum_{d=1}^n d \times \sum_{j=2}^{\lfloor \frac{n}{d} \rfloor}\varphi(j)\\ \end{split}$$

到这里第一步已经成功了，都是经典操作也没什么难度。考虑进一步优化： 设 $S(x) = \sum_{j=2}^x \varphi(j) ,f(x) = \sum_{j = 1}^x j$.

显然原式变成 ：

$$\sum_{d=1}^n d \times S({\lfloor \frac{n}{d} \rfloor})$$

因为 $\lfloor \frac{n}{d} \rfloor$ 被重复计算多次，显然考虑数论分块。

于是原式化为 ：

$$\sum(f(r) - f(l-1)) \times S(\lfloor \frac{n}{l} \rfloor)$$

预处理 $f(x),S(x)$ 的值，最终对于 $T$ 次询问总的时间复杂度是 $O(n + T \sqrt{n} )$ ,可以通过本题。

同余

对于两整数 $a,b$ ，若 $a \space mod \space p = b \space mod \space p$ ,则称 $a$ 与 $b$ 在模 $p$ 意义下同余

用符号表示就是熟悉的 $a \equiv b \space(\space mod \space p \space )$

性质

对称性 ： $a \equiv b \space(\space mod \space p) \Longrightarrow b \equiv a \space(\space mod \space p \space )$ 可乘性 ： $a \equiv b \space(\space mod \space p) , c \equiv d \space(\space mod \space p \space ) \Longrightarrow ac \equiv bd \space(\space mod \space p \space )$ 自反律 ： $a \equiv a$ 传递性 ： $a \equiv b , b \equiv c \Rightarrow a\equiv c$ 分配律 ： $(a \bmod m)d = ad \bmod md$

模意义下的运算规则

将同余元素相加减，仍保持同余关系 ：

$$a \equiv b ,c \equiv d \Longrightarrow a+c \equiv b+d \; (\bmod m)$$ $$a \equiv b ,c \equiv d \Longrightarrow a-c \equiv b-d \; (\bmod m)$$

（当模数是常数时，我们只需要对它说明一次来建立前后关系，像上式那样）

乘法同样有效，但处理的对象需要是整数 ：

$$a \equiv b ,c \equiv d \Longrightarrow ac \equiv bd \; (\bmod m) ,\; b,c \in Z$$

证明 ： $ac - bd = (a-b)c + b(c-d)$

反复利用这个乘法性质，我们就可以取幂 ：

$$a \equiv b \Longrightarrow a^n \equiv b^n \; (\bmod m),\; a,b \in Z,n \in N$$

例如 $2 \equiv -1 \;(\bmod 3 )$ ，于是 $2^n-1$ 是 $3$ 的倍数，当且仅当 $n$ 为偶数。

这样大多数代数运算都可以对同余方程使用，但是显然除法不行 ：

对于 $ad \equiv bd \; (\bmod m)$ ，我们永远不能断言 $a \equiv b$ ，例如 $3 \times 2 \equiv 5 \times 2 \; (\bmod 4)$ ，但是 $3 \not \equiv 5$

但是对于 $d \bot m$ 时，消元的做法是成立的 ：

$$ad \equiv bd \Leftrightarrow a \equiv b \;(\bmod m) ,a,b,d,m \in Z,\; d \bot m$$

我们只需要找到 $d$ 在模 $m$ 意义下的逆元 $d'$ ，对同余式两边同乘 $d'$ 即可。

另一种对同余式做除法的方法是在对式中的数做除法的同时对模数做除法，就像这样 ：

$$ad \equiv bd \; (\bmod md) \Leftrightarrow a \equiv b \;(\bmod m) , \; d \neq 0$$

由分配律可以证明。

我们将以上两种形式的同余式的除法结合起来，可以得到一个一般法则，它尽可能小的改变模数 ：

$$ad \equiv bd \; (\bmod m) \Leftrightarrow a \equiv b \;(\bmod \frac{m}{\gcd(m,d)}) , \; a,b,d,m \in Z$$

证明 ： 设 $d',m'$ 满足 $dd'+ mm' = \gcd(m,d)$，由裴蜀定理可知一定有解，那么对同余式的两边同乘 $d'$ ，我们得到 ：

$$a\cdot \gcd(m,d) \equiv b\cdot \gcd(m,d) \; (\bmod m)$$

上式可以使用 $\gcd(m,d)$ 来除。

进一步观察我们改变模的想法 ： $a \equiv b \;(\bmod 100)$ ，那么必定有 $a \equiv b \;(\bmod 10)$，即此式对任何 $100$ 的因数都成立，因为说 $a-b$ 是 $100$ 的倍数，要比说它是 $10$ 的倍数更强一些，一般来说 ：

$$a \equiv b \;(\bmod md) \Rightarrow a \equiv b \;(\bmod m) ,\; d \in Z$$

因为 $md$ 的任何倍数也是 $m$ 的倍数。

于是我们能否从两个小模数推出一个大模数呢？可以 ：

$$a \equiv b \;(\bmod m) , a \equiv b \;(\bmod n) \Rightarrow a \equiv b \;(\bmod \text{lcm}(m,n)) ,\; m,n \in N_+$$

如果 $a-b$ 是 $m,n$ 的公倍数，那么它就一定是 $\text{lcm}(m,n)$ 的倍数，这一点可以由唯一分解原理得出。

而当 $m \bot n$ 时，$\text{lcm}(m,n) = mn$ ,上式也可以变成等价的形式 ：

$$a \equiv b \;(\bmod mn) \Leftrightarrow a \equiv b \;(\bmod m) , a \equiv b \;(\bmod n), \; m \bot n$$

这是中国剩余定理的一个特例。

我们对于上式的模数 $m,n$ 分解为互素的因子，直到每个不同的素数都被单独分离出来，如果 $m$ 的素因子分解式是 $\prod_pp^{m_p}$ ，我们就有 ：

$$a \equiv b \;(\bmod m) \Leftrightarrow a \equiv b \;(\bmod p^{m_p})$$

上式对所有 $p$ 成立。

以素数幂为模的同余式是所有以整数为模的同余式的基础。

觉得不放例题不合适，所以放一道：P1154 奶牛分厩

发现不成立的情况是 ：

$$S_1 \equiv S_2 \; (\bmod K)$$

此时容易得出，对于所有满足这个条件的$K$，有 $K \mid |S_1 - S_2|$，于是 $|S_1 - S_2|$ 的因子都是不合法解，最后枚举每个解判断是否合法。

这样做的理论复杂度或许能过，但是实际上不容易实现，更容易实现的写法是标记每个 $|S_1 - S_2|$，然后枚举解，判断是否有不合法倍数。这样做的复杂度有经典结论是 $S \ln S$，其中 $S$ 为值域，最大为 $1e6$，预处理差值的复杂度是 $O(n^2)$ 的，所以能过。

剩余系

所谓“剩余系”，就是指对于某一个特定的正整数 $n$，一个整数集中的数模 $n$ 所得的余数域。一剩余系

如果一个剩余系中包含了这个正整数所有可能的余数（般地，对于任意正整数 $n$ ，有 $n$ 个余数：$0,1,2,\dots,n-1$），那么就被称为是模n的一个完全剩余系。（简称完系）

性质 ：

1. 对于 $n$ 个整数，其构成 $n$ 的完系等价于其关于模 $n$ 两两不同余。
2. 若 $a_i (1 \le i \le n)$ 构成模 $n$ 的完系 ，$k,m \in Z,(m,n) = 1$ ，则 $k + ma_i (1 \le i \le n)$ 也构成模 $n$ 的完系。

简化剩余系

简化剩余系也称既约剩余系或缩系，是模 $m$ 的完全剩余系中与 $m$ 互素的数构成的子集。如果模 $m$ 的一个剩余类里所有数都与 $m$ 互素，就把它叫做与模 $m$ 互素的剩余类。在与模 $m$ 互素的全体剩余类中，从每一个类中各任取一个数作为代表组成的集合，叫做模 $m$ 的一个简化剩余系。

例如模 $5$ 的一个简化剩余系是 $1,2,3,4$ ，模 $10$ 的一个简化剩余系是 $1,3,7,9$。

不难发现，简化剩余系的大小为 $\varphi(m)$。

应用

应用较少，主要在定理的证明和表达中使用。

求解线性同余方程

线性同余方程是指形如 $ax \equiv b \space(\space mod \space p)$ 的方程，因为未知数的指数为 $1$ ，所以我们称之为一次同余方程或线性同余方程。

解线性同余方程的方法是 ： 把同余式 $a x\equiv b \space(\space mod \space p \space )$ 转化成 $ax + kp = b$ ，然后使用exgcd求解 对于同余式 $ax \equiv 1 \space(\space mod \space p \space )$ 的一个解是 $a$ 在模 $p$ 意义下的逆元。逆元稍后解释。

对于线性同余方程组的解法则需用到 中国剩余定理(CRT) 和 扩展中国剩余定理(exCRT) ，详见数论算法、定理和常用变换

板子题是P1082

非常简单，直接放下代码罢

#include<bits/stdc++.h>
using namespace std;
long long a,b,x,y;
void exgcd(long long a,long long b){
    if(b == 0)  {x = 1,y = 0;return;}
    exgcd (b,a % b);
    long long m = x;
    x = y;
    y = m - (a / b) * y;
}
int main()
{
    cin>>a>>b;
    exgcd(a,b);
    x = (x % b + b) % b;
    cout<<x;
    return 0;
}

（早期马蜂，看起来可能挺离谱的）

求解高次同余方程

求解高次同余方程有 $a^x\equiv b \space(\space mod \space p)$ 和 $x^a\equiv b \space(\space mod \space p\space )$ 两类问题。

前者可以使用 Baby Step,Giant Step (BSGS)算法解决，后者也可以使用 BSGS 求解，我称之为 “BSGS求解高次剩余”

所以详见数论算法、定理和常用变换

二次剩余

但是对于

$$x^2 \equiv N (\bmod p)$$

其中保证 $p$ 为奇素数时，我们有更容易的解法 ： Cipolla 算法

打算放在 数论算法、定理和常用变换 中，这里再次抛个link（

快速幂

作为逆元的前置知识排到这里罢。

快速幂就是对幂运算的二进制优化，使得计算 $x^k$ 的时间复杂度由 $O(k)$ 降为 $O(log \space k)$

具体做法就是对指数进行二进制拆分，把幂次转换成二进制正次幂乘积的形式，举一个zh_dou博客里的例子就是 ：

$$105_{(10)} = 1101001_{(2)}$$

所以

$$x^{105} = x^{2^6+2^5+2^3+2^0} = x^{2^6} x^{2^5} x^{2^3} x^{2^0}$$

代码实现非常短，应该都有肌肉记忆了（:

int ksm(int a,int b,int p)
{
    int ans = 1;
    for(;b;b>>=1,a = a * a % p) if(b & 1) ans = ans * a % p;
    return ans;
}

补充一个 $O(\sqrt{n})$ 预处理 $O(1)$ 查询的快速幂写法。

这种做法实际上和普通快速幂本质不同，它体现着一种根号分治的思想，且局限性很大，只能用于底数和模数都相同的场合。

具体而言，对于一个数 $b$ ，它可以被表示为 $\lfloor \frac{b}{s} \rfloor s \times b \bmod s$，分别考虑乘号左右的两部分，容易发现当 $s$ 取到 $\sqrt{p}$ 的时候，都只有 $\sqrt{p}$ 级别的取值个数。

于是可以通过预处处理出这两部分，查询时直接求乘积即可。

乘法逆元

若$a * x \equiv 1 (\mod b)$ 则x是a在模b意义下的逆元 求解方法有四种：

一、费马小定理 ：

若$p \in prime,a\in N^*,a \perp p$，则有

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

所以显然$a^{p-2}$即为所求。代码不放了，ksm板子应该都会

二、扩展欧几里得（exgcd）：

这个方法在单次查找中表现优异，要求少速度快。只要求 $a \perp p$ ，不要求 $p$ 是质数。（扩欧不鸽的话会写在数论算法、定理和常用变换中）。代码也很好写:

void exgcd(int a,int b,int &x,int &y)
{
    if(!b) {
        x = 1,y = 0;
        return;
    }
    exgcd(b,a%b,y,x);
    y -= a/b * x;
}
exgcd(a,p,x,y);
x = (x % p + p) % p;

这样求得的 $x$ 就是要求的逆元。

三、线性求逆元 ：

适用于求多个连续数字的逆元，经典例题是 P3811 先放下代码 ：

inv[1] = 1;
for(int i = 2;i<=n;i++)
    inv[i] = (p - p/i) * inv[p % i] % p;

然后我们就有了 $1~n$ 范围内的数模 $p$ 的逆元。 我们已知 $1^{-1} \equiv 1 (mod \space p)$ 然后设 $p = k * i + r,(i < r < i < p) ,(1<r<i<p)$ ，即 $k$ 是 $p/i$ 的商， $r$ 是余数。 再将这个式子放到模 $p$ 意义下就会得到 ：

$$k \times i + r \equiv 0 \space ( \space mod \space p \space )$$

然后乘上 $i^{-1}r^{-1}$ 就会得到 ：

$$k \times r^{-1} + i^{-1} \equiv 0 \space ( \space mod \space p \space )$$ $$i^{-1} \equiv -k \times r^{-1} \space ( \space mod \space p \space )$$ $$i^{-1} \equiv - \lfloor \frac{p}{i} \rfloor \times ( \space p \space mod \space i \space )^{-1} \space ( \space mod \space p \space )$$

于是我们就可以从前面推出当前的逆元了。

线性求阶乘逆元

求 $1 \sim n$ 阶乘及逆元，多用于预处理规模不大的组合数时。

显然可以得到如下递推关系 ：

$$facinv[i+1] = \frac{1}{(i+1)!}$$ $$facinv[i+1] * (i + 1) = \frac{1}{i!} = facinv[i]$$

所以我们可以先求出 $n!$ 的逆元，然后逆推得到这 $n$ 个数的阶乘逆元。

递推式就是 ：

$$facinv[i + 1] * (i + 1) = facinv[i]$$

然后我们就有了这 $n$ 个数的阶乘和阶乘的逆元了。

由以上内容也可以在 $O(1)$ 时间内得到这 $n$ 个数中的一个数的逆元 ：

$$fac[i-1] * facinv[i] = inv[i]$$

线性求任意 $n$ 个数的逆元

上面的情形似乎只适用于阶乘的情况，然而我们利用几乎完全相同的思想可以得到更加具有普适性的方法 ：

求给定数组 $a_i$ 中每一个元素的逆元：

首先计算这 $n$ 个数的前缀积数组 $S$ ,然后对 $S_n$ 进行一个单独的求逆元，得到逆元为 $Sv_n$ ，也就是这 $n$ 个数逆元的乘积。

然后进行一个倒推，每次用 $Sv_i$乘上 $a_i$ ，就可以得到 $Sv_{i-1}$ （因为 $i$ 和 $i^{-1}$ 消掉了）

然后我们就得到了逆元的前缀积数组 $Sv$

对于每次询问，我们只需要用 $S_{i-1} * Sv_i$ 就可以得到 $a_i$ 的逆元

阶与原根

阶

由欧拉定理可知，对于 $a \in Z,m \in N_+$ ，若有 $(a,m) = 1$ ，则 $a^{\varphi(m)}\equiv 1 \;(\bmod m)$ 。 因此满足同余式 $a^n \equiv 1$ 的最小正整数 $n$ 存在，这个 $n$ 称作 $a$ 模 $m$ 的阶，记作 $\delta_m(a)$ 。

注 ： 在抽象代数中，这里的“阶”就是模 $m$ 缩剩余系关于乘法形成的群中，元素 $a$ 的阶。记号 $\delta$ 表示阶也只用于这个特殊的群。 下面的诸多性质可以直接扩展到抽象代数中阶的性质。 另外还有“半阶”的概念，在数论中会出现 $\delta^-$ 记号，表示同余式 $a^x \equiv 1 \;(\bmod m)$ 的最小正整数解。半阶不是群论中的概念。阶一定存在，半阶不一定存在。

阶的性质

性质1： $a,a^2,\cdots,a^{\delta_m(a)}$ 模 $m$ 两两不同余。

证明 ： 使用反证法，设存在 $i \neq j$ 使得 $a^i \equiv a^j \;(\bmod m)$ 则有 $a^{ |i-j| } \equiv 1$ 。 但是显然 ： $0 < |i-j| < \delta_m(a)$ ，与阶的最小性矛盾，原命题成立。

性质2： 若 $a^n \equiv 1 \;(\bmod m)$ ，则 $\delta_m(a) \mid n$

对 $n$ 除以 $\delta_m(a)$ 作带余除法，以 $r$ 为余数，易证 $r > 0$ 的情况与阶的最小性矛盾，于是 $r = 0$，即 $\delta(a) \mid m$

由此还可以推出 ：

若 $a^p \equiv a^q \;(\bmod m)$ ，则有 $p \equiv q \;(\bmod \delta_m(a))$ 。

性质3 ： 设 $m \in N_+,a,b \in Z, \gcd(a,m) = \gcd(b,m) = 1$ ，则 ：

$$\delta_m(ab) = \delta_m(a) \delta_m(b)$$

的充要条件是 ：

$$\gcd(\delta_m(a),\delta_m(b)) = 1$$

证明 ：

必要性 ：

由 $a^{\delta_m(a)} \equiv 1 \;(\bmod m)$ 以及 $b^{\delta_m(b)} \equiv 1 \;(\bmod m)$，可知 ：

$$(ab)^{\text{lcm}(\delta_m(a),\delta_m(b))} \equiv 1 \;(\bmod m)$$

由阶的性质有 ：

$$\delta_m(ab) \mid \text{lcm}(\delta_m(a),\delta_m(b))$$

又由于

$$\delta_m(ab) = \delta_m(a) \delta_m(b)$$

显然有 ：

$$\delta_m(a) \delta_m(b) \mid \text{lcm}(\delta_m(a),\delta_m(b)) = \frac{\delta_m(a) \delta_m(b)}{\gcd(\delta_m(a),\delta_m(b))}$$

即 ：

$$\gcd(\delta_m(a),\delta_m(b)) = 1$$

充分性 ：

由 $\gcd(\delta_m(a),\delta_m(b)) = 1$ 可知

$$1 \equiv (ab)^{\delta_m(ab) \delta_m(b)} \equiv a^{\delta_m(ab) \delta_m(b)}$$

故 $\delta_m(a) \mid \delta_m(ab) \delta_m(b)$ ，结合 $\gcd(\delta_m(a),\delta_m(b)) = 1$ 即得 ：

$$\delta_m(a) \mid \delta_m(ab)$$

由于 $a,b$ 显然满足轮换对称，那么同理可得

$$\delta_m(b) \mid \delta_m(ab)$$

所以 ：

$$\delta_m(a) \delta_m(b) \mid \delta_m(ab)$$

另一方面，我们有 ：

$$(ab)^{\delta_m(a) \delta_m(b)} \equiv (a^{\delta_m(a)})^{\delta_m(b)} \times (b^{\delta_m(b)})^{\delta_m(a)} \equiv 1$$

故

$$\delta_m(ab) \mid \delta_m(a) \delta_m(b)$$

综合以上两点得到 :

$$\delta_m(ab) = \delta_m(a) \delta_m(b)$$

于是充分性和必要性都得证。

性质4 ： 设 $k \in N ,m \in N_+,a \in Z,(a,m) = 1$ ，则 ：

$$\delta_m(a^k) = \frac{\delta_m(a)}{\gcd(\delta_m(a),k)}$$

证明 ：

$$\begin{split} &a ^ {k \delta_m(a^k)}= (a ^ k) ^{\delta_m(a^k)} \equiv 1 \;(\bmod m) \\ &\Rightarrow \delta_m(a) \mid k \delta_m(a^k)\\ &\Rightarrow\frac{\delta_m(a)}{\gcd(\delta_m(a),k)} \mid \delta_m(a^k) \end{split}$$

另一方面，由 $a^{\delta_m(a)} \equiv 1$ 可知 ：

$$(a^k)^{\frac{\delta_m(a)}{\gcd(\delta_m(a),k)}} = (a^{\delta_m(a)})^{\frac{k}{\gcd(\delta_m(a),k)}} \equiv 1$$

故 ：

$$\delta_m(a^k) \mid \frac{\delta_m(a)}{\gcd(\delta_m(a),k)}$$

综合以上两点，得 ：

$$\delta_m(a^k) = \frac{\delta_m(a)}{\gcd(\delta_m(a),k)}$$

证毕。

原根

设 $m \in N_+,a \in Z$ 。若 $\gcd(a,m) = 1$ ，且 $\delta_m(a) = \varphi(m)$ 则称 $a$ 为模 $m$ 的原根。

注 ： 在抽象代数中，原根就是循环群的生成元。这个概念只在模 $m$ 缩剩余系关于乘法形成的群中有“原根”这个名字，在一般的循环群中都称作“生成元”。 并非每个模 $m$ 缩剩余系关于乘法形成的群都是循环群，存在原根就表明它同构于循环群，如果不存在原根就表明不同构。

原根判定定理

设 $m \ge 3 ,a \bot m$ ，则 $a$ 是模 $m$ 的原根的充要条件是 ： 对于 $\varphi(m)$ 的每个素因数 $p$ ，都有 $a^{\frac{\varphi(m)}{p}} \not \equiv 1 \; (\bmod m)$ 。

证明 ：

必要性显然（由阶的性质）。

用反证法证明充分性 ：

当对于 $\varphi(m)$ 的每个素因数 $p$ ，都有 $a^{\frac{\varphi(m)}{p}} \not \equiv 1 \; (\bmod m)$ 成立时，我们假设存在一个 $a$ 不为模 $m$ 的原根。

因为 $a$ 不是原根，则一定存在一个 $t < \varphi(m)$ 使得 $a^t\equiv 1$ <!-- (?) -->

由裴蜀定理得 ： 一定存在一组 $k,x$ 满足 $kt = x\varphi(m) + \gcd(t,\varphi(m))$

参考资料

oi-wiki

《具体数学-计算机科学基础（第二版）》

laffey's blog