対偶による証明

質問

（問題）
ｋを整数とするとき、aｋをｂで割った余りをｒ（ｋ）で表す。ｋ、ｌをb－１以下の正の整数とするとき「ｋ≠１ならばｒ（ｋ）≠ｒ（ｌ)」であることを示せ。ただし、aとｂは互いに素な整数である。

（解説）
元の命題の対偶を取ると「ｒ（ｋ)＝ｒ（ｌ）ならばｋ＝ｌ」となりこれを証明する。aｋ、aｌをｂで割ったときの商をｐ、ｑとすると、
aｋ＝ｂｐ＋ｒ（ｋ）…(1)
aｌ＝ｂｑ＋ｒ（ｌ）…(2)
(1)－(2)より
a（ｋ－ｌ）＝ｂ（ｐ－ｑ）
ここで、aとｂは互いに素であるから、ｋ－ｌはｂの倍数である。
また、ｋ、ｌはb－１以下の正の整数であるから
０＜ｋ＜ｂ、０＜ｌ＜ｂ
よって、－ｂ＜ｋ－ｌ＜ｂ
ゆえにｋ－ｌ＝０であるからｋ＝ｌ
したがって元の命題は証明された。

なんですけど…

ここで、aとｂは互いに素であるから、ｋ－ｌはｂの倍数である。
↑の部分のなぜｋ－ｌはｂの倍数になるのか？
また、ｋ、ｌはb－１以下の正の整数であるから
０＜ｋ＜ｂ、０＜ｌ＜ｂ
↑のー１はどうなったのか？と
よって、－ｂ＜ｋ－ｌ＜ｂ
ゆえにｋ－ｌ＝０であるからｋ＝ｌ
↑のゆえにｋ－ｌ＝０であるからｋ＝ｌの部分の＝０がどこからきたのか分かりません。

質問三つと多いですが、回答お願いします。

回答No.2

PRFRD · ベストアンサー

(1)
> ここで、aとｂは互いに素であるから、ｋ－ｌはｂの倍数である。
> ↑の部分のなぜｋ－ｌはｂの倍数になるのか？

　a (k-l) = b (p-q)
という式を睨みます．
右辺は明らかに b の倍数です．したがって左辺も b の倍数です．
ところが a と b は互いに素なので，a は b の約数を一切含みません．
したがって (k-l) が b の倍数でないと，左辺は b の倍数になりません．

(2)
> また、ｋ、ｌはb－１以下の正の整数であるから
> ０＜ｋ＜ｂ、０＜ｌ＜ｂ
> ↑のー１はどうなったのか？と

「b-1 以下の整数」であることと，「b 未満の整数」であることは同じなので，
不等式の上側をイコール抜きの不等号「< b」にして -1 を消しています．
（もちろん，-1 を書いて「≦ b-1」としてもかまいません）

(3)
> よって、－ｂ＜ｋ－ｌ＜ｂ
> ゆえにｋ－ｌ＝０であるからｋ＝ｌ
> ↑のゆえにｋ－ｌ＝０であるからｋ＝ｌの部分の＝０がどこからきたのか分かりません。

前のほうで見たように，k-l は b の倍数です．
つまり k-l は ..., -2b, -b, 0, b, 2b, ... のどれかです．
ところが，いま不等式 -b < k-l < b があるので，
この条件を満たすものは k-l = 0 しかありません．

回答No.1

zug

１．互いに素ということはｂの１を除くどの約数もａの約数ではないので
　　等式からｂの全ての約数は（ｋ－ｌ）の約数です。
　　よって（ｋ－ｌ）はｂの倍数です。

２．ｋ≦ｂ－１はｋ＜ｂに含まれますし整数条件なら等しいです。

３．－ｂより大きくてｂより小さいｂの倍数は０だけです。