Microsoft Word - ‚f’ﬂ.doc

Size: px

Start display at page:

Download "Microsoft Word - ‚f’ﬂ.doc"

せいいそみ
4 years ago
Views:

1 素数いろいろ H1 下尾知 1 素数 (1) 素数の定義知っているとは思いますが素数の定義をあらためて確認しましょう素数 :1およびその数自身の他に約数を有しない正の整数広辞苑第五版より例えば 13は1と13と-1と-13でのみ割り切れますが約数も正の整数ですので -1や-13は13の約数ではありませんゆえに13は素数です誤解がないために書いておきますが 1 およびその数自身の他に約数を有しない正の整数ではなく 1およびその数自身の他に約数を有しない正の整数ですので 1は素数ではありませんよまた 1 でも素数でもない正整数を合成数と言います他には双子素数と言うものがあります双子素数とは {3,5}{5,7}{11,13}{17,19}{29,31} のように差が 2 である素数の組のことです数が大きいものであれば {99989,99991} などがありますまた双子素数予想は双子素数は無限に存在するというものなのですがいまだに解決されていません (2) エラトステネスの {EQ * jc2 * "Font:MS 明朝 " * hps10 o ad( s up 9( ふるい ), 篩 )} エラトステネスの篩というのは正整数の集合から素数だけを篩い出す方法です素数を習った人はおそらく聞いたことがあるでしょうでは実際にこの方法を使って100までの素数表を作ってみましょうまず 2~100 の整数を並べます次に 2 は素数なので残して 2 から先の 2 の倍数を消します次に残った最初の数 3 を残して 3 から先の 3 の倍数を消します次に残った最初の数 5 を残して 5 から先の 5 の倍数を消します次に残った最初の数 7 を残して 7 から先の 3 の倍数を消します

2 次に残った最初の数 11 を残して 11 から先の 11 の倍数を消しますですがもう残っている 11 の倍数はありませんなぜなら 11 2,11 3,,11 10 はもう消えているので消すことが出来るのは以上の 11 の倍数でありそれはすでに範囲外だからです結局 2 乗が 100 を超えないところまでつまり 10 までの素数を使って消せばいいのです以上のような作業をすると下のようになります 2, 3, 4, 5, 6, 7, 8, 9,10 11,12,13,14,15,16,17,18,19,20 21,22,23,24,25,26,27,28,29,30 31,32,33,34,35,36,37,38,39,40 41,42,43,44,45,46,47,48,49,50 51,52,53,54,55,56,57,58,59,60 61,62,63,64,65,66,67,68,69,70 71,72,73,74,75,76,77,78,79,80 81,82,83,84,85,86,87,88,89,90 91,92,93,94,95,96,97,98,99,100 つまり 100 までの素数は 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47, 53,59,61,67,71,73,79,83,89,97 になります次にこのような作業をした後に何個の素数が残るかというのを数えるのではなく計算して求めてみましょう ( ここで出てくる [n] というのはガウス記号といって n の整数部分を表しています ) まず 2,3,5,7 の倍数の個数を計算します 2 の倍数は [100 2]=50 個 3 の倍数は [100 3]=33 個 5 の倍数は [100 5]=20 個 7 の倍数は [100 7]=14 個なのですが 2,3,5,7 は素数であり 1 は素数ではないのでそれらを修正すると結局 114 個になりますでもこれを 100 から引いてしまうと引きすぎてしまうので次は重複部分の個数を計算しましょう 6 の倍数は [100 6]=16 個

3 10 の倍数は [100 10]=10 個 14 の倍数は [100 14]=7 個 15 の倍数は [100 15]=6 個 21 の倍数は [100 21]=4 個 35 の倍数は [100 35]=2 個合計すると 45 個になりますでもこれでは戻しすぎるので今度はさらに重複している部分の個数を計算しましょう 30 の倍数は [100 30]=3 個 42 の倍数は [100 42]=2 個 70 の倍数は [100 70]=1 個 105 の倍数は [ ]=0 個合計 6 個になります最後に 4 個重複している部分の個数を計算してみます 210 の倍数は [ ]=0 個これ以上重複している部分はありません結局残った個数は =25 個になりますこの方法は素数表の範囲が大きくなるとコンピューターでも計算が大変になってしまいますしかし考え方は重要でありこのような考え方のことを包除原理といいます (3) 素数が無限にあることの証明素数が無限にあることの証明にはいろいろな方法がありますがここでは 1 番簡単な証明法を紹介しておきます証明素数の個数が有限個であったとして最大の素数を M とする N= 1 2 M+1 を作るこれは明らかに M より大きいので合成数であるところがすべての素数である 1,2,,M のどれで割っても 1 余って割り切れないということは N が素数であることになり矛盾するゆえに素数の個数は有限個ではないこれはあくまで数多くある証明の一つです他の証明を見てみたいと言う人は本を買ってみたりホームページをみたりしていろいろと調べてみてください 2 いろいろな素数 (1) メルセンヌ素数昔の数学者はいつも素数を表す式についていろいろ考えましたその中でメルセンヌという数学者は a n -1(n は自然数 ) の形を考えました

4 しかし a n -1=(a-1)( a n - 1+a n ) であるから a>2ならば a n -1はいつも合成数ですだとすると a=2ならばどうなるのでしょうか 2 n -1の形の数はどのような場合に素数になるのでしょうかいくつか計算してみましょう Mn=2 n -1と置きます n=1のとき M1=2 1-1=1 n=9のとき M9=2 9-1=551 n=2のとき M2=2 2-1=3 n=10のとき M10=2 10-1=1023 n=3のとき M3=2 3-1=7 n=11のとき M11=2 11-1=2047 n=4のとき M4=2 4-1=15 n=12のとき M12=2 12-1=4095 n=5のとき M5=2 5-1=31 n=13のとき M13=2 13-1=8191 n=6のとき M6=2 6-1=63 n=14のとき M14=2 14-1=16383 n=7のとき M7=2 7-1=127 n=15のとき M15=2 15-1=32767 n=8のとき M8=2 8-1=255 下線を引いているのが素数ですまず nが合成数のとき n=s t,2 s =rと置くと 2 n -1=2 s t -1=r t -1=(r-1)( r t ) となり s>1だからr>2で 2 n -1が合成数であることがわかりますしかし n= 11のときは素数にならないので nが素数の場合に絶対素数になるわけではありませんそこでメルセンヌは nが257までの中で n=2,3,5,7,13,17,19,31,67,127,257( 全て素数 ) のときにMnも素数であると予想しました ( おそらく大変な計算をしたのでしょう ) 現在では M 67,M 257 のときは素数ではなく M 61,M 89,M 107 は予想から抜けていたことがわかっていますなぜこんなことが断言できるのかというとリュカという人が 1891 年にメルセンヌ型の整数に対してそれほど長い時間をかけずに素数かどうかを判定できるリュカテストと呼ばれる方法を発見しましたどんな方法かというと例えば M 7 が素数かどうか確かめたいとき 4 から始めて (mod M 7) で 2 乗しては 2 を引くという操作を続けます M 7=127 a 1=4 a (mod M 7) a (mod M 7) a (mod M 7) a (mod M 7) a (mod M 7) a 7-1 まで計算して a 7-1 0(mod M7) ならば M 7 は素数であり

5 a 7-1 0(mod M7) ならば M 7 は素数ではありません (b c(mod a) というのは b と c の差が a で割り切れることを表しておりこのことを b と c が a に関して合同であるという ) 以上のような方法を使えばとても大きな素数を見つけ出すことが可能になりますちなみに 2002 年までの最大のメルセンヌ素数は M です (2) 完全数数にはいろいろな分類があるがその中に過剰数不足数完全数というものがありますまず過剰数というのはその数自身を除いた約数の総和がその数より大きい数のことを表します例えば 24 はその数自身を除いた約数の総和が =36 となり 24 より大きいので過剰数です次に不足数というのはその数自身を除いた約数の総和がその数より小さい数のことを表します例えば 25 はその数自身を除いた約数の総和が 1+5=6 となり 25 より小さいので不足数である素数はその数自身を除いた約数は 1 のみなので明らかに不足数です最後に完全数というのはその数自身を除いた約数の総和がその数と等しくなる数のことを表します例えば 6 はその数自身を除いた約数の総和が 1+2+3=6 となるので完全数です次に小さい完全数は 28 でその後は 496,8128, と続きますではどんな数が完全数になるのでしょうか驚くべきことにこの答えは完全ではありませんがかの有名なユークリッドによって 2300 年も昔に出されていますもし単位から始まり順次に 1 対 2 の比をなす任意個の数が定められそれらの総和が素数になるようになされそして全体が最後の数に掛けられてある数をつくるならばその積は完全数であろうこのままだと何を言っているのかわからないのでわかりやすく解説してみたいと思いますまず単位から始まり順次に 1 対 2 の比をなす任意個の数が定められそれらの総和が素数になるというのは n-1 =2 n -1 が素数であると言っていますつまりメルセンヌ素数のことですこれが最後の数に掛けられるのだから N=2 n-1 (2 n -1) が完全数であるとユークリッドは主張していますユークリッドは n=3 のときの具体的な場合を証明していますがその証明は完全に一般的ですしかしユークリッドの証明はたいへん長くまた現代式とはだいぶ違うのでここでは現代風に書き直した証明をのせておきます n を正整数とする 2 n -1 が素数ならば N=2 n-1 (2 n -1) は完全数である証明 2 n-1 の約数と 2 n -1 の約数との積は N の約数でまた 2 n-1 と 2 n -1 は互いに素だ

6 からこれで N の約数は尽くされる 2 n-1 の約数は 1,2,2 2,2 3,2 4,,2 n-1 2 n -1 は素数だからその約数は 1,2 n -1 ゆえに N の約数は 1 1,1 (2 n -1),2 1,2 (2 n -1), 2 n-1 1,2 n-1 (2 n -1) である結局 N の約数 (N 自身も含む ) の総和は ( n-1 )(1+2 n -1)=(2 n -1)2 n =2N であるから N 自身を除いた約数の総和は 2N-N=N である次に気になるのはこの逆はどうなのだろうかということですつまり N が完全数ならば 2 n-1 (2 n -1) の形でなければならないかということですユークリッドはこの証明はしなかったが後のオイラーは偶数の完全数は 2 n-1 (2 n -1) の型に限ることを次のように証明した ( ここで出てくる σ 1(N) というのは N の約数の総和を表しており a=b c(b と c は互いに素 ) のとき σ 1(a)=σ 1(b) σ 1(c) であるちなみに σ 0(N) というのは N の約数の個数である ) 偶数の完全数は N=2 n-1 (2 n -1) の型に限る証明 N が偶数の完全数であるとする N から因数 2 をできるだけ出して N=2 r-1 k,k は奇数とする r-1 としたのはあとの形と合わせるためである σ 1(N)=σ 1(2 r-1 k)=σ 1(2 r-1 )σ 1(k) σ 1(2 r-1 )= r-1 =2 r -1 だから σ 1(N)=(2 r -1)σ 1(k) 1 N は完全数だから σ 1(N)=2N=2 r k=(2 r -1)k+k 2 1,2 より (2 r -1)σ 1(k)=(2 r -1)k+k 両辺を (2 r -1) で割ると k σ 1(k)=k+ 2 r -1 右辺の 2 項は k の約数でその和が約数全体の和 σ 1(k) になるのだから k の約数は 2 つだけよって k は素数でもう一つの項は 1 でなければならないよって k=2 r -1( 素数 ) ゆえに N=2 r-1 (2 r -1) いまだに奇数の完全数は発見されていません存在しないであろうという予想ですが証明されていません存在したとしても以上だそうです

7 (3) フェルマー素数素数を表す式はあるかという問題でかの有名なフェルマーは F=2 m +1 という型の数を考えました m から 2 のベキをできるだけ出して m=2 t k=uk,k は奇数としますさらに 2 u =v と置くと F=2 m +1=2 uk +1=(2 u ) k +1=v k +1 k は奇数だから k>1 ならば v k +1=(v+1)( v k - 1 -v k ) のように因数分解されて素数ではありませんそこで F が素数であるためには k=1,m=2 n で Fn=2 (2^n) +1 となることが必要ですこの形の整数が素数であるかどうかはこれだけではわかりませんこの形の整数のことをフェルマー数その中で素数であるものをフェルマー素数といいますフェルマーはフェルマー数 Fn=2 (2^n) +1 はすべて素数であると予想しました果たしてこの予想は当たっているのでしょうか実はこの予想は間違っていますではどのように間違っているのか見てみましょう F0=2 1 +1=3 F1=2 2 +1=5 F2=2 4 +1=17 F3=2 8 +1=257 F4= =65537 ここまでは苦労して調べれば全て素数であることが判りますでも次が問題で F5= = = であるから F 5 は合成数ですこのことはフェルマーの予想が出てから 100 年も後にオイラーによって見つけられましたフェルマーの予想に反して F 5 からあとはまだ素数は発見されておらずいまでは F 5 から F 30 までは全て合成数であるということがわかっています F 5 以降は全て合成数であろうという予想もなされています 3 あとがき

8 短い文章ですが素数については書き始めるときりがないのでこれでおしまいですいろいろな素数についての話いかがだったでしょうか私は素数というものが昔から好きだったのですが今回は素数入門計算しながら理解できるを読んでみて素数にもいろいろなものがあることを知りましたこの本には素数のことだけでなく整数全般のこともいろいろ書いてありしかも多くの数学者の説明が書いてあるのでなかなか面白い入門書です興味がある人は是非読んでみてください初めて部誌を書いたのでどんな風にすればいいのかどのくらい難しくすればいいのかというのがわかりませんでしたもしかしたら他の人よりも簡単になったかも知れません最後にここまで読んで頂きありがとうございます来年も灘の文化祭に来て数学研究部に寄って頂けるのをお待ちしております 4 参考文献ブルーバックス素数入門計算しながら理解できる著者芹沢正三

æœ•å¤§å–¬ç´—æŁ°,æœ•å°‘å–¬å•“æŁ°,ã…¦ã…¼ã‡¯ã…ªã……ã…›ã†®äº™éŽ¤æ³Ł

æœ•å¤§å–¬ç´—æŁ°,æœ•å°‘å–¬å•“æŁ°,ã…¦ã…¼ã‡¯ã…ªã……ã…›ã†®äº™éŽ¤æ³Ł 最大公約数, 最小公倍数, ユークリッドの互除法最大公約数, 最小公倍数とはつ以上の正の整数に共通な約数 ( 公約数 ) のうち最大のものを最大公約数といいます. と 8 の公約数は,,,,6 で, 6 が最大公約数つ以上の正の整数の共通な倍数 ( 公倍数 ) のうち最小のものを最小公倍数といいます. との公倍数は, 6,,8,,... で, 6 が最小公倍数最大公約数, 最小公倍数の求め方