論理学 へ戻る【 問 題 １ 】
-
全体集合を自然数とする。「 a と b が互いに素である ならば a, 2a, 3a,・・・ (b−1) a を ｂ で割った余りは全て異なる 」という命題が真であることを証明せよ。
-
「 a と b が互いに素である ならば a, 2a, 3a,・・・ (b−1) a を ｂ で割った余りは全て異なるということはない 」という命題が真であると仮定する。
そこで、ma と na（ m ＞ n ）を b で割った余りは同じであるとする。すると、(m−n) a は b の倍数になる。したがって、(m−n) a ＝ kb と置ける。したがって、k ＝ (m−n)a / b となる。１ ≦ m−n ＜ b だから、もし仮に m−n と b が通分できたとしても分母になんらかの数が残る。a と b が互いに素であるので、この残った数は a とは通分できない。ということは、k は自然数ではないということである。これは矛盾である。というわけで、上記の命題は真ではないことが分かった。ということは、その逆の「 a と b が互いに素である ならば a, 2a, 3a,・・・ (b−1)a を ｂ で割った余りは全て異なる 」という命題は真であることが明らかになった。（ 背理法 ）
-
全体集合を整数とする。 a と b は自然数とする。 「 a x ＋ b y ＝ 1 が 解（ x , y ）を持つ ならば a と b は互いに素である 」という命題が真であることを証明せよ。
-
この命題の対偶「 a と b が互いに素ではない ならば a x ＋ b y ＝ 1 は 整数解（ x , y ）を持たない 」が真であることが証明されれば、問題の命題が真であることが明らかになる。
a と b が互いに素ではないとき、 a と b の公倍数を n（ n ≧ 2 ）とする。すると、a x ＋ b y は n の倍数になるので、a x ＋ b y ≧ n ≧ 2 となり、a x ＋ b y ＝ 1 という式はどんな x と y のペアをしても成立しないことが分かる。というわけで、問題の命題の対偶が真であることが証明されたので、問題の命題が真であることが明らかになった。
-
「 自然数 a と b が互いに素である ならば a x ＋ b y ＝ 1 は 整数解（ x , y ）を持つ 」という命題が真であることを証明せよ。
-
a と b が互いに素であるから a, 2a, 3a,・・・ (b−1) a を ｂ で割った余りは全て異なる。したがって、余りが 1 となる数が必ず存在する。それを ma と置き、b で割った商を n と置く。m も n も自然数である。すると、ma ＝ bn ＋ 1 という式が成り立つ。したがって、ma − bn ＝ 1 となり、a x ＋ b y ＝ 1 は 整数解（ x , y ）＝（ m , −n ）を持つことが分かる。