82
到目前为止，我们所探讨的内容都以质数模为前提。接下来讨论当模是合数的情况。然而，这里出现的定理不像前面的情况那么优美，也无须使用微妙的技巧去发现这些定理（因为使用前面讲过的原理就可以推导出这里几乎所有的定理） ，那么详尽地讨论所有的情况是没有必要也是烦琐枯燥的。所以，我们只讨论哪些情况与之前有相同的性质，哪些情况有它们自己独特的性质。
83
针对一般情况，条目45到48的定理已经得到证明。但是条目49的定理必须做如下更改：
如果f 表示与模m 互质且小于m 的数的个数，即f ＝φm （参考条目38） ，且如果a 是与m 互质的一个给定的数，那么a 的对于模m 同余于1的最小方幂的指数t 就等于f 或者是f 的一个因数。
如果我们用m 替换p ，用f 替换p -1，并且取与m 互质且小于m 的数来代替1，2，3，…，p -1，条目49中定理的证明在这种情况下是成立的。所以读者自己可以回到条目49来做这个证明。但是，条目50和51里面讨论的其他那些定理在这里不能直接应用，必须采用迂回的方式。关于条目52和后面的那些定理，就模是质数幂和模可以被多于一个质数整除的不同情况，它们的区别是非常大的。因此，我们单独讨论后一种情况。
84
如果p 是质数，且模m ＝p n ，那么我们有f ＝p n -1 （p -1） （参考条目38） 。现在，如果我们将条目53和54中的定理用于这个情况下，并按照前一条目做出必要的改变，我们就会发现，只要我们首先证明形如x t -1≡0（mod p n ）的同余方程不可能有多于t 个不同的根，那两个条目中的定理在这种情况下依然成立。我们在条目43中通过使用更加一般的结论证明了对于指数模它是成立的；但这条定理仅针对质数模成立，在合数模的情况下不适用。然而，我们会用一种特殊的方法证明在这种情况下这条定理是成立的。在第8章我们会更加容易地证明它。
85
我们现在证明这条定理：
如果数t 和p n -1 （p -1）的最大公约数为e ，那么同余方程x t ≡1（mod p n ）就有e 个不同的根。
令e ＝kp v ，式中k 不包含因数p 。因此，k 整除数p -1。那么，对于模p ，同余方程x t ≡1就有k 个不同的根。如果我们分别用A ，B ，C ，…表示这些不同的根，那么，对于模p n 的同样的同余方程的每个根一定对于模p 同余于数A ，B ，C ，…中的一个。现在我们来证明：同余方程x t ≡1（mod p n ）有p v 个根对于模p 同余于A ，有相同多个根对于模p 同余于B ，…。由此推出，正如我们之前所说的，所有的根的个数等于kp v ，也就是e 。下面我们首先证明：如果α 是对于模p 同余于A 的根，那么
也是该同余方程的根。然后，我们证明：在对于模p 同余于A 的数中，只有形如α ＋hp n -v （h 表示任意整数） 的数是该同余方程的根。因此，显然只有p v 个不同的根。对于同余于B ，C ，…的根，这个结论也成立。最后，我们证明：总是能够找到一个对于模p 同余于A 的根。
86
定理
如果按照上一条目，t 是一个被p v 整除，但不能被p v ＋1 整除的数，我们有（α ＋hp μ ） t -α t ≡0（mod p μ ＋v ）并且同余于α t -1 hp μ t （mod p μ ＋v ＋1 ）。
当p ＝2且μ ＝1时，定理的第二部分不成立。
通过展开二项式可以证明这条定理，前提是我们能证明第2项以后所有的项都能被p μ ＋v ＋1 整除。但是，因为讨论系数的分母会陷入争论，我们选择下面的方法。
我们首先假设μ 大于1且v 等于1，那么我们就有
但是
α ＋hp μ ≡α （mod p 2 ）
所以，（α ＋hp μ ） t -1 ，α （α ＋hp μ ） t -2 ，…中的每一项都同余于α t -1 （mod p 2 ），并且，它们的和就同余于tα t -1 （mod p 2 ）；那么它就是tα t -1 ＋Vp 2 的形式，式中V 是某个整数。那么，（α ＋hp μ ） t -α t 就有如下的形式：
α t -1 hp μ t ＋Vhp μ ＋2
即同余于α t -1 hp μ t （mod p μ ＋2 ）且同余于0（mod p μ ＋1 ）。
因而，对于这种情况，定理得证。
如果现在仍假定μ ＞1，但对于另外的一些v 值定理不成立，那么，就一定应该有一个界限值，在到达这个界限之前，此定理总是成立的。超出这个界限之后，此定理就不成立。令使定理不成立的v 的最小值等于φ 。显然，如果t 能够被p φ -1 整除，但不能被p φ 整除，则定理就仍然成立。反之，如果我们用tp 代替t ，定理就不成立。那么，我们有
或者等于α t ＋α t -1 hp μ t ＋up μ ＋φ ，其中，u 是整数。但是，因为对于v ＝1，定理已经得证，我们有
因而
即，如果用tp 代替t ，定理成立，因为v ＝φ 。但是这与假设矛盾，因此，定理对于v 所有的值都成立。
87
现在，还剩下μ ＝1的情况没有讨论。通过使用完全类似于上个条目的方法，我们可以不用二项式定理证明以下各式
因此，由它们的和得到的多项式（项数为t ） 就同余于下式
但是，因为t 可以被p 整除，所以，除了当p ＝2的情况外（上一条目提到了这个情况） ，（t -1）t /2就都可以被p 整除。然而，在其他的情况下，我们有（t -1）tα t -2 hp /2≡0（mod p 2 ），并且像上一条目一样，多项式和同余于tα t -1 （mod p 2 ）。剩下的证明按照同样的方式进行。
除了p ＝2的情况之外，一般的结果就是
（α ＋hp μ ） t ≡α t （mod p μ ＋v ）
并且，对于任何模为比p μ ＋v 更高次的p 的方幂，（α ＋hp μ ） t 就不同余于α t ，前提是h 不能被p 整除且p v 是整除t 的p 的最高次幂。
由此我们可以立即推导出在条目85中提出的两条定理：
第一，如果α t ≡1，我们同样有（α ＋hp n -v ） t ≡1（mod p n ）。
第二，如果某个数α ′对于模p 同余于A ，因而也同余于α ，但对于模p n -v 不同余于α ，并且如果α ′满足同余方程x t ≡1（mod p n ），我们就令α ′＝α ＋lp λ 使得l 不能被p 整除。由此推出，λ ＜n -v ，因而（α ＋lp λ ） t 就对于模p λ ＋v 同余于α t ，但对于模p 的更高次幂的模p n 则不同余于α t 。因此，α t 不可能是同余方程x t ≡1的根。
88
第三，我们曾经提出求同余方程x t ≡1（mod p n ）的某个同余于A 的根。我们这里只演示在已经知道这个方程对于模p n -1 的一个根的情况下，我们怎样求解。显然，知道这一点就足够了；因为，当模为p 时，A 是这个同余方程的一个根，我们可以从模p 推到模p 2 ，进而依次推到后面所有连续的方幂。
因而，我们假设α 是同余方程x t ≡1（mod p n -1 ）的一个根。我们现在求同一个同余方程对于模p n 的根。我们假设这个根等于α ＋hp n -v -1 。从上一条目知，这个根一定有这种形式（我们单独考虑v ＝n -1的情况，但是要注意v 不可能大于n -1） 。因此，我们得到
但是
因此，如果这样选择h ，使得1≡α t ＋α t -1 htp n -v -1 （mod p n ）或者使得（α t -1）/p n -1 ＋α t -1 ht /p v 被p 整除［因为，根据假设，1≡α t （mod p n -1 ）并且t 能够被pv 整除］ ，那么，我们就求得了想要的根。从上一章可知，这是能够做到的，因为我们预先假设t 不能被比p v 更高次的p 的方幂整除，因而α t -1 t /p v 就与p 互质。
但是，如果v ＝n -1，即，如果t 能够被p n -1 整除，或者被p 的更高次幂整除，则对于模p ，满足同余方程x t ≡1的每一个值A 也将对于模p n 满足这个同余方程。因为，如果令t ＝p n -1 τ ，则有t ≡τ （mod p -1）；又因为A t ≡1（mod p ），所以A τ ≡1（mod p ）。因此，令A τ ＝1＋hp ，我们就有A τ ＝（1＋hp ） pn -1 ≡1（mod p n ） （参考条目87） 。
89
我们在条目57以及以后的条目中，借助定理“同余方程x t ≡1不能有多于t 个不同的根”所推出的一切结论，对于模是质数的方幂的情况来说都是成立的，并且，如果我们把那些属于指数p n -1 （p -1）的数，也就是那些在周期中包含了所有不被p 整除的数，称为原根 ，那么，对于模是质数的方幂的情况来说就存在原根。进而，我们所讨论的关于指标以及它们的应用，以及关于同余方程x t ≡1的解的全部结论都可以应用于这种情况。因为证明没有什么困难，重复这些证明就是多余的。我们之前已经演示过如何从模p 的同余方程x t ≡1的根去求得模p n 的这个同余方程的根。现在，我们必须补充上文中所排除的当模为2的方幂的情况的讨论。
