《初等数论》教学中的启示及应用

Enlightenment and Applications in the Teaching of Elementary Number Theory

摘要: 初等数论是一门研究“数”的学科，是针对数学专业的本科生开设的一门课程。本文主要阐述了在初等数论的教学过程中得到的一些启示和应用，分别为以下三方面内容：一是利用同余的性质得到了任意整数b能被给定正整数a整除的等价条件；二是给出了求解任意同余式的方法；三是给出了指数的两种证明方法。

Abstract: Elementary Number Theory is a subject that studies “number” and is a course for undergraduates majoring in mathematics. This paper mainly expounds enlightenment and applications obtained in the teaching process of elementary number theory, which are as follows: First, the equivalent condition that any integer b can be evenly divided by a given positive integer a is obtained by using the property of congruence. Second, the method of solving any congruence formula is given. Third, two methods of proving the index are given.

1. 引言

初等数论是一门古老的学科，有着相当悠久的历史。它的主要研究内容是整数的性质及其应用。但是随着计算机和科学技术的发展，信息安全这一重大问题被提出。在这一背景下，数论为解决信息安全问题提供了一种核心技术——公开密钥，为信息技术的发展做出了巨大的贡献。此外，数论在密码学、算子理论、代数编码、最优设计、计算方法、组合代数及信息科学等诸多领域都有着极其重要的应用[1]-[4]。

在高等学校的教学中，这门课程的教学对象一般是数学专业的二、三年级的本科生，因此教材多数选用的都是闵嗣鹤、严士健主编的《初等数论》。这本教材的内容比较基础、通俗易懂，主要的教学内容包括整数的性质、不定方程的求解、同余的性质以及同余式的求解、原根及指标的性质及其应用、连分数的性质、代数数与超越数以及数论函数。作者所在高校也开设了初等数论这门课程，是针对数学与应用数学专业一年级的本科生开设的专业选修课，教材选用的也是闵嗣鹤、严士健主编的《初等数论》。作者已经连续两年承担初等数论这门课程的教学。在教学过程中，获得了一些有关初等数论教学的启示及应用。本文将详细阐述这些启示和应用。本文的结构如下：

在第二部分，首先列举同余的一些性质，然后在此基础上得到同余的一个应用，即给出任意整数能被给定正整数a整除的判定条件；

在第三部分，首先列举孙子定理、平方剩余及平方非剩余、原根和指标的性质，然后在此基础上给出求解一般同余式的方法；

在第四部分，首先给出指数的定义，然后给出指数的两种证明方法；

在第五部分，对本文进行总结。

2. 同余的应用

定义1 [5]给定正整数m。对任意的整数a，b，如果m去除a和b所得的余数相同，则称a和b对模m同余，记作$a\equiv b\left(\mathrm{mod}m\right)$ 。如果所得的余数不同，则称a和b对模m不同余，记作$a\ne b\left(\mathrm{mod}m\right)$ 。

定理1 [5]给定整数m。如果整数a和b都是m的倍数，则$a+b$ 和$a-b$ 也是m的倍数。

定理2 [5]给定正整数m。则对任意整数a，b来说，a和b对模m同余的充分必要条件是m能整除$a-b$ 。

定理3 [5]设$A_{{\alpha }_1{\alpha }_2\cdots {\alpha }_k}\equiv B_{{\alpha }_1{\alpha }_2\cdots {\alpha }_k}\left(\mathrm{mod}m\right)$ ，$x_i\equiv y_i\left(\mathrm{mod}m\right)$ ，$i=1,2,\cdots ,k$ 。则

${\displaystyle \sum _{{\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_k}{A}_{{\alpha }_1{\alpha }_2\cdots {\alpha }_k}}{x}_1^{{\alpha }_1}{x}_2^{{\alpha }_2}\cdots x_k^{{\alpha }_k}\equiv {\displaystyle \sum _{{\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_k}{B}_{{\alpha }_1{\alpha }_2\cdots {\alpha }_k}}{y}_1^{{\alpha }_1}{y}_2^{{\alpha }_2}\cdots y_k^{{\alpha }_k}\left(\mathrm{mod}m\right)$ 。

特别地，如果$a_i\equiv b_i\left(\mathrm{mod}m\right)$ ，$i=0,1,2,\cdots ,n$ ，则

$a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_0\equiv b_n{x}^n+b_{n-1}{x}^{n-1}+\cdots +b_0\left(\mathrm{mod}m\right)$ 。

应用定理1，定理2和定理3，我们能给出任意整数被给定正整数a整除的判定条件。

定理4 给定正整数a。如果存在正整数i使得${10}^i\equiv 1\left(\mathrm{mod}a\right)$ ，那么对任意整数b，b能被a整除的充分必要条件是$a|{\displaystyle \sum _{j=0}^n{b}_j}$ ，其中$b=b_n{\left({10}^i\right)}^n+b_{n-1}{\left({10}^i\right)}^{n-1}+\cdots +b_0$ ，$0\le b_j<{10}^i$ 。

如果存在正整数i使得${10}^i\equiv -1\left(\mathrm{mod}a\right)$ ，那么对任意整数b，b能被a整除的充分必要条件是$a|{\displaystyle \sum _{j=0}^n{\left(-1\right)}^j}{b}_j$ ，其中$b=b_n{\left({10}^i\right)}^n+b_{n-1}{\left({10}^i\right)}^{n-1}+\cdots +b_0$ ，$0\le b_j<{10}^i$ 。

证明：如果存在正整数i使得${10}^i\equiv 1\left(\mathrm{mod}a\right)$ ，则由定理3知

$b=b_n{\left({10}^i\right)}^n+b_{n-1}{\left({10}^i\right)}^{n-1}+\cdots +b_0\equiv b_n{1}^n+b_{n-1}{1}^{n-1}+\cdots +b_0={\displaystyle \sum _{j=0}^n{b}_j}\left(\mathrm{mod}a\right)$ ，

即$b\equiv {\displaystyle \sum _{j=0}^n{b}_j}\left(\mathrm{mod}a\right)$ 。由定理2可a知能整除$b-{\displaystyle \sum _{j=0}^n{b}_j}$ 。

若a能整除b，则由定理1知a就能整除$b-\left(b-{\displaystyle \sum _{j=0}^n{b}_j}\right)$ ，即a能整除${\displaystyle \sum _{j=0}^n{b}_j}$ 。

反之，若a能整除${\displaystyle \sum _{j=0}^n{b}_j}$ ，则由定理1知a就能整除$\left(b-{\displaystyle \sum _{j=0}^n{b}_j}\right)+{\displaystyle \sum _{j=0}^n{b}_j}$ ，即a能整除b。

因此，b能被a整除的充分必要条件是$a|{\displaystyle \sum _{j=0}^n{b}_j}$ 。

如果存在正整数i使得${10}^i\equiv -1\left(\mathrm{mod}a\right)$ ，则由定理3知

$b=b_n{\left({10}^i\right)}^n+b_{n-1}{\left({10}^i\right)}^{n-1}+\cdots +b_0\equiv b_n{\left(-1\right)}^n+b_{n-1}{\left(-1\right)}^{n-1}+\cdots +b_0={\displaystyle \sum _{j=0}^n{\left(-1\right)}^j{b}_j}\left(\mathrm{mod}a\right)$ ，

即$b\equiv {\displaystyle \sum _{j=0}^n{\left(-1\right)}^j{b}_j}\left(\mathrm{mod}a\right)$ 。由定理2可知a能整除$b-{\displaystyle \sum _{j=0}^n{\left(-1\right)}^j{b}_j}$ 。

若a能整除b，则由定理1知a就能整除$b-\left(b-{\displaystyle \sum _{j=0}^n{\left(-1\right)}^j{b}_j}\right)$ ，即a能整除${\displaystyle \sum _{j=0}^n{\left(-1\right)}^j{b}_j}$ 。

反之，若a能整除${\displaystyle \sum _{j=0}^n{\left(-1\right)}^j}{b}_j$ ，则由定理1知a就能整除$\left(b-{\displaystyle \sum _{j=0}^n{\left(-1\right)}^j{b}_j}\right)+{\displaystyle \sum _{j=0}^n{\left(-1\right)}^j{b}_j}$ ，即a能整除b。

因此，b能被a整除的充分必要条件是$a|{\displaystyle \sum _{j=0}^n{\left(-1\right)}^j{b}_j}$ 。

下面，我们将列举一些例题来阐述上述定理得应用。

例1 任意整数a能被11整除的充分必要条件是$11|{\displaystyle \sum _{i=0}^n{\left(-1\right)}^i{a}_i}$ ，其中$a=a_n{10}^n+a_{n-1}{10}^{n-1}+\cdots +a_0$ ，$0\le a_i<10$ 。

解：因为$10\equiv -1\left(\mathrm{mod}11\right)$ ，所以由定理4知a能被11整除的充分必要条件是$11|{\displaystyle \sum _{i=0}^n{\left(-1\right)}^i{a}_i}$ ，其中$a=a_n{10}^n+a_{n-1}{10}^{n-1}+\cdots +a_0$ ，$0\le a_i<10$ 。

若$a=54897635$ ，则$a=5\times {10}^7+4\times {10}^6+8\times {10}^5+9\times {10}^4+7\times {10}^3+6\times {10}^2+3\times 10+5$ ，所以${\displaystyle \sum _{i=0}^7{\left(-1\right)}^i{a}_i}={\left(-1\right)}^7\times 5+{\left(-1\right)}^6\times 4+{\left(-1\right)}^5\times 8+{\left(-1\right)}^4\times 9+{\left(-1\right)}^3\times 7+{\left(-1\right)}^2\times 6+\left(-1\right)\times 3+5=1$ 而11不能整除1，所以11不能整除54,897,635。

例2 任意整数a能被37整除的充分必要条件是$37|{\displaystyle \sum _{i=0}^n{a}_i}$ ，其中$a=a_n{1000}^n+a_{n-1}{1000}^{n-1}+\cdots +a_0$ ，$0\le a_i<1000$ 。

解：因为$1000\equiv 1\left(\mathrm{mod}37\right)$ ，所以由定理4知a能被37整除的充分必要条件是$37|{\displaystyle \sum _{i=0}^n{a}_i}$ ，其中$a=a_n{1000}^n+a_{n-1}{1000}^{n-1}+\cdots +a_0$ ，$0\le a_i<1000$ 。

若$a=54897635$ ，则$a=54\times {1000}^2+897\times 1000+635$ ，所以${\displaystyle \sum _{i=0}^2{a}_i}=54+897+635=1586$ ，而37不能整除1586，所以37不能整除54,897,635。

例3 任意整数a能被101整除的充分必要条件是$101|{\displaystyle \sum _{i=0}^n{\left(-1\right)}^i{a}_i}$ ，其中$a=a_n{100}^n+a_{n-1}{100}^{n-1}+\cdots +a_0$ ，$0\le a_i<100$ 。

解：因为$100\equiv -1\left(\mathrm{mod}101\right)$ ，所以由定理4知a能被101整除的充分必要条件是$101|{\displaystyle \sum _{i=0}^n{\left(-1\right)}^i{a}_i}$ ，其中$a=a_n{100}^n+a_{n-1}{100}^{n-1}+\cdots +a_0$ ，$0\le a_i<100$ 。

若$a=54897635$ ，则$a=54\times {100}^3+89\times {100}^2+76\times 100+35$ ，所以${\displaystyle \sum _{i=0}^3{\left(-1\right)}^i}{a}_i={\left(-1\right)}^3\times 54+{\left(-1\right)}^2\times 89+\left(-1\right)\times 76+35=-6$ ，而101不能整除−6，所以101不能整除54,897,635。

由上述几个例题可以看出，同余有着很重要的应用。事实上，同余在整个初等数论的教学过程中都具有非常重要的位置和作用。所以，在实际教学过程中，当讲解同余时，可以在讲解同余的概念和性质时适当穿插一些相关的应用，如上面列举的得到任意整数被给定正整数整除的条件，或者是利用同余的性质验算两个比较大的整数做乘法结果是否正确等。这样不仅能让学生了解同余的广泛应用，增加对知识的兴趣，也能缓解学生在长时间的理论学习中所带来的注意力不集中、分散的现象。

3. 一般同余式的求解

定义2 [5]设$f\left(x\right)=a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_0$ ，其中$a_i$ 是整数。给定正整数m。则$f\left(x\right)\equiv 0\left(\mathrm{mod}m\right)$ 叫做模m的同余式。如果$a_n\ne 0\left(\mathrm{mod}m\right)$ ，则该同余式的次数为n。

若a是使$f\left(a\right)\equiv 0\left(\mathrm{mod}m\right)$ 成立的一个整数，则$x\equiv a\left(\mathrm{mod}m\right)$ 叫做该同余式的一解。

定理5 [5]一次同余式

$ax\equiv b\left(\mathrm{mod}m\right)$ ，$a\ne 0\left(\mathrm{mod}m\right)$

有解的充分必要条件是a和m的最大公约数$\left(a,m\right)$ 能整除b。

由定理5可以看出，求解一次同余式$ax\equiv b\left(\mathrm{mod}m\right)$ ，也就相当于求解二元一次方程$ax-my=b$ ，找到满足条件的x，并将所有满足条件的x在模m的意义下分类。

定理6 [5] (孙子定理)设$m_1,m_2,\cdots ,m_k$ 是k个两两互素的正整数，$m=m_1{m}_2\cdots m_k$ ，$M_i=\frac{m}{m_i}$ ，$i=1,2,\cdots ,k$ ，则同余式组

$x\equiv b_1\left(\mathrm{mod}{m}_1\right),x\equiv b_2\left(\mathrm{mod}{m}_2\right),\cdots ,x\equiv b_k\left(\mathrm{mod}{m}_k\right)$

的解为

$x\equiv {M^{\prime }}_1{M}_1{b}_1+{M^{\prime }}_2{M}_2{b}_2+\cdots +{M^{\prime }}_k{M}_k{b}_k\left(\mathrm{mod}m\right)$ ，

其中${M^{\prime }}_i$ 满足${M^{\prime }}_i{M}_i\equiv 1\left(\mathrm{mod}{m}_i\right)$ ，$i=1,2,\cdots ,k$ 。

定理7 [5]设$m_1,m_2,\cdots ,m_k$ 是k个两两互素的正整数，$m=m_1{m}_2\cdots m_k$ 。则同余式

$f\left(x\right)\equiv 0\left(\mathrm{mod}m\right)$

与同余式组

$f\left(x\right)\equiv 0\left(\mathrm{mod}{m}_1\right),f\left(x\right)\equiv 0\left(\mathrm{mod}{m}_2\right),\cdots ,f\left(x\right)\equiv 0\left(\mathrm{mod}{m}_k\right)$

等价。

由定理6和定理7可知，对于一般的同余式$f\left(x\right)\equiv 0\left(\mathrm{mod}m\right)$ ，可以先将m进行标准分解，求出m的标准分解式$m=2^{\alpha }{p}_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$ ，其中$p_i\left(i=1,2,\cdots ,k\right)$ 是奇素数，然后再分别求出同余式$f\left(x\right)\equiv 0\left(\mathrm{mod}{2}^{\alpha }\right)$ 的解$x\equiv b_{0t_0}\left(\mathrm{mod}{2}^{\alpha }\right)$ ，其中$t_0=1,2,\cdots ,T_0$ 以及同余式$f\left(x\right)\equiv 0\left(\mathrm{mod}{p}_i^{{\alpha }_i}\right),\left(i=1,2,\cdots ,k\right)$ 的解$x\equiv b_{i{t}_i}\left(\mathrm{mod}{p}_i^{{\alpha }_i}\right)$ ，其中$t_i=1,2,\cdots ,T_i$ 。最后再求解同余式组

$x\equiv b_{0t_0}\left(\mathrm{mod}{2}^{\alpha }\right),x\equiv b_{1t_1}\left(\mathrm{mod}{p}_1^{{\alpha }_1}\right),x\equiv b_{2t_2}\left(\mathrm{mod}{p}_2^{{\alpha }_2}\right),\cdots ,x\equiv b_{k{t}_k}\left(\mathrm{mod}{p}_k^{{\alpha }_k}\right)$ 。

对于同余式$f\left(x\right)\equiv 0\left(\mathrm{mod}{p}^{\alpha }\right)$ ，其中p是素数，有如下的定理：

定理8 [5]如果$x\equiv x_1\left(\mathrm{mod}p\right)$ 是同余式$f\left(x\right)\equiv 0\left(\mathrm{mod}p\right)$ 的解并且满足p不能整除$f^{\prime }\left(x_1\right)$ ，则由$x_1$ 可以诱导出$f\left(x\right)\equiv 0\left(\mathrm{mod}{p}^{\alpha }\right)$ 的一解，即存在整数$x_{\alpha }$ 使得$x\equiv x_{\alpha }\left(\mathrm{mod}{p}^{\alpha }\right)$ 是$f\left(x\right)\equiv 0\left(\mathrm{mod}{p}^{\alpha }\right)$ 的一解，其中$x_{\alpha }\equiv x_1\left(\mathrm{mod}p\right)$ 。

由定理8可知，要求解同余式$f\left(x\right)\equiv 0\left(\mathrm{mod}{p}^{\alpha }\right)$ ，可以先求解出同余式$f\left(x\right)\equiv 0\left(\mathrm{mod}p\right)$ 的全部的解$x\equiv x_1\left(\mathrm{mod}p\right)$ ，$x\equiv x_2\left(\mathrm{mod}p\right)$ ，$\cdots$ ，$x\equiv x_k\left(\mathrm{mod}p\right)$ 。如果$x_i$ 满足p不能整除$f^{\prime }\left(x_i\right)$ ，则将$x=x_i+p{t}_1$ 代入到同余式$f\left(x\right)\equiv 0\left(\mathrm{mod}{p}^2\right)$ 中，并在点$x_i$ 处进行泰勒展开，于是有

$f\left(x_i\right)+p{t}_1{f}^{\prime }\left(x_i\right)\equiv 0\left(\mathrm{mod}{p}^2\right)$ ，

即

$f^{\prime }\left(x_i\right)t_1\equiv -\frac{f\left(x_i\right)}{p}\left(\mathrm{mod}p\right)$ 。

又因为p不能整除$f^{\prime }\left(x_i\right)$ ，所以$\left(p,f^{\prime }\left(x_i\right)\right)=1$ ，所以同余式$f^{\prime }\left(x_i\right)t_1\equiv -\frac{f\left(x_i\right)}{p}\left(\mathrm{mod}p\right)$ 有一解$t_1\equiv {t^{\prime }}_1\left(\mathrm{mod}p\right)$ ，即$t_1={t^{\prime }}_1+p{t}_2$ 。代入到$x=x_i+p{t}_1$ 有$x=x_i+p\left({t^{\prime }}_1+p{t}_2\right)=x_2^i+p^2{t}_2$ ，其中$x_2^i=x_i+p{t^{\prime }}_1\equiv x_i\left(\mathrm{mod}p\right)$ 且满足$f\left(x_2^i\right)\equiv 0\left(\mathrm{mod}{p}^2\right)$ 。所以$x\equiv x_2^i\left(\mathrm{mod}{p}^2\right)$ 是同余式$f\left(x\right)\equiv 0\left(\mathrm{mod}{p}^2\right)$ 的解。如此迭代下去，最终可以求出同余式$f\left(x\right)\equiv 0\left(\mathrm{mod}{p}^{\alpha }\right)$ 的解$x\equiv x_{\alpha }^i\left(\mathrm{mod}{p}^{\alpha }\right)$ 且$x_{\alpha }^i\equiv x_i\left(\mathrm{mod}p\right)$ 。

对于同余式$f\left(x\right)\equiv 0\left(\mathrm{mod}p\right)$ ，当$f\left(x\right)$ 是一般的多项式时，只能通过试根的方法求出它的全部解，即依次将$0,1,2,\cdots ,p-1$ 代入到$f\left(x\right)\equiv 0\left(\mathrm{mod}p\right)$ 中判断哪些是解。

当$f\left(x\right)$ 是如下几种特殊的多项式时，可以通过更便捷的方法求出$f\left(x\right)\equiv 0\left(\mathrm{mod}p\right)$ 的解。

当$f\left(x\right)=x^2$ 且$p=2$ 时，对于同余式$x^2\equiv a\left(\mathrm{mod}{p}^{\alpha }\right)$ ，$\left(a,p\right)=1$ 有如下的定理。

定理9 [5]设$\alpha >1$ 。则同余式$x^2\equiv a\left(\mathrm{mod}{2}^{\alpha }\right)$ ，$\left(a,2\right)=1$ 有解的充分必要条件是当$\alpha =2$ 时，$a\equiv 1\left(\mathrm{mod}4\right)$ ；当$\alpha \ge 3$ 时，$a\equiv 1\left(\mathrm{mod}8\right)$ 。在有解的情况下，当$\alpha =2$ 时，解数是2；当$\alpha \ge 3$ 时，解数是4。

由定理9可以看出，对于同余式$x^2\equiv a\left(\mathrm{mod}{2}^{\alpha }\right)$ ，$\left(a,2\right)=1$ ，

当$\alpha =1$ 时，显然同余式$x^2\equiv a\left(\mathrm{mod}2\right)$ 的解只有$x\equiv 1\left(\mathrm{mod}2\right)$ ；

当$\alpha =2$ 且$a\equiv 1\left(\mathrm{mod}4\right)$ 时，显然同余式$x^2\equiv a\left(\mathrm{mod}{2}^2\right)$ 有两解$x\equiv 1\left(\mathrm{mod}4\right)$ ，$x\equiv 3\left(\mathrm{mod}4\right)$ ；

当$\alpha =3$ 且$a\equiv 1\left(\mathrm{mod}8\right)$ 时，显然同余式$x^2\equiv a\left(\mathrm{mod}{2}^3\right)$ 有四解$x\equiv 1\left(\mathrm{mod}8\right)$ ，$x\equiv 3\left(\mathrm{mod}8\right)$ ，$x\equiv 5\left(\mathrm{mod}8\right)$ ，$x\equiv 7\left(\mathrm{mod}8\right)$ ；

当$\alpha >3$ 且$a\equiv 1\left(\mathrm{mod}8\right)$ 时，由定理8可知，求解同余式$x^2\equiv a\left(\mathrm{mod}{2}^{\alpha }\right)$ ，需要通过一次次迭代求解。而$x^2\equiv a\left(\mathrm{mod}{2}^3\right)$ 的解已经求出，是全部的奇数，而全部奇数又可以表示成$\pm \left(1+4t\right)$ ，$t=0,\pm 1,\pm 2,\cdots$ 。所以可以将$\pm \left(1+4t_3\right)$ 代入到$x^2\equiv a\left(\mathrm{mod}{2}^4\right)$ 中，即${\left(1+4t_3\right)}^2\equiv a\left(\mathrm{mod}16\right)$ ，解得$t_3\equiv \frac{a-1}{8}\left(\mathrm{mod}2\right)$ ，即$t_3=\frac{a-1}{8}+2t_4$ ，令${t^{\prime }}_3=\frac{a-1}{8}$ ，则$t_3={t^{\prime }}_3+2t_4$ 。所以$x=\pm \left(1+4{t^{\prime }}_3+8t_4\right)$ ，令$x_4=1+4{t^{\prime }}_3$ ，则$x=\pm \left(x_4+8t_4\right)$ ，$t_4=0,\pm 1,\pm 2,\cdots$ 是同余式$x^2\equiv a\left(\mathrm{mod}{2}^4\right)$ 的解。如此迭代下去，最终可以求出同余式$x^2\equiv a\left(\mathrm{mod}{2}^{\alpha }\right)$ 的解。

当$f\left(x\right)=x^n$ ，$m=2$ 或4或$p^{\alpha }$ 或$2p^{\alpha }$ 且$\left(a,m\right)=1$ 时，对于同余式$x^n\equiv a\left(\mathrm{mod}m\right)$ 有如下的求解方法。为此，我们先回顾一些基本概念。

定义3 [2]设$m>1$ 且$\left(a,m\right)=1$ 。则使得同余式

$a^{\gamma }\equiv 1\left(\mathrm{mod}m\right)$

成立的最小正整数$\gamma$ 叫做a对模m的指数。

若a对模m的指数是$\phi \left(m\right)$ ，则a叫做模m的一个原根。

定理10 [5]模m的原根存在当且仅当$m=2$ 或4或$p^{\alpha }$ 或$2p^{\alpha }$ 。

定义4 [5]设g是模m的一个原根。对任意的整数a来说，若存在正整数$\gamma$ 使得

$a\equiv g^{\gamma }\left(\mathrm{mod}m\right)$

则称$\gamma$ 是以g为底的a对模m的一个指标。

定理11 [5]设g是模m的一个原根，a是一整数且$\left(a,m\right)=1$ ，$c=\phi \left(m\right)$ ，则存在$0\le {\gamma }^{\prime }<c$ 使得${\gamma }^{\prime }$ 是以g为底的a对模m的一个指标；且以g为底的a对模m的指标是满足$\gamma \equiv {\gamma }^{\prime }\left(\mathrm{mod}c\right)$ 的一切正整数$\gamma$ 。记以g为底的a对模m的所有指标模c的最小非负剩余为$in{d}_{g}a$ 或$inda$ 。

定理12 [5]设g是模m的一个原根，$c=\phi \left(m\right)$ ，a是一整数且$\left(a,m\right)=1$ ，n是正整数。记$d=\left(n,c\right)$ 。则同余式

$x^n\equiv a\left(\mathrm{mod}m\right)$

有解当且仅当$d|in{d}_{g}a$ ；并且在有解的情况下解数是d。

基于以上的准备知识，我们可以得到同余式$x^n\equiv a\left(\mathrm{mod}m\right)$ 的求解过程。

首先，找到模m的一个原根g；然后，构造出以g为底的模m的指标表。由定理12可知同余式$x^n\equiv a\left(\mathrm{mod}m\right)$ 与同余式n$in{d}_{g}x\equiv in{d}_{g}a\left(\mathrm{mod}c\right)$ 等价。所以当$d|in{d}_{g}a$ 时，可以先求解同余式n $in{d}_{g}x\equiv in{d}_{g}a\left(\mathrm{mod}c\right)$ ，求出它的解$in{d}_{g}x\equiv t_1\left(\mathrm{mod}c\right)$ ，$in{d}_{g}x\equiv t_2\left(\mathrm{mod}c\right)$ ，$in{d}_{g}x\equiv t_3\left(\mathrm{mod}c\right)$ ，……，$in{d}_{g}x\equiv t_s\left(\mathrm{mod}c\right)$ ，然后再由指标表查出对应的x的值，即为同余式$x^n\equiv a\left(\mathrm{mod}m\right)$ 的解。

下面，我们将列举一些例题来看一下同余式的具体求解。

例4 解同余式$31x^4+57x^3+96x+191\equiv 0\left(\mathrm{mod}225\right)$ 。

解：因为$225=3^2\times 5^2$ ，所以同余式$31x^4+57x^3+96x+191\equiv 0\left(\mathrm{mod}225\right)$ 与同余式组

$31x^4+57x^3+96x+191\equiv 0\left(\mathrm{mod}9\right)$ ，$31x^4+57x^3+96x+191\equiv 0\left(\mathrm{mod}25\right)$

等价。

记$f\left(x\right)=31x^4+57x^3+96x+191$ ，则$f^{\prime }\left(x\right)=124x^3+171x^2+96$ 。

先求解同余式$31x^4+57x^3+96x+191\equiv 0\left(\mathrm{mod}9\right)$ 。经试根发现同余式$31x^4+57x^3+96x+191\equiv 0\left(\mathrm{mod}3\right)$ 的解为$x_1\equiv 1\left(\mathrm{mod}3\right)$ ，$x_2\equiv 2\left(\mathrm{mod}3\right)$ 。经计算知$f^{\prime }\left(x_1\right)=391$ ，$f^{\prime }\left(x_2\right)=1772$ ，3不能整除$f^{\prime }\left(x_1\right)$ 和$f^{\prime }\left(x_2\right)$ 。

将$x=1+3t_1$ 代入到$31x^4+57x^3+96x+191\equiv 0\left(\mathrm{mod}9\right)$ 中并在$x=1$ 处泰勒展开有

$3t_1\times 391+375\equiv 0\left(\mathrm{mod}9\right)$ ，

即$391t_1+125\equiv 0\left(\mathrm{mod}3\right)$ 。又$391\equiv 1\left(\mathrm{mod}3\right)$ ，$125\equiv 2\left(\mathrm{mod}3\right)$ ，所以$t_1+2\equiv 0\left(\mathrm{mod}3\right)$ ，即$t_1\equiv 1\left(\mathrm{mod}3\right)$ 。所以$t_1=1+3t_2$ ，$t_2=0,\pm 1,\pm 2,\cdots$ 。所以$x=4+9t_2$ ，即$x\equiv 4\left(\mathrm{mod}9\right)$ 。

将$x=2+3t_1$ 代入到$31x^4+57x^3+96x+191\equiv 0\left(\mathrm{mod}9\right)$ 中并在$x=1$ 处泰勒展开有

$3t_1\times 1772+1335\equiv 0\left(\mathrm{mod}9\right)$ ，

即$1772t_1+445\equiv 0\left(\mathrm{mod}3\right)$ 。又$1772\equiv 2\left(\mathrm{mod}3\right)$ ，$445\equiv 1\left(\mathrm{mod}3\right)$ ，所以$2t_1+1\equiv 0\left(\mathrm{mod}3\right)$ ，即$t_1\equiv 1\left(\mathrm{mod}3\right)$ 。所以$t_1=1+3t_2$ ，$t_2=0,\pm 1,\pm 2,\cdots$ 。所以$x=5+9t_2$ ，即$x\equiv 5\left(\mathrm{mod}9\right)$ 。

因此，$31x^4+57x^3+96x+191\equiv 0\left(\mathrm{mod}9\right)$ 的解为$x\equiv 4\left(\mathrm{mod}9\right)$ ，$x\equiv 5\left(\mathrm{mod}9\right)$ 。

再求解同余式$31x^4+57x^3+96x+191\equiv 0\left(\mathrm{mod}25\right)$ 。经试根发现同余式$31x^4+57x^3+96x+191\equiv 0\left(\mathrm{mod}5\right)$ 的解为$x_1\equiv 1\left(\mathrm{mod}5\right)$ ，$x_2\equiv 2\left(\mathrm{mod}5\right)$ 。经计算知$f^{\prime }\left(x_1\right)=391$ ，$f^{\prime }\left(x_2\right)=1772$ ，5不能整除$f^{\prime }\left(x_1\right)$ 和$f^{\prime }\left(x_2\right)$ 。

将$x=1+5t_1$ 代入到$31x^4+57x^3+96x+191\equiv 0\left(\mathrm{mod}25\right)$ 中并在$x=1$ 处泰勒展开有

$5t_1\times 391+375\equiv 0\left(\mathrm{mod}25\right)$ ，

即$391t_1+75\equiv 0\left(\mathrm{mod}5\right)$ 。又$391\equiv 1\left(\mathrm{mod}5\right)$ ，$75\equiv 0\left(\mathrm{mod}5\right)$ ，所以$t_1\equiv 0\left(\mathrm{mod}5\right)$ 。所以$t_1=5t_2$ ，$t_2=0,\pm 1,\pm 2,\cdots$ 。所以$x=1+25t_2$ ，即$x\equiv 1\left(\mathrm{mod}25\right)$ 。

将$x=2+5t_1$ 代入到$31x^4+57x^3+96x+191\equiv 0\left(\mathrm{mod}9\right)$ 中并在$x=1$ 处泰勒展开有

$5t_1\times 1772+1335\equiv 0\left(\mathrm{mod}25\right)$ ，

即$1772t_1+267\equiv 0\left(\mathrm{mod}5\right)$ 。又$1772\equiv 2\left(\mathrm{mod}5\right)$ ，$267\equiv 2\left(\mathrm{mod}5\right)$ ，所以$2t_1+2\equiv 0\left(\mathrm{mod}5\right)$ ，即$t_1\equiv 4\left(\mathrm{mod}5\right)$ 。所以$t_1=4+5t_2$ ，$t_2=0,\pm 1,\pm 2,\cdots$ 。所以$x=22+25t_2$ ，即$x\equiv 22\left(\mathrm{mod}25\right)$ 。

因此，$31x^4+57x^3+96x+191\equiv 0\left(\mathrm{mod}25\right)$ 的解为$x\equiv 1\left(\mathrm{mod}25\right)$ ，$x\equiv 22\left(\mathrm{mod}25\right)$ 。

最后，求解同余式组

$x\equiv b_1\left(\mathrm{mod}9\right)$ ，$x\equiv b_2\left(\mathrm{mod}25\right)$ ，$b_1=4,5$ ，$b_2=1,22$ 。

可知$m_1=9$ ，$m_2=25$ ，$m=m_1{m}_2=225$ ，$M_1=\frac{m}{m_1}=25$ ，$M_2=\frac{m}{m_2}=9$ 。

求解一次同余式$M_1{M^{\prime }}_1\equiv 1\left(\mathrm{mod}9\right)$ ，即$25{M^{\prime }}_1\equiv 1\left(\mathrm{mod}9\right)$ ，解得${M^{\prime }}_1\equiv 4\left(\mathrm{mod}9\right)$ ，所以取${M^{\prime }}_1=4$ 。

求解一次同余式$M_2{M^{\prime }}_2\equiv 1\left(\mathrm{mod}25\right)$ ，即$9{M^{\prime }}_2\equiv 1\left(\mathrm{mod}25\right)$ ，解得${M^{\prime }}_2\equiv -11\left(\mathrm{mod}25\right)$ ，所以取${M^{\prime }}_2=14$ 。

由孙子定理知该同余式组的解为$x\equiv M_1{M^{\prime }}_1{b}_1+M_2{M^{\prime }}_2{b}_2\equiv 100b_1+126b_2\left(\mathrm{mod}225\right)$ 。分别代入$b_1$ 和$b_2$ 的取值可知同余式$31x^4+57x^3+96x+191\equiv 0\left(\mathrm{mod}225\right)$ 的解为$x\equiv 22\left(\mathrm{mod}225\right)$ ，$x\equiv 76\left(\mathrm{mod}225\right)$ ，$x\equiv 122\left(\mathrm{mod}225\right)$ ，$x\equiv 176\left(\mathrm{mod}225\right)$ 。

例5 解同余式$x^2\equiv 41\left(\mathrm{mod}64\right)$ 。

解：因为$41\equiv 1\left(\mathrm{mod}8\right)$ ，所以该同余式有解。

将$x=\pm \left(1+4t_3\right)$ 代入到$x^2\equiv 41\left(\mathrm{mod}16\right)$ 中有${\left(1+4t_3\right)}^2\equiv 41\left(\mathrm{mod}16\right)$ ，即$8t_3\equiv 40\left(\mathrm{mod}16\right)$ ，所以$t_3\equiv 5\equiv 1\left(\mathrm{mod}2\right)$ ，即$t_3=1+2t_4$ ，$t_4=0,\pm 1,\pm 2,\cdots$ 。所以$x=\pm \left(5+8t_4\right)$ 。

将$x=\pm \left(5+8t_4\right)$ 代入到$x^2\equiv 41\left(\mathrm{mod}32\right)$ 中有${\left(5+8t_4\right)}^2\equiv 41\left(\mathrm{mod}32\right)$ ，即$80t_4\equiv 16\left(\mathrm{mod}32\right)$ ，所以$5t_4\equiv 1\left(\mathrm{mod}2\right)$ ，即$t_4\equiv 1\left(\mathrm{mod}2\right)$ ，所以$t_4=1+2t_5$ ，$t_5=0,\pm 1,\pm 2,\cdots$ 。所以$x=\pm \left(13+16t_5\right)$ 。

将$x=\pm \left(13+16t_5\right)$ 代入到$x^2\equiv 41\left(\mathrm{mod}64\right)$ 中有${\left(13+16t_5\right)}^2\equiv 41\left(\mathrm{mod}64\right)$ ，即$416t_5\equiv -128\left(\mathrm{mod}64\right)$ ，所以$13t_5\equiv -4\left(\mathrm{mod}2\right)$ ，即$t_5\equiv 0\left(\mathrm{mod}2\right)$ ，所以$t_5=2t_6$ ，$t_6=0,\pm 1,\pm 2,\cdots$ 。所以$x=\pm \left(13+32t_6\right)$ 。

因此，$x^2\equiv 41\left(\mathrm{mod}64\right)$ 的解为$x\equiv 13\left(\mathrm{mod}64\right)$ ，$x\equiv 19\left(\mathrm{mod}64\right)$ ，$x\equiv 45\left(\mathrm{mod}64\right)$ ，$x\equiv 51\left(\mathrm{mod}64\right)$ 。

例6 解同余式$x^{15}\equiv 14\left(\mathrm{mod}41\right)$ 。

解：已知6是模41的一个原根，且有如下的指标表：

	0	1	2	3	4	5	6	7	8	9
0		0	26	15	12	22	1	39	38	30
1	8	3	27	31	25	37	24	33	16	9

续表

2	34	14	29	36	13	4	17	5	11	7
3	23	28	10	18	19	21	2	32	35	6
4	20

	0	1	2	3	4	5	6	7	8	9
0	1	6	36	11	25	27	39	29	10	19
1	32	28	4	24	21	3	18	26	33	34
2	40	35	5	30	16	14	2	12	31	22
3	9	13	37	17	20	38	23	15	8	7

因为$d=\left(n,c\right)=\left(15,40\right)=5$ ，而$in{d}_{6}14=25$ ，$5|25$ ，所以该同余式有解。同余式$x^{15}\equiv 14\left(\mathrm{mod}41\right)$ 与同余式$15in{d}_{6}x\equiv in{d}_{6}14\left(\mathrm{mod}40\right)$ 等价，即$15in{d}_{6}x\equiv 25\left(\mathrm{mod}40\right)$ ，所以$3in{d}_{6}x\equiv 5\left(\mathrm{mod}8\right)$ 。解得$in{d}_{6}x=15+8t$ ，$t=0,\pm 1,\pm 2,\cdots$ 。所以$in{d}_{6}x\equiv 7,15,23,31,39\left(\mathrm{mod}40\right)$ ，查表可知$x\equiv 3,7,13,29,30\left(\mathrm{mod}41\right)$ 。所以同余式$x^{15}\equiv 14\left(\mathrm{mod}41\right)$ 的解为$x\equiv 3,7,13,29,30\left(\mathrm{mod}41\right)$ 。

同余式的求解一直是初等数论教学中的一个重点内容，在整本教材中有三章的内容都在讲解同余式的求解。所以学生在学习起来也会比较吃力。在实际的教学过程中，首先就是要打好基础，这个基础指的就是“一次同余式”，这是同余式的开端。所以在这一部分教学中，应该加强学生对“一次同余式”的理解，可以类比着“一元方程”，来让学生理解一次同余式，同时也应强调它区别于一元方程的地方，也就是一次同余式的解有很多数，只不过在同余的关系下将它们看成一个剩余类。其次，在讲解高次同余式的求解时，因为涉及到的相关定理如上面定理7和定理8，它们的证明有一定的难度。在实际教学过程中，在讲这些证明时，学生接受的效果也不是太好，所以在这一部分教学时，可以适当略去一些证明，多增加一些练习，让学生掌握解题的思路和方法，这样学生接受的效果也能更好一些。然后就是指数和指标这两个定义，学生在学习过程中总容易弄混淆，所以在教学时可多强调几遍，多列举一些例子帮助学生辨析这两个概念。最后，在讲解完全部的同余式求解的知识后，应该对一般同余式的求解的方法加以总结，不然这部分知识有些分散，学生理解的也不是很透彻，很容易学完就忘，对同余式也没有系统化的理解和认知。在加以总结后，学生就能系统地掌握同余式的求解方法和步骤了。

4. 指数的两种证明方法

在第2章，已经给出了指数的定义。在这一章，我们将给出指数的两种证明方法。

给定正整数m。要想证明a对模m的指数是$\gamma$ ，也即证明$\gamma$ 是使得同余式$a^{\gamma }\equiv 1\left(\mathrm{mod}m\right)$ 成立的最小正整数。所以有如下两种方法：

第一种，先证明$\left(a,m\right)=1$ 以确保a对模m的指数存在；然后证明$a^{\gamma }\equiv 1\left(\mathrm{mod}m\right)$ ；最后假设正整数$\delta$ 满足$a^{\delta }\equiv 1\left(\mathrm{mod}m\right)$ ，证明$\gamma \le \delta$ ；

第二种，先证明$\left(a,m\right)=1$ 以确保a对模m的指数存在；然后设a对模m的指数是$\delta$ ，证明$\delta =\gamma$ 。

下面，我们将举例来看一下这两种方法的具体应用。

例7 已知a对模m的指数是$\delta$ 。证明$a^{\lambda }$ 对模m的指数是$\frac{\delta }{\left(\lambda ,\delta \right)}$ 。

证明：因为a对模m的指数存在，所以$\left(a,m\right)=1$ ，从而$\left(a^{\lambda },m\right)=1$ 。因此，$a^{\lambda }$ 对模m的指数存在。

方法1. 设$\lambda =k_1\left(\lambda ,\delta \right)$ ，$\delta =k_2\left(\lambda ,\delta \right)$ 。则

${\left(a^{\lambda }\right)}^{\frac{\delta }{\left(\lambda ,\delta \right)}}=a^{\frac{\lambda }{\left(\lambda ,\delta \right)}\delta }=a^{k_1\delta }={\left(a^{\delta }\right)}^{k_1}\equiv 1\left(\mathrm{mod}m\right)$ 。

设正整数$\eta$ 满足${\left(a^{\lambda }\right)}^{\eta }\equiv 1\left(\mathrm{mod}m\right)$ 。则$a^{\lambda \eta }\equiv 1\left(\mathrm{mod}m\right)$ 。又a对模m的指数是$\delta$ ，所以$\delta |\lambda \eta$ ，即$k_2\left(\lambda ,\delta \right)|k_1\left(\lambda ,\delta \right)\eta$ ，即$k_2|k_1\eta$ 。又因为$\left(k_1,k_2\right)=\left(\frac{\lambda }{\left(\lambda ,\delta \right)},\frac{\delta }{\left(\lambda ,\delta \right)}\right)=1$ ，所以$k_2|\eta$ ，所以$k_2\le \eta$ ，即$\frac{\delta }{\left(\lambda ,\delta \right)}\le \eta$ 。

因此，$a^{\lambda }$ 对模m的指数是$\frac{\delta }{\left(\lambda ,\delta \right)}$ 。

方法2. 设$\lambda =k_1\left(\lambda ,\delta \right)$ ，$\delta =k_2\left(\lambda ,\delta \right)$ 。设$a^{\lambda }$ 对模m的指数是$\eta$ 。则$a^{\lambda \eta }\equiv 1\left(\mathrm{mod}m\right)$ 。又a对模m的指数是$\delta$ ，所以$\delta |\lambda \eta$ ，即$k_2\left(\lambda ,\delta \right)|k_1\left(\lambda ,\delta \right)\eta$ ，即$k_2|k_1\eta$ 。又因为$\left(k_1,k_2\right)=\left(\frac{\lambda }{\left(\lambda ,\delta \right)},\frac{\delta }{\left(\lambda ,\delta \right)}\right)=1$ ，所以$k_2|\eta$ ，所以$k_2\le \eta$ ，即$\frac{\delta }{\left(\lambda ,\delta \right)}\le \eta$ 。

反之，又

${\left(a^{\lambda }\right)}_{}^{\frac{\delta }{\left(\lambda ,\delta \right)}}=a^{\frac{\lambda }{\left(\lambda ,\delta \right)}\delta }=a^{k_1\delta }={\left(a^{\delta }\right)}^{k_1}\equiv 1\left(\mathrm{mod}m\right)$ ，

所以$\eta |\frac{\delta }{\left(\lambda ,\delta \right)}$ ，所以$\eta \le \frac{\delta }{\left(\lambda ,\delta \right)}$ ，从而$\eta =\frac{\delta }{\left(\lambda ,\delta \right)}$ 。

因此，$a^{\lambda }$ 对模m的指数是$\frac{\delta }{\left(\lambda ,\delta \right)}$ 。

在这一小节，我们给出了指数的两种证明方法，这样不仅可以帮助学生从不同角度理解指数的定义，也可以拓宽学生的数学思维。在实际教学过程中，不仅仅是“指数”这一知识点，其它内容都可以去积极探索有没有不同于书上的证明方法，这样便可以为学生提供多种解题思路，拓宽学生的思维，不使学生的思维固化，让其更加发散。

5. 小结

在这篇文章中，我们主要列出了初等数论的一些应用，一是得到了任意整数能被给定正整数整除的等价条件；二是给出了一般同余式的求解方法及过程；三是给出了指数的两种证明方法。这些不仅丰富了初等数论的教学内容，也能给学生提供系统化的方法，使得学生对初等数论的理解更加深刻，从而增加学生的学习兴趣。