>>319
<設定>
N=(P1＾α1)(P2＾α2)…(Pm＾αm) (素因数分解）
Pi＾αi=Ni
<証明>
x＾2≡x (mod N)
⇔x(x-1)≡0 (mod N)
⇔x(x-1)≡0 (mod N1) ∧ x(x-1)≡0 (mod N2) ∧…∧ x(x-1)≡0 (mod Nm)
⇔(x≡0 (mod N1) ∨ x-1≡0 (mod N1)) ∧…∧ (x≡0 (mod Nm) ∨ x-1≡0 (mod Nm))…(*)

(*)は2＾m個の連立合同式に分割されるが、Ni,Nj(1≦i＜j≦m)は対ごとに素であることより、
それぞれの連立方程式はただひとつの解を持つ。また解の重複はない。

…という感じで。