論理的な誤りがあるなら指摘して

いまnを3以上の自然数、mを自然数とする。

f(n)を「nと互いに素でnよりも小さい自然数の個数」と定義します。

f(6)なら、1、2、3、4、5のなかで互いに素なのは、1、2、4、5の4個よりf(6) = 4です。

さてm<nのときにmとnが互いに素なら、n-mとnも互いに素です（これは証明されたとします）

このときf(n)が偶数であることを証明します。

------------
k∈Nとして

n = 2k＋1のとき
｛１、２・・k｝の集合をA
｛k+１、k+２・・2k｝の集合をBとする。集合Aでnと互いに素な自然数をrとすると、
1≦ r ≦ k ⇔ n-k ≦ n-r ≦ n-1 ⇔ k+1≦ n-r ≦ 2kより互いに素なn-rは必ず集合Bに存在するので、集合Aの互いに素な個数とBの個数は同数なので、f(n)は偶数になる


n = 2k＋2のとき
｛１、２・・k｝の集合をA
｛k+2、k+２・・2k+1｝の集合をBとする。
｛k+1｝の集合をCとする

集合Cにおいて、n =2(k+1)とk+1は因数としてk+1(≧2)を持つので互いに素ではないのは
明らか。

集合Aでnと互いに素な自然数をrとすると、
1≦ r ≦ k ⇔ n-k ≦ n-r ≦ n-1 ⇔ k+2≦ n-r ≦ 2k+1より互いに素なn-rは必ず集合Bに存在し、さきほどと同じ議論になるので、f(n)は偶数になる

qed

で何か誤りがあるかね？

No.2 回答者： Tacosan 回答日時： 2014/05/04 03:25

そもそも何を証明したいのかがわからん.

「このとき」ってあるから「mとnが互いに素のとき f(n) が偶数」を証明するの? もしそうだとしたら, m はどう選べばいい?

No.1 回答者： stomachman 回答日時： 2014/05/03 22:17

> 互いに素なn-rは必ず集合Bに存在するので、

というだけじゃ

> 集合Aの互いに素な個数とBの個数は同数なので

とは言えないっしょ。こういう飛躍が残っていると、証明としてカンペキではない。

　集合
　　a={r |r∈A かつ nとrは互いに素}
　　b={x |x∈B かつ nとxは互いに素}
を考えると分かり易いでしょう。

(1) 「aからbへの対応が存在する」ということは、ご質問に記載の証明で言えている。
　しかし、その「対応」によって「r(r∈a)に対応するx(x∈B)が、p(p∈a, p≠r)にも対応する、ということはない」ということが明示されていない。つまり【aからbへの単射が存在する】ということを証明できていない。
　これを明示して初めて、bの要素の個数|b|と、aの要素の個数|a|について
　　|b|≧|a|
であることが言える。

しかし、これじゃご質問の証明を完遂するにはまだ不足ですね。

(2) 証明すべきは【aからbへの全単射（1：1対応）が存在する】ということ。これを証明すれば、
　　|b|=|a|
であると言える。

この回答への補足

f(6)なら、1、2、3、4、5のなかで互いに素なのは、1、2、4、5の4個よりf(6) = 4です。

------
ここ訂正、

f(6)なら、1、2、3、4、5のなかで互いに素なのは、1、5の２個よりf(6) = ２です。

------

ああ、わかった。前半だけ考えて終わりじゃだめなのね。Aの元に対応していないものもあるかもしれないね。そっか。

補足日時：2014/05/03 22:51