Content deleted Content added
→References: split author names for working harv links |
Add one more link to Chinese remainder theorem |
||
Line 34:
:# Solve the simultaneous congruence <math display="block">x\equiv x_i\pmod{p_i^{e_i}}
\quad\forall i\in\{1,\dots,r\}
\text{.}</math>The [[Chinese remainder theorem]] guarantees there exists a unique solution <math>x\in\{0,\dots,n-1\}</math>.
:# Return <math>x</math>.
The correctness of this algorithm can be verified via the [[Abelian group#Classification|classification of finite abelian groups]]: Raising <math>g</math> and <math>h</math> to the power of <math>n/p_i^{e_i}</math> can be understood as the projection to the factor group of order <math>p_i^{e_i}</math>.
| |||