 | 「a+pmとb+qmが互いに素」というキーワードで検索すると回答が付いた同一の質問が見つかります。
<→方向の証明>
(a+pm)q-(b+qm)p = aq-bpですから、aq-bpが素因数rを持つと仮定して矛盾を導きます。
(1)pがrの倍数の場合(2)pがrの倍数でない場合の2通りに分けて説明します。
(1)pがrの倍数の場合
aq-bp ≡ aq ≡ 0 (mod r)と(p, q) = 1より、aがrの倍数であることが必要です。
よって、a+pm ≡ 0 (mod r)となります。
一方(p, q) = 1より、qはrの倍数ではありません。
rは素数ですから、1q, 2q, ・・・, (r-1)qは法rで全て非合同で、
この中に-bと合同となるものが存在すると言えます。
つまり、b+qm ≡ 0 (mod r)となるmが存在するということです。
a+pmもb+qmもrの倍数となりますが、これは(a+pm, b+qm) = 1に矛盾します。
(2)pがrの倍数でない場合
(1)と同様にa+pm ≡ 0 (mod r)となるmを選べます。
このとき、(a+pm)q-(b+qm)p ≡ -(b+qm)p ≡ 0、かつ(p, r) = 1より、
b+qm ≡ 0 (mod r)となってしまい、これは(a+pm, b+qm) = 1に矛盾します。
以上から(a+pm, b+qm) = 1のときaq-bpが素因数を持つという仮定が誤りで、
|aq-bp| = 1と言えます。
<←方向の証明>
|aq-bp| = 1 = |(a+pm)q-(b+qm)p|ですから、(a+pm, b+qm) > 1と仮定すると、
1が1より大きい因数を持つという矛盾になります。
よって、仮定が誤りで(a+pm, b+qm) = 1です。
|