代数系入門(松坂和夫) の 第1章 §8 問題8 の解答です。 (メモレベルです、いつかまとめます。)

( M_1 , … , M_k ) は互いに素ですから、 ( M_1 y_1 + cdots + M_k y_k equiv 1 ) なる ( y_1, cdots , y_k ) が存在するので (関連: 代数系入門(松坂和夫) §5 問題11)、 その両辺に ( 2, cdots , m ) を掛けると ( m ) の完全剰余系ができます。

またそのとき、 ( y_i ) と ( m_i ) は互いに素で、 ( y_i, 2y_i, … my_i ) は重複を含めて ( m_i ) の完全剰余系を動きます。 ( (y_i, m_i ) = d ) なる ( d ) があれば左辺の全ての項は ( d ) で割り切れるため、 右辺の 1 も ( d ) で割り切れることになりますが、 そのような ( d ) は 1 しかないので ( y_i, m_i ) が互いに素であることがわかります。 また、 ( r lt m_i ) として ( py_i = qm_i + ry_i ) と書けるときは、 ( M_i p y_i = M_i q m_i + M_i r y_i = m q + r y_i equiv M_i r y_i ; pmod{m} ) より ( m_i ) を法として合同なものは置き換えて良いことになりますから、 ( M_i ) に掛ける数は 完全剰余系のに含まれる全ての剰余類の代表元 ( m_i ) 個のみを考えればよいことがわかります。

すると各 ( x_i ) は ( m_i ) 個の値をとりうることになり、 全部で ( m ) 個 の組み合わせがあります。 右辺の値も ( m ) 通りありますから、 ( x_i ) が ( m_i ) を法として異なる値ならば ( sum M_i x_i ) も ( m ) を法として異なる値となることがわかります。

もし 式の値が ( m ) と公約数 ( d ) を持つ場合は、 ( m = Pi m_i ) から ( exists i, (d, m_i) > 1 ) です。 この ( i ) をひとつ固定して ( (d, m_i) = d_0 ) とします。 すると ( forall j, j neq i Rightarrow d_0 | M_j ) 。 これより、 ( d_0 ) を法として

begin{eqnarray*} 0 & equiv & sum M_i x_i & equiv & M_i x_i . end{eqnarray*}

( (m_j, m_i) = 1 ; (i neq j) ) より ( ( M_i, d_0 ) = 1 ) 。 これより ( x_i equiv 0 ; pmod{d_0} ) で ( (x_i, m_i) geq d_0 ) 。 以上より、 ( (z, m) gt 1 Rightarrow exists i, (x_i, m_i) gt 1 ) 。 この待遇を考えて、( forall i, (x_i, m_i) = 1 Rightarrow (z, m) gt 1 )。

この逆は、 ( (x_j, m_j) gt 1 ) なる ( j ) が存在するとき、 ( d = (x_j, m_j) ) とすると ( forall i, (M_i x_i, d) geq d ) 。 よって 式の値 ( z ) についても ( (z, d) geq d ) すなわち ( (z, m) geq d ) 。 この待遇を考えて ( (z, m) = 1 Rightarrow forall i, (x_i, m_i) = 1 ) 。

以上より ( (z, m) = 1 Leftrightarrow forall i, (x_i, m_i) = 1 )

( (a, b) = 1 ) なる ( a, b ) について、 ( ab ) の剰余類として ( 0 leq ax + by lt ab ) を考えます。 このとき、 前述の性質 ( (z, m) = 1 Leftrightarrow forall i, (x_i, m_i) = 1 ) により、 ( (ax + by , ab) = 1 Leftrightarrow (x, a) = 1 wedge (y, b) = 1 ) です。 これより

begin{eqnarray*} & & varphi(ab) & = & | left{ax + by | (ax + by, ab) = 1, 0 leq ax + by lt ab right} | & = & | left{ (a, b) | (a, x) = 1, (b, y) = 1, 0 leq x lt a, 0 leq y lt b right} | & = & | left{ a | (a, x) = 1, 0 leq x lt a right} | | left{ b | (b, y) = 1, 0 leq y lt b right} | & = & varphi(a) varphi(b) . end{eqnarray*}

よって ( varphi ) は乗法的である。