2017年11月26日

勤労感謝の日

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

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

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

-----

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

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

( 2m - 1 ) - ( 2n - 1 )
= 2m - 2n
= 2n[ 2m-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 で

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

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

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

より

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

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

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

( 27 - 1 ) - ( 22 - 1 ) = 22( 25 - 1 ) [ 127 - 3 = 4・31 ) ]
( 25 - 1 ) - ( 22 - 1 ) = 22( 23 - 1 ) [ 31 - 3 = 4・7 ]
( 23 - 1 ) - ( 22 - 1 ) = 22 [ 7 - 3 = 4 ]

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

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

Posted by fussy at 20:43Comments(0)TrackBack(0)数学