内容 第三章 · 幂剩余 · 41
术语线索
moduli compositi / reductio ad factores
复合模数 / 化归到因子。
命题
For composite moduli, power-residue problems are reduced to the corresponding prime-power moduli.
复合模数下的幂剩余问题，可以化归到各个素数幂因子下的问题。
读法 现代白话辅助
这里第三章回扣第二章的剩余合并。若模数分解成互素的素数幂，解一个幂同余就等于分别解各个分量，再用中国剩余定理合并。
分步证明Step-by-step proof
1 / 2把模数分解为互素的素数幂。
分别判断每个素数幂模数下是否有解；全部有解后再合并。
小例 worked example
题
判断 x²≡1 (mod 15) 时为什么可分看模 3 和模 5？
解
15=3·5 且互素。模 15 的解正好对应模 3 和模 5 的解的组合，再由中国剩余定理合并。
我的笔记 自动保存