Fussy's Diary

先週は「勤労感謝の日」で一日お休みでした。

今年の祝日はあと一日、「天皇誕生日」を残すのみとなりました。気がつけばもうすぐ 12 月。寒さも厳しくなってきて、冬が苦手な自分にとってはつらい時期となりました。

「数学問題bot(個人用)‏」から同志社大学の問題です。例によって合っている保証なしです。

-----

m, n は自然数とする ( m > n )。「m と n が互いに素」⇔「2^m - 1 と 2ⁿ - 1 が互いに素」を示せ ( 同志社 )

2^m - 1 と 2ⁿ - 1 の差分は以下のように計算できます。

( 2^m - 1 ) - ( 2ⁿ - 1 )
= 2^m - 2ⁿ
= 2ⁿ[ 2^m-n - 1 ]

m, n は互いに素であることから m - n は m, n の因数を持たず ( もし持つならば、m の因数を G、m = Gm'、m - n = GK としたとき m - n = Gm' - n = GK より n = G( m' - K ) となり m, n は共通の因数を持つので矛盾 )、m, n, m - n はそれぞれ互いに素になります。
m > n, m > m - n より、n と m - n に対して同様の操作を行うと、n > m - n の場合、 n, m - n, n - ( m - n ) = 2n - m は互いに素であり、n > m - n, n > 2n - m です。さらに m - n, 2n - m に対してこの操作を行います。以下、最大数 ( 最初は m ) を除いた 2 数でこの操作を繰り返すと、常に値は小さくなっていき最終的には差が 1 になります。この 2 数を M, N ( M > N )とすると M - N = 1 で

( 2^M - 1 ) - ( 2^N - 1 )
= 2^M - 2^N
= 2^N[ 2^M-N - 1 ] = 2^N

であり、2^M - 1 と 2^N - 1 は奇数なので 2 を因数として持たず、従って互いに素です。遡って M + N, M, N では

( 2^M+N - 1 ) - ( 2^M - 1 ) = 2^M( 2^N - 1 )

より

2^M+N - 1 = 2^M( 2^N - 1 ) + ( 2^M - 1 )

であり、2^M - 1 と 2^N - 1 は互いに素で 2^M は偶数なので 2^M - 1 と 2^M( 2^N - 1 ) は互いに素なので、2^M+N - 1, 2^M - 1, 2^N - 1 は それぞれ互いに素です。これを繰り返していくと最終的に 2^m - 1 と 2ⁿ - 1 は互いに素になります。

ちなみに m = 7, n = 2 のとき

( 2⁷ - 1 ) - ( 2² - 1 ) = 2²( 2⁵ - 1 ) [ 127 - 3 = 4・31 ) ]
( 2⁵ - 1 ) - ( 2² - 1 ) = 2²( 2³ - 1 ) [ 31 - 3 = 4・7 ]
( 2³ - 1 ) - ( 2² - 1 ) = 2² [ 7 - 3 = 4 ]

で 3, 7, 31, 127 は全て互いに素になります。

2^m - 1, 2ⁿ - 1 はそれぞれ 1 のみからなる m, n 桁の二進数で表すことができます。m, n が互いに素でない時、m, n の共通因数を G とすると、2^m - 1, 2ⁿ - 1 はどちらも 2^G - 1 ( G 桁の 1 のみからなる二進数 ) で割り切れます。よって 2^m - 1, 2ⁿ - 1 は共通因数 2^G - 1 を持ち、互いに素ではありません。この対偶として、2^m - 1, 2ⁿ - 1 が互いに素なら m, n は互いに素です。