第14节 模为2的方幂
90
如果取2的高于二次的某个方幂2n作为模，则任意奇数的2n-2次幂就同余于1。
例如，38＝6561≡1（mod 32）。
因为，任意奇数都形如1＋4h或者形如-1＋4h，于是可以立刻推出这个命题（条目86中的定理）。
因此，由于奇数对于模2n所属的指数一定是2n-2的除数，容易判断这个奇数属于指数1，2，4，8，…2n-2中的哪一个。假如所给的数为4h±1，整除h的2的最高次幂的指数为m（m可以等于0，因为h可以是奇数）；那么，当n＞m＋2时，所给的数所属的指数就为2n-m-2；但是，当n等于或小于m＋2时，则所给的这个数同余于±1，因而，它所属的指数就是1或2。从条目86容易推出，形如±1＋2m＋2k的数（它等价于4h±1的形式），如果自乘到2n-m-2次幂，对于模2n同余于1；如果自乘到2的较低次幂，它就不同余于1。因此，任何形如8k＋3或8k＋5的数就属于指数2n-2。
91
由此可以推出，在这种情况下，不存在上文定义下的原根；即，不存在这样的数，使得其周期中包含了所有小于模且与模互质的数。可以发现，对于形如8k＋3的数，其奇数次幂也是形如8k＋3的数，其偶数次幂是形如8k＋1的数；不存在形如8k＋5或8k＋7的方幂。因为，对于形如8k＋3的数，它的周期是由不同的2n-2项形如8k＋3或8k＋1的数组成，小于模的这样的数也不会超过2n-2个。显然，任何形如8k＋1或8k＋3的数都对于模2n同余于形如8k＋3的一个数的方幂。通过类似的方法我们可以证明，一个形如8k＋5的数的周期包含了所有形如8k＋1和8k＋5的数。因此，如果取一个形如8k＋5的数作为基数，将所有形如8k＋1和8k＋5的数取正号，并且将所有形如8k＋3和8k＋7的数取负号后，我们都可以求得它们真实的指标。而且，我们必须将对于模2n-2同余的指标视为等价的指标。表1应当从这个角度来理解，在表1中对于模16，32和64，总是取5作为基数（对于模8不需要表）。例如，数19是形如8n＋3的数，因而我们必须对其取负号；对于模64，它的指标是7。这就意味着57≡-19（mod 64）。如果我们对形如8n＋1和8n＋5的数取负号，并且对形如8n＋3和8n＋7的数取正号，那么，我们就要给它们赋予所谓的虚指标。如果我们这样做，指标的计算法则就可以得到简化。但是，如果我们极其严格地讨论这一点，就会跑题；所以，我们把这一点放在其他场合——当我们或许能够更深入地讨论虚量理论的时候再来讨论。在我们看来，到目前为止还没有人明确地提出了关于这一点的处理方法。有经验的数学家会发现开发算法很容易。对于经验较少的人，只要他们掌握好上文中讨论的原理，可以利用我们的表格。这就类似于对于当代虚对数的研究一无所知的人可以运用对数运算一样。
92
对于由若干个质数合成的模，几乎所有关于幂剩余的结论都可由一般的同余理论来推出。我们后面会更加详细地讨论如何将对于若干个质数合成的模的同余式简化为对于模为质数或者质数幂的同余式。因此，关于这个话题我们不再作更多讨论。我们这里只是指出一个对于质数或质数幂的模有而对于其他模没有的一个优雅的性质：我们总是可以找到这样一个数，它的周期中包含所有与模互质的数。但是，有一种情况除外，即使在这里我们也能求得一个数。这种情况出现在当模是质数的两倍，或者是质数的幂的两倍之时。因为，如果模m可以简化为AaBbCc…的形式，其中A，B，C，…是各不相同的质数，如果我们用α代表Aa-1（A-1），用β代表Bb-1（B-1），…，然后选择一个与m互质的数z，我们得到zα≡1（mod Aa），zβ≡1（mod Bb），…。并且，如果μ是数α，β，γ，…的最小公倍数，那么对于所有的模Aa，Bb，…，我们有zμ≡1；因而对于它们的乘积m也成立。但是，m是质数的两倍或者质数幂的两倍的情况除外，此时数α，β，γ，…的最小公倍数总是小于它们的乘积（因为数α，β，γ，…不可能互质，它们有公约数2）。因此，不存在这样的周期，它包含的项数同与模互质且小于模的数的个数一样多，因为后者的个数等于数α，β，γ，…的乘积。例如，对m＝1001，每一个与m互质的数的60次幂必同余于1，因为数6，10，12的最小公倍数是60。在模是两倍的质数或两倍的质数幂的情况完全与模是质数或质数幂的情况相同。
93
我们已经提到了其他数学家关于本章相同主题的著作。对于想要对本主题有更加详细的讨论的读者，我们推荐下列欧拉的论文，这些论文的清晰度和洞察力都使得这位伟大的数学家领先于其他评论者：
Theoremata circa residua ex divisione potestatum relica，见Novi. comm. acad. Petrop，7［1758-1759］，1761，49-82。
Demonstrationes circa residua ex divisione potestatum per numeros primos resultantia，ibid.，18［1773］，1774，85-135。
此外，还有他的著作Opuscula Analytica的论文5，第152页；论文8，第242页。
[1] 第8章未发表，见作者自序。
[2] 但是，它们的不同之处在于，对于对数来说，不同的系统有无限个，而这里系统的个数就等于原根的个数。因为，显然，相互同余的基数产生的系统也是相同的。
[3] 没有必要知道这些方幂本身的值，因为每一个方幂的最小剩余可以轻易地通过前一个方幂的最小剩余来得到。
[4] 由条目18，我们能看出如何轻松地做到这一点。把y分解为因数不同的质数或质数的方幂的乘积。每一个因数将整除t或者u（或者同时整除两者）。考察这些因数是整除t还是整除u，来指定它们分别属于哪一个；如果同时整除两者，则可任意指定。令所有指定属于t的因数的乘积为m，其他因数的乘积等于n，显然，m整除t，n整除u，且mn＝y。
[5] 拉格朗日参考的是1770年第1版的第218页。
[6] 第125页。
[7] 这样确定数a，b，c，…，使得a≡1（mod aα）且a≡0（mod bβcγ…）；b≡1（mod bβ）且b≡0（mod aαcγ…）；…（参考条目32）。因而，a-b＋c≡1（mod p-1）（参考条目19）。现在，如果任意原根r表示为乘积ABC…的形式，我们就有A≡ra，B≡rb，C≡rc，…；并且A就属于aα的指数，B属于bβ的指数，…，那么，A，B，C…的乘积就同余于r（mod p）；显然，A，B，C，…不能用任何其他方式来确定。