勉強時間の計測に時間時刻記録

2009年04月16日

素数かどうかを速く判定する方法


自然数nが素数かどうかを素数の定義に従って判定しようとすると
1より大きくn未満の自然数で割ってみなければなりません。

ところが全ての自然数は素数の積であらわせるから・・・@(証明は一番下)
そのうちの素数だけで割リ切れるかどうかを確かめればいいです。

しかし次の定理を使うともう少し楽になります。


「nが√n以下の素数で割り切れないならnは素数である」

このことを使って113が素数かどうかを判定してみよう。
100<113<121 なので
10<√113<11
よって√113以下の素数は2,3,5,7である。
113はこれらのどれでも割り切れないので素数である。


証明 

nが素数でないなら1より大きくn未満のある自然数s,tを用いて
n = st 
とあらわせる。
s > √n かつ t > √n とすると n = st > n となって矛盾するから
sまたはtは√n以下でなければならない。
よってs、tともに素数の積だからnは√n以下の素数で割り切れる。
すなわちnが素数でないならnは√n以下の素数で割り切れることが証明された。
この対偶より
nが√n以下の素数で割り切れないならnは素数である


証明終了




@の証明
nが素数の積であらわせないとすると
1より大きいある自然数s,tを用いて
n = st
とあらわせる。
nは素数の積で表せないないからsまたはtは素数でない。
よって同様にs、tのうち素数でないものを1より大きいある自然数の積で表せる。
nは素数の積で表せないのでこの操作を何度繰り返しても素数でないものがある。
よってnは2以上の自然数の無限個の積になってnより大きくなってしまう(n<2^nだから)ので矛盾である。


証明終了
タグ:素数

posted by qc at 17:12 | Comment(0) | その他 | このブログの読者になる | 更新情報をチェックする

2009年04月07日

4で割った余り

ある自然数を4で割ったあまりはその下2桁を4で割った余りに等しい。


証明
大雑把に言えば百の位以上は100の倍数なので4で割り切れるので
下2桁の余りが全体のあまりになる。
以下もうちょっと詳しく。

以下の4つを正しいとして証明します。
(1)
任意の自然数は
杷(i)*10^i (0≦i, 0≦f(i)≦9)
であらわせる。
たとえば
278
= 2*100 + 7*10 + 8*1
である。

(2)
任意の自然数nはある自然数q,rを用いて次のようにあらわせる。
n = 4*q + r (ただし 0≦r<4)
このrがnを4で割った余りである。

(3)
自然数nがkの倍数であるとはある自然数qを用いて次のようにあらわせることである。
n = k*q

(4)
kの倍数+kの倍数はkの倍数である。
なぜなら
k*s+k*t = k*(s+t)
これと(3)による。


ここからが証明
(1)より任意の自然数は
杷(i)*10^i  (0≦i)
でありその下2桁は
f(1)*10+f(0)
である。
よってある自然数k,t,rを用いて
f(1)*10+f(0) = 4*t + r(ただし 0≦r<4)
と表したときに
杷(i)*10^i = 4*k + r 
を示せばよい。

i≧2のとき
10^i
= 100*10^(i-2)
= 4*25*10^(i-2)
よってs≧2のとき
f(s)*10^s
= f(s)*4*25*10^(s-2)
= 4*(f(s)*25*10^(s-2))
= 4の倍数((3)より)・・・@ 
だから
杷(s)*10^s は @と(4)より4の倍数である。
よって(3)よりある自然数qを用いて
杷(s)*10^s = 4*q
である。

よって
杷(i)*10^i
= 杷(s)*10^s + f(1)*10+f(0) (s≧2)
= 4*q + (4*t+r)
= 4*(q+s) + r

証明終了


posted by qc at 23:43 | Comment(3) | 余りを求める方法 | このブログの読者になる | 更新情報をチェックする

2009年03月04日

最大公約数を求める(ユークリッドの互除法)

正整数a,b( a > b )の最大公約数を求める方法

aをbで割ったときの商をq、余りをrとすると
a = qb + r (0 ≦ r < b )
とあらわせます。
このときaとbの最大公約数を(a,b)であらわすと
(a,b) = (b,r)
が成り立ちます。(証明は下)
これを繰り返せばaとbの最大公約数を
それらより小さな2つの数を使って求められます。
例えばb,rに対して同じことをすれば
b = sr + t (0 ≦ t < r )
とあらわせるので
(b,r) = (r,t)
が成り立つ。
よって
(a,b) = (r,t)。


(1234,137)
1234 = 9*137 + 1
よって(1234,137) = (137,1) = 1

(376,24)
376 = 15*24 + 16
24 = 1*16 + 8
よって(376,24) = (16,8) = 8



a = qb + r (0 ≦ r < b )のとき(a,b) = (b,r)の証明
(以下aがbで割り切れることをa|bと書くことにします)

a,b,rはある整数s,t,u,vを用いて
a = (a,b)s …@
b = (a,b)t = (b,r)u …A
r = (b,r)v …B
とあらわせる。
よって
a
= qb + r
= q(b,r)u + (b,r)v (なぜならAB)
= (b,r)(qu + v)
すなわち (b,r)|a
さらに (b,r)|b だから
(b,r)はa,bの公約数である。
よって(b,r) ≦ (a,b) …C

r
= a - qb (なぜならa = qb + r)
= (a,b)s - q(a,b)t(なぜなら@A)
= (a,b)(s - qt)
すなわち (a,b)|r
さらに (a,b)|b だから
(a,b)はb,rの公約数である。
よって(a,b) ≦ (b,r) …D

CDより(a,b) = (b,r)
証明終了



別の証明

a,bの公約数をdとする。
このとき下の補題より
d|(a-qb)
よってdはb,rの公約数である。…E

逆に b,rの公約数をeとすると
a = qb + r
だから下の補題より e|a
よってeはa,bの公約数である。…F

EFよりa,bの公約数の集合とb,rのそれは一致する。
よってa,bの最大公約数とb,rのそれは同じである。
証明終了


別の証明の補題
d|a,d|b のとき次の二つが成り立つ。
d|ka (kは任意の整数)
d|(a+b)

なぜなら
d|a,d|bのときある整数s,tにより
a = sd
b = td
とあらわせる。
このとき
ka = k(sd) = (ks)d なので d|ka
a+b = sd + td = (s+t)d なので d|(a+b)
証明終了



以下の各テキストボックスに自然数を1つずつ入力してボタンを押すと最大公約数を求められます。









posted by qc at 16:48 | Comment(0) | その他 | このブログの読者になる | 更新情報をチェックする
勉強時間の計測に時間時刻記録
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。