もっと簡単だった…

gcd(x, 100)=1の時
kx≡23 (mod 100)を満たす正整数kが存在することを示す。

1≦i<j≦100とすると1≦j−i≦99
よってx(j−i)は100で割り切れない。∴x(j−i)≢0 (mod 100)
これよりmod 100でxiとxjは異なる。
∴集合{xi}と集合{i} (i=1,2,…,100)はmod 100で一致する。
よってxk≡23 (mod 100)を満たす正整数kが(1から100の中に)存在する。

補題の証明で全部終わっていた。