素数全書

素数全書 練習問題1.17

つかみどころがわからなくて、かなり長い間考えていた問題である。 が、先日出張中の宿でいろいろやっているうちに気がついた。modulo 3 で系列を追いかけるのである。スタートの素数をPとする。P=3 でなければ、Pの3での余りは1か2である。仮にP≡1(mod 3)と…

素数全書 問題1.17

ちょこっと計算にもっともふさわしい問題である。ただし、=100,000,000=一億以下の素数を求めておく必要がある。いままで使っていた既知の素数で割ってみるテストを繰り返すという schemeプログラムだと時間がかかりすぎてどうにもならなかったので、エラト…

素数全書 練習問題1.16

有名な Cauchyの素数生成多項式の問題である。まずはちょこっと計算により、の値(-40≦x≦39)を出してみた。ただし、負の整数部分については単に折り返しているだけなので実質は0≦x≦39である。 41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223,…

素数全書 練習問題1.15

まず、(ここに)の収束性について。帰納法により n≧2ならば が示せるので、となり、上に有界であるので収束する。□ さて、d(n)の母関数を考える。 前問1.14から、十分大きなkに対しては [tex:d(k)n]の場合がある。2)と3)の場合の数は同じなので、2)の場合を二…

素数全書 練習問題1.14

正整数nの因子の数をd(n)とするとき、任意のについて、を証明せよ、という問題であるがなかなか不思議な結果である。ヒントに沿って考えてみる。 pを素数として、とする。このときである。を満たすpとkを考えると、kを動かすと右辺が指数関数であるのでpを固…

素数全書 練習問題1.13

Legendreによる素数定理π(x)=o(x)の証明を再現する問題らしい。まず、 であるが、の定義から、『1≦n≦x で nの素因子がすべてより大きいような n』の個数である。ところが、nがより大きな素数のどれかに一致しない場合、nのその他の素因子はより小さくなるた…

素数全書 練習問題1.12

厳密に定式化せよ(cast in rigorous language)ということであるが、ある整数xが与えられた時点でそれが素数かどうかは決まっているので、『xが素数である確率』といったもような表現はそもそも変である。 そこで、xが素数かどうかということを知るための情報…

素数全書 練習問題1.10、1.11

まず、N以下の正整数で、有限素数列のいずれかで割り切れるものの数が-\sum_{i0.22857\cdots]である。 さて、後半。の逆数の和が発散するとして、の任意の有限部分列を作ると先の議論と同様にして、の漸近密度がで抑えられることがわかる。にできるのでの漸…

素数全書 練習問題1.9

まず、前半。 は明らかなので、aの位数dはnの約数である。もし、d<n だとすると [tex:1\le a^d-1

素数全書 練習問題1.8

問題1.7によく似ているが、与えられた数の素因子のどれか一つはmod 4で1になるという部分がうまくいかないため、全く違う解法となった。 qをの素因子の一つとすると、 一方、フェルマーの小定理よりであるが、もし (q-1)/2 が奇数であるととなり、矛盾してし…

素数全書 練習問題1.7

はその形から、n≡3(mod 4)である。しかも、p以下の素数では割り切れないため、その素因子はpより大きな素数である。そのどれか一つは少なくとも mod 4で3になる。なぜなら、そうでないと 素因子は全て mod4 で1になるが、それらを掛け合わせた nは mod 4で3…

素数全書 練習問題1.6

Euclidの証明を少し変えて としてを考える。(の条件をつけるのはとしたいため。)これはのどれでも割り切れないため、より大きな素数を素因子として含む。 よって 。 ∴ [tex:p_n\frac{1}{ln2}ln ln x] □ しかしながら実際にこの不等式を計算してみるとπ(10)…

素数全書 練習問題1.5

n番目の素数を与える Gandhi formula を証明せよという問題。(GahndiとprimeでWeb検索するとどうしてもprime minister Gahndiが出てくるというオチが...)ヒントを参考に、から、d桁毎に1が立っている二進小数展開ができ、それが合成数のところでうまく打ち…

練習問題1.4

π(x)を与える一見すごそうな公式に見えるのだが、実は前問と同じく計算としては実用性のないものである。nをkで割って n=k・m+r , 0≦r<k と表しておく。であるから、 よって ⇔ r≠0 ⇔ kはnを割り切らない ⇔ r=0 ⇔ kはnを割り切るが成立する。よって = nの2以…

練習問題1.3

和の中でm=nの時とm=1の時はどちらもとなるので、それ以外の項の和が 0 かどうかで素数判定できるという等式である。n:素数でない⇒ ∃p,q>1 (n=p・q) ⇒ であるから素数でないなら和は2でない。つまり 問題の和=2 ⇒ n:素数 逆に 1<m<n かつ なる m が存在し…

素数全書 問題1.2

ユークリッド整域 ⇒ 単項イデアル域 ⇒ 素元分解整域というような一般論もあるが、ここではユークリッド互除法を使って直接証明してみる。素数pとpで割り切れない整数xに対して、ユークリッド互除法を繰り返し使うとkp+lx=1 なるような整数k,lが存在する。同…

素数全書 練習問題1.1

さっそく練習問題を解いてみる。私は練習問題をちまちまと解くのが好きである。練習問題愛好家と言ってもいいであろう。暇人の一種である。 さて、問題は2つ出されていて、問、次のそれぞれの条件を満たす最大のNを求めよ。 1) {2,3,..,N-1} の中の数でNと…

趣味のちょこっと計算

とまあ、最初は有限群の勉強と思ってブログを始めたのだが、それからコロコロと興味が変わってしまい、更新もごぶさたであった。しかし…最近、私の趣味の数学魂を刺激する次の2つの書物がでてしまったのだ。数学基礎論作者: 新井敏康出版社/メーカー: 岩波書…