物理学基础精解【56】

物理学中的数论

一次同余式及解法

涉及数学中的同余理论，以下是对其定义、数学原理、公式、计算、例子和例题的详细阐述：

定义

一次同余式，亦称线性同余方程，指未知数仅出现一次幂的同余方程。若a，b都是整数，m是正整数，当a≢0 (mod m)时，把ax=b (mod m)称为模m的一元一次同余方程，简称一次同余方程。

数学原理

• 解的存在性：一次同余式ax≡b(mod m)有解的充要条件是(a,m)|b，即a和m的最大公约数能整除b。

• 解的数量：

  • 若(a,m)=1，则同余式有且仅有一个解。
  • 若(a,m)=d>1，且d|b，则同余式有d个解。
  • 若(a,m)=d>1，但d∤b，则同余式无解。

公式与计算

在解决一次同余式时，常用的公式和计算步骤包括：

• 求最大公约数：首先计算a和m的最大公约数d。
• 化简同余式：将原同余式ax≡b(mod m)化简为(a/d)x≡(b/d)(mod m/d)。
• 求解特解：求解化简后的同余式的一个特解x0。
• 求通解：根据特解x0，利用公式x≡x0+t·(m/d)(mod m)，其中t为整数，求出所有解。

例子

• 例子1：解同余式2x≡3(mod 5)。

  • 首先，计算2和5的最大公约数，得d=1，满足(a,m)=1的条件，因此同余式有唯一解。
  • 然后，找到2在模5下的乘法逆元，即满足2s≡1(mod 5)的s。通过计算可得s=3（因为2×3=6≡1(mod 5)）。
  • 最后，将b乘以s，得到x≡3×3=9≡4(mod 5)。

• 例子2：解同余式6x≡28(mod 32)。

  • 首先，计算6和32的最大公约数，得d=2，且d|28，因此同余式有2个解。
  • 然后，将原同余式化简为3x≡14(mod 16)。
  • 接着，求解化简后的同余式的一个特解。通过观察或尝试，可以找到特解x0=10（因为3×10=30≡14(mod 16)）。
  • 最后，利用公式x≡x0+t·(m/d)求出所有解，即x≡10+16t(mod 32)，其中t=0,1。因此，原同余式的两个解分别为x≡10(mod 32)和x≡26(mod 32)。

例题

• 例题：解同余方程组

  {x≡2(mod 3)
  x≡3(mod 5)
  x≡2(mod 7)}

  这是一个一次同余方程组，可以通过中国剩余定理（孙子定理）来求解。具体步骤如下：

  • 首先，验证模数3、5、7是否两两互素，由于它们是质数，因此满足条件。
  • 然后，分别求解每个同余式的一个特解。例如，对于第一个同余式x≡2(mod 3)，特解可以是x0=2；对于第二个同余式x≡3(mod 5)，特解可以是x1=3；对于第三个同余式x≡2(mod 7)，特解可以是x2=2。
  • 接着，利用中国剩余定理的公式，求出同余方程组的唯一解。具体公式和计算过程较为复杂，这里不展开详述。最终可以求得解为x≡23(mod 105)。

综上所述，一次同余式及解法涉及数学中的同余理论、最大公约数、乘法逆元等概念，通过一系列步骤和公式可以求解出同余式的解或解集。

中国剩余定理（Chinese Remainder Theorem）

又称孙子定理，是中国古代求解一次同余式组问题的方法，也是数论中一个重要定理。以下是对其定义、数学原理、公式、计算、例子和例题的详细阐述：

定义

中国剩余定理用于求解一次同余式组问题，即找出这样一个正整数，它分别能被给定的多个正整数整除，并且是其中最小的。具体来说，设有m个线性方程，每个方程有n个未知数，形式为：x≡ai(mod pi)，其中i=1,2,…,m。假设pi两两互质，那么存在一个解x，使得x≡ai(mod pi)对i=1,2,…,m都成立。

数学原理

中国剩余定理的原理可以简述为：几个数相加，如果存在一个加数不能被数a整除，那么它们的和就不能被整数a整除。这个定理的证明可以通过数学归纳法和欧几里得算法得出。

公式

中国剩余定理的公式如下：

设m1,m2,…,mk是两两互素的正整数，M=m1×m2×…×mk，对于任意的整数a1,a2,…,ak，同余式组有唯一解，解的形式为：

x=M1’M1a1+M2’M2a2+…+Mk’Mkak(mod M)

其中，Mi=M/mi，Mi’Mi≡1(mod mi)（即Mi’是Mi关于模mi的逆元）。

计算步骤

1. 找出每个模数的逆元。
2. 根据公式计算出解x。

例子

一个整数除以3余2、除以5余3、除以7余2，求这个整数。

转化为下述公式：

X%3=2
X%5=3
X%7=2

求整数X除以3余2、除以5余3、除以7余2。

例题

例题1：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

这个问题是中国南北朝时期的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题。翻译成现代文的意思是：一个整数除以三余二，除以五余三，除以七余二，求这个整数。表示如下：

x≡2(mod 3)
x≡3(mod 5)
x≡2(mod 7)

这是一个典型的中国剩余定理问题，可以通过上述公式和计算步骤求解。

例题2：一个数，除以5余1，除以3余2，求这个数是多少？

满足除以5余1的数，可以表示为5n+1，从小到大依次为1,6,11,16,21,26,……。然后再去看第二个条件是除以3余2，所以在这些数当中满足条件的最小的数是11。所以满足题目当中两个条件的数就可以表示成15n+11（15为3和5的最小公倍数）。

中国剩余定理

是数论中一个重要的定理，用于求解一次同余式组问题。通过掌握其定义、数学原理、公式、计算步骤以及例子和例题，可以更好地理解和应用这一定理。
完全剩余系是数论中的关键概念，以下是对其定义、数学原理、公式、计算、例子和例题的详细阐述：

一、定义

从模n的每个剩余类中各取一个数，得到一个由n个数组成的集合，叫做模n的一个完全剩余系（CRS）。剩余类是指，对于某一个特定的正整数n，一个整数集中的数模n所得的余数域。

二、数学原理

1. 完整性：CRS中的数来自模n的不同剩余类，因此它们模n两两不同余。
2. 等价性：CRS中的数加减n的整数倍后，新集合仍为模n的CRS。
3. 乘法性质：若m为正整数，a与m互质，k遍历模m的CRS，则ak+b也遍历模m的CRS。

三、公式

若m是一个给定的正整数，则全部整数可以被分为m个集合，记做K0，K1，…，Km−1，其中Kr（r=0，1，…，m−1）是由一切形如qm+r的整数组成的。

四、计算

设m是正整数，整数a满足gcd(a，m)=1，b是任意整数。若x是遍历m的完全剩余系，那么ax+b也是遍历m的完全剩余系。

五、例子

1. 对于m=5，模5的一个完全剩余系可以是{0，1，2，3，4}。这个集合中的每个元素都代表了一个模5的剩余类：

   • C0={…，−10，−5，0，5，10，…}
   • C1={…，−9，−4，1，6，11，…}
   • C2={…，−8，−3，2，7，12，…}
   • C3={…，−7，−2，3，8，13，…}
   • C4={…，−6，−1，4，9，14，…}

2. 模4的CRS可以是{0，1，2，3}或{4，5，6，7}。

六、例题

证明：对每一个素数p∈{3，5，7，11，13}，存在无穷多个正整数n，使得p|an。

证明：

1. 写几项不难发现，对于较小的n，可以直接验证结论成立，即存在m，使得p|am（因为下面论述的前提是首先要存在这样的m）。
2. 下面用反证法来处理，假定有有限个n，使得p|an。找出最大的一个下标m，由m的最大性，对于k>m，都有p∤nk。
3. 目标是通过递推式，得到一个比m更大的k，使得p|ak成立。
4. 对递推公式进行分析和处理，取3m≤i≤3m+2（希望得到的新的下标比m大），这时有ai=ai−1+am。
5. 考虑整数p的性质，对它模p处理，有a3m−1≡a3m≡a3m+1≡a3m+2≡r(记作)(modp)（注意am≡0(modp)）。规定r∈{1，2，3，…，p−1}（显然r≠0）。
6. 对于9m−3≤i≤9m+8，有3m−1≤[i/3]≤3m+2。再用一次递推式，与上面类似，有ai≡ai−1+r(modm)。把从9m−3至9m+8的所有整数代入，并写出通项的形式，有a9m−4+j≡a9m−4+j−1+r≡a9m−4+j−2+2r≡…≡a9m−4+jr(modm)。
7. 这样的形式暗示要用完全剩余系的观点来看。由于无法一下子处理这么多的同余式，每个同余式单个看起来没有什么值得刻画的点，因此要把所有的同余式联系起来，整体地思考。
8. 把这些同余式看成同余方程组，容易证明r，2r，3r，…，jr遍历一个modp的完全剩余系，于是，必然存在一个i∈{1，2，3，…，j}，使得ir≡−a9m+4(modm)，即ir+a9m+4≡0(modm)，于是ir+a9m+4≡a9m+4+i≡0(modm)。

说明：本题的出发点是从某一项p|an开始，在其后面找到一个mod p的完全剩余系，从而找到下一项。另外，本题对于完全剩余系构造的技巧十分常见和重要。事实上，指出对这类题目的记忆是有效的。就像熟悉经典棋谱对于棋手的帮助一样，数学家们可以从一些经典题目中养成识别、构建、解决问题的能力。并且这些问题可能在理论发展或者证明更加深刻的结论中起到关键作用。

综上所述，完全剩余系是数论中的重要概念，具有广泛的应用价值。

参考文献

1.文心一言
2.《初等数论》陈景润