2.3.20

素数のときと同じ方針で示してみる。

$$S = \{n_1, n_2, \ldots n_k\}$$とする。 任意に$$x \in S$$をとり$$A = \{n_1 x \bmod m, n_2 x \bmod m, \ldots, n_k x \bmod m\}$$とする。

任意の$$i$$について$$n_i \perp m$$かつ$$x \perp m$$なので$$n_i x \bmod m \in S$$である。 これより$$A \subseteq S$$である。

次に任意の相異なる$$i,j$$について$$n_ix \bmod m \neq n_jx \bmod m$$となることを背理法で示す。 $$n_ix \bmod m = n_jx \bmod m$$なる$$i,j$$が存在したとすると $$(n_i - n_j)x \bmod m = 0$$となり、$$x \perp m$$より$$(n_i - n_j) \bmod m = 0$$である。 従って$$n_i \bmod m = n_j \bmod m$$であるが、$$n_i,n_j$$は$$m$$より小さいので$$n_i = n_j$$となり矛盾する。

これより$$A$$の要素はちょうど$$k$$個ある。 $$S$$の要素がちょうど$$k$$個あり$$A \subseteq S$$であるから$$A = S$$である。

$$S$$は1を必ず含むので$$A$$も必ず1を含む。 先に示したことから$$n_i x \bmod m = 1$$なる$$n_i$$がちょうど一つあるので示したいことが示せた。