Knuthの補題Pと(Z/mZ)*の構造定理の補題

“The Art of Computer Programming”において線形合同法に関する定理を証明するのに使われる補題Pの証明を記す．また整数論の教科書で(Z/mZ)*の構造を決定するのに用いられる補題 (補題2と補題4)が補題Pから導かれることを見る．