答えが1002になるであろうことは容易に想像がつきますが、それを証明するのが大変ですね。
>>1が答えを出すためにヒントになっているように見えるので、まずは途中まで証明してみました。
本来なら、厳密に条件付けをしなければいけないのでしょうが、そのあたりは省略ということで。
(i)kが偶数のとき
(i-1)kよりも小さい自然数xがkと互いに素である場合、
kが偶数であることからxは奇数となり、明らかにxと2kも互いに素である。
同様に、k+xは奇数かつkと互いに素となることから、k+xと2kは互いに素である。
(i-2)kよりも小さい自然数xがkと互いに素でない場合、
kとxは共通の因数を持つことから、xと2kも共通の因数を持ち、したがってkとxは互いに素ではない
同様に、k+xとkは共通の因数を持つことから、k+xと2kも共通の因数を持ち、互いに素でない。
以上より、2kと互いに素となる数は、1〜kの間のφ(k)個、k+1〜k+(k-1)の間にφ(k)個あることから、
φ(2k)=2φ(k)となる
(ii)kが奇数のとき
(ii-1)kよりも小さい自然数xがkと互いに素である場合、かつxが奇数の場合
kとxは互いに素でありxが奇数であることから、2kとxも明らかに互いに素
また、k+xは偶数となることから、2kとk+xはそれぞれ因数2を持ち、互いに素ではない
(ii-2)kよりも小さい自然数xがkと互いに素である場合、かつxが偶数の場合
kとxはそれぞれ因数2を持ち、明らかに互いに素ではない
また、k+xは奇数かつkと互いに素となることから、k+xと2kは互いに素である
(ii-3)kよりも小さい自然数xがkと互いに素でない場合
kとxは共通の因数を持つことから、xと2kも共通の因数を持ち、したがってkとxは互いに素ではない
同様に、k+xとkは共通の因数を持つことから、k+xと2kも共通の因数を持ち、互いに素でない。
以上より、2kと互いに素である数は、kと互いに素である数のうち奇数のものおよびkと互いに素である数のうち偶数のものにkを足した数となるから、φ(2k)=φ(k)となる
あとは、任意の2^mに対して、φ(x)=2^mとなる奇数xが必ず一つだけ存在するということを証明すれば、帰納法で証明できると思うのですが・・・。
>>1の前半部分がそのための条件にも見えるのですが、私の力では理解不能でした・・・。
>>1が答えを出すためにヒントになっているように見えるので、まずは途中まで証明してみました。
本来なら、厳密に条件付けをしなければいけないのでしょうが、そのあたりは省略ということで。
(i)kが偶数のとき
(i-1)kよりも小さい自然数xがkと互いに素である場合、
kが偶数であることからxは奇数となり、明らかにxと2kも互いに素である。
同様に、k+xは奇数かつkと互いに素となることから、k+xと2kは互いに素である。
(i-2)kよりも小さい自然数xがkと互いに素でない場合、
kとxは共通の因数を持つことから、xと2kも共通の因数を持ち、したがってkとxは互いに素ではない
同様に、k+xとkは共通の因数を持つことから、k+xと2kも共通の因数を持ち、互いに素でない。
以上より、2kと互いに素となる数は、1〜kの間のφ(k)個、k+1〜k+(k-1)の間にφ(k)個あることから、
φ(2k)=2φ(k)となる
(ii)kが奇数のとき
(ii-1)kよりも小さい自然数xがkと互いに素である場合、かつxが奇数の場合
kとxは互いに素でありxが奇数であることから、2kとxも明らかに互いに素
また、k+xは偶数となることから、2kとk+xはそれぞれ因数2を持ち、互いに素ではない
(ii-2)kよりも小さい自然数xがkと互いに素である場合、かつxが偶数の場合
kとxはそれぞれ因数2を持ち、明らかに互いに素ではない
また、k+xは奇数かつkと互いに素となることから、k+xと2kは互いに素である
(ii-3)kよりも小さい自然数xがkと互いに素でない場合
kとxは共通の因数を持つことから、xと2kも共通の因数を持ち、したがってkとxは互いに素ではない
同様に、k+xとkは共通の因数を持つことから、k+xと2kも共通の因数を持ち、互いに素でない。
以上より、2kと互いに素である数は、kと互いに素である数のうち奇数のものおよびkと互いに素である数のうち偶数のものにkを足した数となるから、φ(2k)=φ(k)となる
あとは、任意の2^mに対して、φ(x)=2^mとなる奇数xが必ず一つだけ存在するということを証明すれば、帰納法で証明できると思うのですが・・・。
>>1の前半部分がそのための条件にも見えるのですが、私の力では理解不能でした・・・。