数学関連


初等整数論の初歩
初等整数論の初歩を解説しました。
高校の教科書の「整数の性質」には,証明がきちんと書かれていないので,それを埋めるもので,大学入試問題は扱っていませんが,大学入試問題を深く理解す るための基盤となるものです。
主に,高木貞治先生の「初等整数論講義」の第1章の前半部分を参考にして,証明を丁寧に書いたつもりでいます。
また, 初等整数論の応用として,RSA暗号についても解説しています。
校正が十分でないため,間違いや誤植が多いかもしれませんが,見つかり次第に直すつもりですので,ご容赦ください。
フィボナッチ数列9999
問題 1
a1=1,a2=1,an+2=an+1+an  で定義されるフィボナッチ数列
    1,1,2,3,5,8,13,21,……
の項の中に,下4桁が9999となるものが存在することを示しなさい。
一般に,nを任意の自然数として,下n桁がすべて9になる項が存在します。

問題 2
第n項には,1がn個並ぶ数列
   1,11,111,1111,11111,……
を考えます。この数列の項の中に,2の倍数と5の倍数は存在しません。
しかしながら
    111は3の倍数,111111は7の倍数,11は11の倍数,111111は13の倍数,1111111111111111は17の倍数,……
などとなります。
一般に,2,5以外の素数について,この数列の項の中に,その素数で割り切れるものが存在します。
さらに一般化すると,「自然数nが素因数に2と5を含まなければ,この数列の項の中に,nで割り切れるものが存在する。」となります。このことを示してく ださい。
なお,次の数は素数です。1が並ぶ素数は他にも存在するようです。
 11
 1111111111111111111
 11111111111111111111111
 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

問題1は解答を付けましたが,問題2は解答を付けません。問題1の解答を参考にして考えてみて下さい。問題2には,問題1と同様に鳩ノ巣原理を用いる証明 の他に,初等整数論のオイラーの定理を用いる証明があります。
13枚の金貨
金貨が13枚あって,その中に1枚だけ重さが違う偽金貨がある。偽金貨は,本物より重いか軽いか分からない。その偽金貨を,天秤 を3回だけ使って見つけよ。ただし,偽金貨が本物より重いか軽いかを見分けなくて良いものとする。
上記の問題を一般化して,(3n-1)/2枚のとき,天秤をn回だけ使って見つける証明ができたので掲載します。


素数が無限に存在することの証明
補題 a,bを互いに素な整数とすると,ab と a+b は互いに素である。
証明 ab と a+b が互いに素でないと仮定すると,ある素数pが存在して,整数k,lを用いて ab=kp,a+b=lp と表される。
このとき,ab=kpより,a,bの少なくとも一方はpの倍数である。
aがpの倍数であるとすると,b=lp-aよりbがpの倍数となり,aとbが互いに素であることに矛盾する。
bがpの倍数であるとしても,同様に矛盾する。
ゆえに,ab と a+b は互いに素である。

証明の基本形(以下のすべての証明は,この証明の変形です。)

自然数Nは,「N=K×L,KとLは互いに素な自然数」と分解できる。
このとき,K×L と K+L は互いに素であるから,N´=N×(K+L) の異なる素因数の個数は,Nの異なる素因数の個数より多い。
この操作は,無限に続けることができるから,素数は無限に存在する。

ユークリッドの証明(証明の基本形と同じになるように,少し変形 しました。)
p1, p2,……,pn が異なる素数の組であるとき,p1×p2×……×pn と P=p1×p2×……×pn+1 は互いに素である。
よって,Pの素因数の1つをpn+1とすると,p1, p2,……,pn, pn+1も異なる素数の組である。
この操作は,無限に続けることができるから,素数は無限に存在する。

フェルマー数による証明の変形
数列 {an} は,a1を1より大きい整数として,次の漸化式により定義される数列とする。
    an+1=a1a2a3……an+1
任意の自然数nについて,an+1と ak (n=1,2,3,…….n) は互いに素であるから, {an} の各項は,どの2つも互いに素である。
よって,任意に多くの異なる素因数を作れるので,素数は無限に存在する。

サイダックの証明
nは1より大きい整数とする。n と n+1 は連続する整数であるから,これらは互いに素である。
したがって,N2=n(n+1) は少なくとも2つの異なる素因数を持つ。
同様に,n(n+1) と n(n+1)+1 は連続する整数であるから,互いに素である。
よって,N3=n(n+1){n(n+1)+1} は少なくとも3つの異なる素因数を持つ。
この操作は,無限に続けることができる。

漸化式 an+1=a1a2a3……an+1 において Nn=a1a2a3……an とおくと, an+1=Nn+1,Nn+1=Nnan +1 であるから Nn+1=Nn(Nn+1) が成り立つ。
よって,フェルマー数による証明とサイダックの証明は同等であると言える。補足証明

スティルチェスの証明の背理法を使わない変形
p1, p2,……, pn を異なる素数の組であるとき,p1×p2×……×pn と P=p1×p2×……×pm+pm+1×……×p は互いに素である。
よって,Pの素因数の1つをpn+1とすると,p1,p2,……,pn,pn +1も異なる素数の組である。
この操作は,無限に続けることができるから,素数は無限に存在する。

エラトステネスの篩による証明
Ⅰ 2以上の自然数のリストを考える。
Ⅱ リストの斜線が引かれていない数のうち最小なものは素数であるから,その数の倍数に斜線を引く。これを繰り返す。
Ⅱにおいて,素数 2, 3,……,p が見つかったとき,2×3×……×p には,2, 3,……,p のすべてによる斜線が引かれる。
ところが,2は倍数は2個に1個,3の倍数は3個に1個,……,pの倍数はp個に1個ずつ斜線が引かれるから 2×3×……×p±1 には斜線が引かれることはない。
よって,斜線が引かれない数が常に存在するから,Ⅱは無限に繰り返される。

どの証明も,本質的にはユークリッドの『原論』にある証明の変形にすぎないですね。
変形として,「a1,a2,……,an のどの2つも互いに素ならば,a1a2……an と a2a3……an+a1a3……an+a1a2a4……an+…… +a1a2a3……an-1は互いに素である」 ことを用いた証明もあります。

ユークリッドの証明を発展させた次の命題は,ショルンの証明を変形して得られたものです。
命題 小さい方からk番目の素数をpkと する。n≧2のとき,pn+2 から p1p2……pn×(pn+2) +1 までの整数のなかに,pn+2 個以上の素数が存在する。
証明 T=p1p2……pn とし,aj=T×j+1 (1≦j≦pn+2) を考える。
    (ai,ak)=(T×i+1,T×k+1)=(T×i+1-T× k-1,T×k+1)=(T×(i-k),T×k+1)
i>k とする。このとき,1≦i-k≦pn+1 (pn+1は偶数)であるから,i-k の素因数はすべて T の素因数である。
よって,T×(i-k)  の素因数はすべて T×k の素因数であるから,T×(i-k)  と T×k+1 は互いに素である。
したがって,ai と ak は互いに素である。
さらに,aj=T×j+1 (1≦j≦pn+2) と pj (1≦j≦n) はどの2つの組も互いに素であるから,aj の素因数はすべて pn より大きい。
ゆえに,pn+2 から T×(pn+1)+1=p1p2……pn×(pn+2) +1 までの整数のなかに,pn+2 個以上の素数が存在する。

これより,素数は無限に存在する。( a1=p1p2……pn+1 だけを考えれば,ユークリッドの証明と一致する。)

3次方程式の解の公式
3次方程式の解の公式で,カルダノの解法と若干異なる解法を紹介します。
単振り子
単振り子の運動方程式の厳密解と,周期の近似値を求めてみました。

最初のページに戻る