問.
が互いに素であるための必要十分条件は,
が互いに素であることである.
(証明)
対偶を証明する.
()
「が互いに素でないならば,は互いに素でない」を示す.
が互いに素でないので,ある整数 で となるものが存在する.
これよりかつと表せる.
したがっては互いに素でないことが示された.
()
「が互いに素でないならば,は互いに素でない」を示す.
が互いに素でないので,ある素数でとなるものが存在する.
から一般性を失うことなく, は を割り切るとしてよい.
ここで の両辺を で割ると, となる.
変形して となるが は を割り切るので は整数である.
ゆえに は整数なので は整数である.
したがって は を割り切る.
すなわち はいずれも で割り切れることが分かった.
よって は互いに素でないことが示された. (証明終)