証明、こんな感じ? ac≡bc (mod n) かつ「c と n の最大公約数が d」であれば、 a≡b (mod n') (ただし n=dn') を証明する。 このとき c=dc' とおけて、d は c と n の最大公約数であるから n' と c' は互いに素である。 k を整数として ac-bc=kn を成り立たせる k が存在し、この式から (a-b)dc'=kdn' ∴ (a-b)c'=kn' ここで n' と c' は互いに素であるから、a-b は n' の倍数であることがわかり、このことから a≡b (mod n')