2017年10月 / 09月≪ 12345678910111213141516171819202122232425262728293031≫11月

--.--.-- (--)

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
--:--  |  スポンサー広告  |  EDIT  |  Top↑

2009.11.28 (Sat)

ちょっと前の話題に戻ってみた

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

nは自然数とする。

(n!)2 ≧ nn

を証明せよ。


(証明)
(n!)2

= {n・(n-1)・(n-2)・ … ・1}・{1・2・3・…・n}

= (n・1)・{(n-1)・2}・{(n-2)・3}・…・(1・n)

= Π[k=1,n] k(n-k+1)

ここで、

1 ≦ k ≦ n の自然数 k において、

k(n-k+1) - n

= (k-1) n - k(k-1)

= (k-1)(n-k)

≧ 0

(等号成立は k = 1,nのとき)

∴ k(n-k+1) ≧ n

∴Π[k=1,n] k(n-k+1) ≧ Π[k=1,n] n

∴ (n!)2 ≧ n2
(等号成立は、常に k = 1,n が成り立つとき、つまり、 n = 1,2 のとき)



それでは。



↓↓あらららら。↓↓

スポンサーサイト
19:38  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2009.05.01 (Fri)

今回は簡単に

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

「次の各問いに答えよ。
(1) a2 + b2 = 2009 を満たす自然数(a,b) (a≦bは7の倍数) の組を一つ挙げよ。
(2) l2 + m2 + n2 = 2009 を満たす自然数(l,m,n) (l≦m≦nは7の倍数) の組を一つ挙げよ。」


終わりです。

↓↓終わりです↓↓

22:05  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2009.04.11 (Sat)

フェルマーの最終定理を考える3

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

戻る

その、数学オリンピックの問題というのが、これです。

 「ある世界的組織は6カ国のメンバーから構成される。組織のメンバーリストには1978人が登録し、各人が1,2,・・・,1978番と番号付けられている。このとき次のようなメンバーが少なくとも一人はいることを証明せよ。
『その人の番号は同じ国の2人の人の番号の和であるか、あるいは同じ国のある人の番号のちょうど2倍である』」



ものすごくエレガントな証明がありました。 

それでは。

次へ



↓↓難しい↓↓

22:52  |  整数-math  |  TB(0)  |  CM(1)  |  EDIT  |  Top↑

2009.04.08 (Wed)

フェルマーの最終定理を考える

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

フェルマーの最終定理、御存知ですね。

「nを3以上の自然数とするとき、
xn + yn = zn

を満たす自然数 (x,y,z) の組は存在しない。」


というものです。

今でこそ証明されましたが、このような難問になると、様々な定理が副産物として生まれます。

次の定理も、その一つです。


<<リブリの定理>>
「p,q はともに奇素数であるとする。
pを固定して、
xp + yp ≡ zp (mod q)

を満たす自然数 (x,y,z) の組が、
xyz ≡ 0 (mod q)
を満たす自然数 (x,y,z) の組しか存在しないような q が無限に存在するならば、フェルマーの最終定理は正しい。」


さて、証明してみてください。

難しくはありませんよ。

次へ

↓↓解決!↓↓

21:34  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2009.04.06 (Mon)

7の倍数判定法

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

最早記事の順番が滅茶苦茶ですね。
4/4の問題の答えは明日にしましょう。

今回は、4/1の問題の解答の補足のようなかたちになります。

7の倍数の判定法をお教えしましょう。


まず、次の数が7の倍数かどうか、判別してみてください。

24028917

386512

173999168

さあ、お分かりでしょうか?


正解は、次のように判定します。

まず、24028917から。

まず、下から3桁ずつ区切ります。

24|028|917

すると、24,28,917という3つの数字になりました。

これを、交互に足し引きします。
下から計算します。

917 - 28 + 24 = 916

916を7で割ってみると・・・

916 ÷ 7 = 130 ・・・ 6

割りきれません。

よって、24028917は7の倍数ではありません。


次は、386512です。

386|512

となりますので、

512 - 386 = 126

126 ÷ 7 = 18

と割り切れますので、386512は7の倍数です。


最後の173999168も同様に考えましょう。

173|999|168

168 - 999 + 173 = -658

-658 ÷ 7 = -94

割り切れましたので、173999168も7の倍数です。


ただ、最後に3桁の数を7の倍数かどうか判定しなければなりません。
これにも方法があります。

先ほど出てきた最終段階の数字、
916
126
-658
の3つを見てみましょう。

916の場合、
91 - 6×2 = 79
これは7で割り切れないので、916は7の倍数ではない。

126の場合、
12 - 6×2 = 0
これは7で割り切れるので、126は7の倍数である。

-658の場合、(658について確かめればよい)
65 - 8×2 = 49
これは7で割り切れるので、-658は7の倍数である。

という具合です。



それでは、授業を延長してもらえれば、これらのことの証明をご覧いただけます。

↓↓素晴らしい!!↓↓

18:54  |  整数-math  |  TB(0)  |  CM(1)  |  EDIT  |  Top↑

2008.12.26 (Fri)

返答・144

144にありましたコメントへの返答です。

フィボナッチ数列の項以外についても考えてみると、


n進法表記において、


100は、

n2 (n≧2)

で表されるので、平方数です。



121は、

n2 + 2・n + 1

= (n + 1)2 (n≧3)

で表されるので、平方数です。


169も、10進法以上では平方数であることが分かります。


しかし、225は、6進法以上での記数法において、

2n2 + 2n + 5 (n≧6)

となり、これは平方数でありません。


256も、289も、324も、361も違います。

もちろん、5進法以上での記数法においては、400は平方数です。



このように、一概には言えないものなのです。

分かりましたか?
16:17  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2008.12.17 (Wed)

144

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

144は、素晴らしい数字だと思います。

まず、144はフィボナッチ数列に登場します。

1,1,2,3,5,8,13,21,34,55,89,144,・・・

そして、この144は平方数であり、フィボナッチ数で唯一の平方数でもあるのです。

そして、素晴らしいのがこれ。

144はどのような記数法においても平方数である


144(10)では、言うまでもなく平方数です。

しかし、n進法で、
144(n)でも、これは平方数であるのです。
ことわっておきますが、nは5以上です。(4という数字を使用しているため)

証明しましょう。

(証明)
144(n)は、10進法で表すと、

1・n2 + 4・n + 4

と表せます。

そして、これは

(n + 2)2

となり、めでたく平方数であることが証明されました。

(Q.E.D.)

素晴らしいですね。

それでは。

↓↓スゲェー↓↓
17:52  |  整数-math  |  TB(0)  |  CM(1)  |  EDIT  |  Top↑

2008.12.09 (Tue)

問題11/09

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

問題1.船長様の命令です
問題2.二つのダイイング・メッセージ
nを整数とし、n2 + 1 が素数となるものは有限個あるか、それとも無限個あるか。
有限個で、具体的な個数が求まる場合は、それも答えよ。



↓↓解けたらご連絡を↓↓
21:19  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2008.11.29 (Sat)

数学テストの問題

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

問題1.船長様の命令です
問題2.二つのダイイング・メッセージ
それでは、始めましょう。

分かる人には分かると思いますが、次の問題をご覧ください。


「2n = 3m + 2
を満たすような整数 m が存在するための、整数 n の必要十分条件を求めよ」



これは、「ある数学テスト」の問題を少し拡張して一般化した問題です。
基本的には、「ある数学テスト」と同じように考えればいいのですが、これを、合同式で解いてみましょう。

合同式
合同式2
合同式3
フェルマーの小定理
ウィルソンの定理
位数の法則

などで触れた、あの合同式です。


それでは、考えてみましょう。

まず、2n = 3m + 2 について、 n が負の整数のとき、左辺は整数になりませんが、右辺は m にどのような整数を代入しても整数となるので、等しくはなりません。
よって、 n は 0 以上の整数ということになります。
n = 0 のとき、(左辺) = 1となりますが、ここで、3m + 2 = 1となるような整数 m は存在しないので、これも不適です。

よって、 n は正の整数、つまり、自然数であるときに限られます。



ここで、注目すべきが、与えられた式を変形すると、
2n - 2 = 3m
より、
2(2n-1 - 1) = 3m
となります。
m は整数で、3 と 2 は互いに素であるので、m は 2 の倍数であり、また、左辺の (2n-1 - 1) は 3 の倍数である必要があります。

よって、
2n-1 - 1 が 3 の倍数となるような自然数 n が存在すればよいことになります。

ここで、合同式の登場です。
今の事柄を合同式で表すと、

2n-1 - 1 ≡ 0 (mod 3)
となるような自然数 n が存在すればよい、ということになります。


2n-1 - 1 ≡ 0 (mod 3)
となるような自然数 n が存在するとき、

上の式より
2n-1 ≡ 1 (mod 3)
です。

ここで、2x ≡ 1 (mod 3) となる最小の自然数 x を求めると、 x = 2 であることが分かります。

よって、位数の法則より、n - 1 は、 2 の倍数、ということが分かるわけです。

つまり、 n という数は、 2 の倍数に1を足したもので自然数なので、これはすなわち奇数、ということになります。


ゆえに、n は奇数である、ということが、2n-1 - 1 ≡ 0 (mod 3) となるような自然数 n が存在するための必要条件です。

n が奇数のとき、 n - 1 は偶数となり、kを整数として、
2n-1 = 22k = 4k
と表せます。
4 ≡ 1 (mod 3)
であるので、両辺を k 乗して、
4k ≡ 1k = 1 (mod 3)
です。

ゆえに、2n-1 ≡ 1 (mod 3)
つまり、2n-1 - 1 ≡ 0 (mod 3)
であるので、

n が奇数であることは、2n-1 - 1 ≡ 0 (mod 3) となるような自然数 n が存在するための十分条件でもあります。


よって、n が奇数であることが、2n-1 - 1 ≡ 0 (mod 3) となるような自然数 n が存在するための必要十分条件であることが分かりました。

最初に導いたとおり、2n-1 - 1 ≡ 0 (mod 3)となることと、2n = 3m + 2 を満たすような整数 m が存在することは同値であるので、

n が奇数であることが、2n = 3m + 2 を満たすような整数 m が存在するための必要十分条件となるのです。

分かりましたでしょうか?

それでは。

↓↓合同式の素晴らしさ↓↓
19:17  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2008.11.10 (Mon)

11/8解答

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

問題1.船長様の命令です
問題2.二つのダイイング・メッセージ
前回提示した問題です。
「初項が 1 で公差が自然数dである等差数列の初項から第 n 項までの和を Sn とする。 n ≧ 3 のとき、次の問に答えよ。
(1) Sn = 94 となる n と d がちょうど一組ある。その n と d を求めよ。
(2) Sn = 98 となる n と d の組はない。その理由を述べよ。」
[2004 神戸大・文]

数列絡みの整数問題です。
発想もそれほど難しくはないと思います。
あとは、ケアレスミスをしないように、ただそれだけのことです。

(解答)
(1)
Sn = (項数)×{(初項)+(末項)}÷ 2
であり、(末項) = (初項)+(公差)×{(項数)-1}
であるので、
Sn = n{1+1+d(n-1)}/2 = n(2+dn-d)/2
ここで、Sn = 94 となるとき、
n(2+dn-d) = 188
188 = 22×47
であり、n,dはともに自然数であるので、
nと(2+dn-d)の組み合わせは、n ≧ 3 も考慮に入れて、
(n,2+dn-d) = (4,47),(47,4),(94,2),(198,1)
の4通りが考えられる。また、dは自然数なので、d ≧ 1 である。
ゆえに、2+dn-d ≧ 2+n-1 = 1+n > n
であるので、これを満たす(n,2+dn-d)の組は
(n,2+dn-d) = (4,47)
のみである。
このとき、
2+4d-d = 47
となり、
このとき、(n,d) = (4,15)
となり、これは条件に適合する。
以上より、
n=4,d=15

(2)(証明)
Sn = 98
のとき、
n(2+dn-d) = 196
となる、
196 = 22×72
であり、n,dはともに自然数であるので、
nと(2+dn-d)の組み合わせは、n ≧ 3 も考慮に入れて、
(n,2+dn-d) = (4,49),(14,14),(28,7),(49,4),(98,2),(196,1)
の6通りが考えられる。
d ≧ 1より 2+dn-d ≧ n であるので、
(n,2+dn-d) = (4,49),(14,14)
の2通りのみが考えられる。

(i) (n,2+dn-d) = (4,49) のとき
2+4d-d = 49
より、
3d = 47
ゆえに、d = 47/3 であるが、dは自然数であるので、これは不適。

(ii) (n,2+dn-d) = (14,14) のとき
2+14d-d = 14
より、
13d = 12
ゆえに、d = 12/13 であるが、dは自然数であるので、これは不適。

以上より、Sn = 98 となる n と d の組は存在しない。
(Q.E.D.)

とことん系の問題ですね。
それでは。


↓↓とことん or ひらめき?↓↓

21:10  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2008.11.08 (Sat)

11/8問題

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

問題1.船長様の命令です
問題2.二つのダイイング・メッセージ
初項が 1 で公差が自然数dである等差数列の初項から第 n 項までの和を Sn とする。 n ≧ 3 のとき、次の問に答えよ。
(1) Sn = 94 となる n と d がちょうど一組ある。その n と d を求めよ。
(2) Sn = 98 となる n と d の組はない。その理由を述べよ。
[2004 神戸大・文]


↓↓シンキング・タイム スタート!↓↓

18:06  |  整数-math  |  TB(0)  |  CM(1)  |  EDIT  |  Top↑

2008.11.04 (Tue)

11/3解答

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

問題1.船長様の命令です
問題2.二つのダイイング・メッセージ
(解答)
上からk枚目のカードが、一回のシャッフルによって、上から ƒ(k) 枚目に移動するとする。

ここで、ƒをm回合成して、
ƒ○ƒ○ƒ○・・・○ƒ(k) = k
となるとき、このmが2nであることを示せばよい。

ƒ(k) ≡ 2k (mod (2n + 1) )
であるので、
ƒ○ƒ○ƒ○・・・○ƒ(k) ≡ 2m k (mod (2n + 1) )

ここで、m = 2n
とすると、2m - 1 = (2n - 1)(2n + 1)
より、
2m - 1 ≡ 0 (mod (2n + 1) )
ゆえに、
2m ≡ 1 (mod (2n + 1) )
したがって、
ƒ○ƒ○ƒ○・・・○ƒ(k) ≡ 2m k ≡ k (mod (2n + 1) )

ゆえに、
ƒ○ƒ○ƒ○・・・○ƒ(k) ≡ k (mod (2n + 1) )
となる、mが存在し、m=2nのとき、上式が成り立つことから、
示された。
(Q.E.D.)

↓↓WWWwwwI↓↓

21:34  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2008.11.03 (Mon)

トランプのシャッフル

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

問題1.船長様の命令です
問題2.二つのダイイング・メッセージ
パラパラ・・・とトランプをシャッフルすることがありますよね?リフルシャッフルです。

あのシャッフルを、たとえば次のようにしましょう。
nは自然数です。

1. 2n枚のカードを、上からn枚のところで2つの山に分ける
2. 2つの山に分けられたカードを、それぞれの山の上のカードから順に重ね合わせる


このようなことです。


このとき、次の問題です。

「2n 枚のカードを 2n シャッフルすると、元の順番に戻ることを示せ」

それでは。

↓↓ヒンズー・リフル↓↓

22:11  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2008.10.27 (Mon)

位数の法則

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

問題1.船長様の命令です
問題2.二つのダイイング・メッセージ
今回も合同式です。
まず、これにおける位数というものから説明しましょう。

整数aと自然数pにおいて、

ae ≡ 1 (mod p )

となる最小の自然数eを、aの(mod p における)位数と呼びます。

例えば、mod 7 では、
2の位数は3,
3の位数は6
となります。


そして、次のような法則が成り立ちます。


~位数の法則~
mod p でのaの位数を e とする。
このとき、an ≡ 1 (mod p ) ならば、n は e の倍数
とくに、p - 1 は e の倍数

証明しましょう。

(証明)
e は ae ≡ 1 (mod p ) となる最小の自然数 ・・・(i)
また、
an ≡ 1 (mod p ) ・・・(ii)
とします。
ここで、n を e で割った商を m ,余りを r とします。
すると、
n = em + r (0 ≦ r ≦ e ) ・・・(iii)
と表せます。
(iii)を(ii)に代入して、
aem + r ≡ 1 (mod p )
つまり、
(ae)m ar ≡ 1 (mod p )

ここで、(i)より、
ar ≡ 1 (mod p )
でないといけません。

しかし、r は e より小さく、 (i)よりe は ae ≡ 1 (mod p ) となる最小の自然数であることから、
r = 0
しか可能性はありません。

すると、(iii)より、
n = em
となります。

とくに、フェルマーの小定理から、
ap - 1 ≡ 1 (mod p )
であるので、 n = p - 1
とおけば、
e は p - 1 を割り切ることがわかります。

以上より、位数の法則は示されました。
(証明終)


どうでしょう?
これは、とても便利な法則ですね。

今回はここまでです。

それでは。

↓↓China↓↓
21:03  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2008.10.25 (Sat)

合同式3

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

問題1.船長様の命令です
問題2.二つのダイイング・メッセージ
それでは、今日は合同式を利用する練習をしてみましょう。

「問.82999 + 52999 を 13 で割った余りを求めよ。」
このような問題が簡単に解けるところが、合同式のいいところですね。解答です。

(解答)
8 ≡ -5 (mod 13)
であるので、両辺を2999乗して、
82999 ≡ (-5)2999 (mod 13)
ゆえに、
82999 ≡ -52999 (mod 13)
移項して、
82999 + 52999 ≡ 0 (mod 13)

以上より、82999 + 52999 を 13 で割った余りは0である。

上は、8 + 5 = 13 であること、また、どちらも指数が奇数であり、等しいことから、簡単に導くことができたのですが、それではそうではなかったらどうなるのでしょうか?
考えてみましょう。

まず、これから。
「問.82999 + 52999 を 7 で割った余りを求めよ。」
どうなるでしょうか?

8 ≡ 1 (mod 7)
であることから、
82999 ≡ 12999 (mod 7)
よって、
82999 ≡ 1 (mod 7)

また、
5 ≡ 5 (mod 7)
25 ≡ 4 (mod 7)
125 ≡ 4・5 ≡ 6 (mod 7)
625 ≡ 6・5 ≡ 2 (mod 7)
3125 ≡ 2・5 ≡ 3 (mod 7)
15625 ≡ 3・5 ≡ 1 (mod 7)
である。

15625 = 56であるので、
56 ≡ 1 (mod 7)

ゆえに、
(56)499 ≡ 1499 (mod 7)
つまり、
52994 ≡ 1 (mod 7)

両辺に 55 をかけて、
52999 ≡ 55 (mod 7)

55 = 3125 ≡ 3 (mod 7)
であるので、
52999 ≡ 3 (mod 7)

以上より、
82999 + 52999 ≡ 1 + 3 = 4 (mod 7)

よって、
82999 + 52999 を 7 で割った余りは4である。

この解法だと、別に指数が一致していなくても、解くことができますね。
1と合同になるものを探し出すわけです。それをもとに計算をする、ということなのです。

ここで、思いませんか?今回はmod 7で56が1と合同になりましたが、もしも、指数がもっと大きくなってしまった時は、どうするのでしょうか?

前回までの記事を思い出しましょう。

フェルマーの小定理です。

この場合だと、5 は 7 で割り切れないので、
57-1 ≡ 1 (mod 7)
ということがすぐに分かりますね。


まあ、この場合は素数でないといけませんが。


今回はここまでです。

それでは。


↓↓合同式は黄金↓↓
17:46  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2008.10.24 (Fri)

ウィルソンの定理

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

問題1.船長様の命令です
問題2.二つのダイイング・メッセージ
今回は、「ウィルソンの定理」です。
内容は、次のようなものです。

「pが素数ならば、
(p - 1) ! ≡ -1 (mod p)
が成り立つ」


これもシンプルですね。これを証明する前に、次をご覧ください。

「a,bを整数とする。
1 ≦ a ≦ p - 1
の範囲の任意のaにおいて、
ab ≡ 1 (mod p)
となるbが必ず存在する」


これは、前回の基本定理からすぐに確認ができます。1 ≦ b ≦ p - 1 という条件を付け加えると、一つのaに対応するbはただ一つだけです。


例えば、p = 7 について考えると、

a
1
2
3
4
5
6
b
1
4
5
2
3
6


となります。ここで分かることは、1と6以外は、全て異なるaとbが対応しています。

一般的に、
a=bとなるとき、
a2 ≡ 1 (mod p)
より、
a2 - 1 ≡ 0 (mod p)
(a + 1)(a - 1) ≡ 0 (mod p)
ゆえに、a ≡ ±1 (mod p)のときに限ります。

よって、a = 1 , p - 1 のときは、a = b
それ以外の時は、a≠b で、a,bの組は、すべて異なります。二つの異なるaに、同じbが対応することはありません。


これを用いて、ウィルソンの定理を証明します。

(証明)
p=2のときは自明である。

p≧3のとき、
(p - 1) ! = (p - 1)(p - 2)(p - 3)・・・3×2×1

ここで、上に述べた事柄より、2から(p - 1)までの整数は、積が1とmod pで合同となる2整数の組同士に全てを組み替えることができるので、

(p - 1) ! ≡ (-1)×1×1×1×・・・×1 ≡ -1 (mod p)

よって、示された。
(Q.E.D.)



一応、例をあげておきましょう。

p=7のとき、

(7 - 1) ! = 6×5×4×3×2×1

= 6×1×(4×2)×(5×3)

≡ (-1)×1×1×1

≡ -1 (mod p)

ということですね。

分かりましたか?
それでは。



↓↓分かりました!↓↓
19:58  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2008.10.23 (Thu)

フェルマーの小定理

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

問題1.船長様の命令です
問題2.二つのダイイング・メッセージ
まず、補足ですね。

a,bを整数、nを自然数、ƒ(x)を整数係数多項式とし、a ≡ b (mod n)のとき、
ƒ(a) ≡ ƒ(b) (mod n)


が成り立ちます。

それでは、今回は「フェルマーの小定理」を証明しましょう。

内容は、次の通りです。

「p を素数とする。
aがpの倍数でないならば、
ap-1 ≡ 1 (mod p)
が成り立つ。」


さて、どうでしょうか?

これを証明する前に、次の定理を確認しておきましょう。

1次合同方程式の基本定理

「p を素数、 a は p の倍数ではないとする。このとき、以下のことが成り立つ。

(1)
{a,2a,3a,・・・,(p - 2)a,(p - 1)a}
は、 mod p で、全体として、
{1,2,3,・・・,(p - 2),(p - 1)}
と合同になる。

(2)
xについての合同方程式
ax + b ≡ 0 (mod p)
は一意的に解ける。ただし、bは整数とする。」


(1)は、集合A
A = {a,2a,3a,・・・,(p - 2)a,(p - 1)a}
としたとき、Aの中のどの2つも mod p では合同とはならない、ということです。

(証明)
(1)から証明する。
集合A
A = {a,2a,3a,・・・,(p - 2)a,(p - 1)a}
とする。

もしも、
ia ≡ ja (mod p)
となる、0 ≦ i ≦ j ≦ p - 1 があると仮定すれば、移行して整理すると、
(i - j)a ≡ 0 (mod p)
となる。
aはpの倍数ではないので、i - jがpの倍数となる。
ここで、
0 ≦ i - j ≦ p - 1
より、
i - j がpの倍数となるためには、
i - j = 0
でないといけない。
すなわち、
i = j

すなわち、Aのどの2つも合同でない。
ゆえに、Aは全体として、{1,2,3,・・・,(p - 2),(p - 1)}を並び替えたものとmod p で合同となる。(これは、aとpが互いに素であるという条件があれば、pが素数でなくとも成り立ちます。証明は同じ)

次に、(2)を証明する。
(1)より、Aの中には、mod p で1と合同になるものが、必ずただ1つのみ存在するので、条件を満たすどのようなaに対しても、
ac ≡ 1 (mod p)
となるような整数cが存在する。

よって、
ax + b ≡ 0 (mod p)
は、bを移項し、cをかけて、
acx ≡ -bc (mod p)
1x ≡ -bc (mod p)
x ≡ -bc (mod p)
と、一意的に解ける。

(Q.E.D.)

すぐに分かると思いますが、
ac ≡ 1となるようなcは、
0 ≦ c ≦ p-1
の範囲では、ただ1つしか存在しません。

それでは、本題へ参りましょう。
上の基本定理を踏まえての、フェルマーの小定理の証明です。



(証明)
{a,2a,3a,・・・,(p - 2)a,(p - 1)a}と{1,2,3,・・・,(p - 2),(p - 1)}はmod pで全体として合同であるので、それぞれの集合の要素を掛け合わせて、

a(2a)(3a)・・・(p-2)a(p-1)a ≡ 1×2×3×・・・×(p-2)(p-1) (mod p)
である。

ゆえに、
ap-1(p - 1) ! ≡ (p - 1) ! (mod p)

両辺から(p - 1) ! を引いて、

(ap-1 - 1)(p - 1) ! ≡ 0 (mod p)

ここで、pは素数であるので、pを素因数に含まない(p - 1) ! は、pで割りきれない。
つまり、(p - 1) ! と、pは互いに素である。 よって、両辺を(p - 1) ! で割って、


ap-1 - 1 ≡ 0 (mod p)

両辺に1を足して、

ap-1 ≡ 1 (mod p)

以上より、フェルマーの小定理は示された。
(Q.E.D.)

このように、証明できました。
分かりましたか?

意外と簡単ですね。

次回は、ウィルソンの定理です。

それでは。



↓↓フェルマーは天才!?↓↓



21:46  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2008.10.22 (Wed)

合同式2

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

問題1.船長様の命令です
問題2.二つのダイイング・メッセージ
 前回の続きといきましょう。

最後に残る証明を済ましてしまいましょう。(以下全て複合同順)

a,b,c,d,kを整数、nを自然数とし、a ≡ b (mod n) かつ、 c ≡ d (mod n) のとき、
・ a ± c ≡ b ± d (mod n)
・ ac ≡ bd (mod n)
・ kとnが互いに素の時、 ka ≡ kb (mod n) ⇔ a ≡ b (mod n)

(証明)
まず、a ± c ≡ b ± d (mod n) を証明する。
a ± c - b ± d = (a - b) ± (c - d)

a ≡ b (mod n) かつ c ≡ d (mod n) であるので、
a - b も c - d も n の倍数である。
よって、(a - b) ± (c - d) は n の倍数となる。

ゆえに、a ± c ≡ b ± d (mod n)


次に、ac ≡ bd (mod n) を証明する。
a ≡ b (mod n) かつ c ≡ d (mod n) より、整数 j,k,l,m を用いて、
a = jn
b = kn
c = ln
d = mn
とおける。
ゆえに、
ac - bd = jln2 - kmn2 = n2( jl - km )
以上より、ac - bd は n の倍数であるので、
ac ≡ bd (mod n)


最後に、 kとnが互いに素の時に、 ka ≡ kb (mod n) ⇔ a ≡ b (mod n) であることを証明する。
a ≡ b (mod n) ⇒ ka ≡ kb (mod n) は、既に証明されている。(前回の記事参照)

kとnが互いに素の時、ka ≡ kb (mod n) ⇒ a ≡ b (mod n) であることを証明する。

ka ≡ kb (mod n) であるので、整数l,mを用いて、
ka = ln
kb = mn
とおける。

ここで、kとnは互いに素であるので、aはnの倍数、また、bはnの倍数となる。

ゆえに、kとnが互いに素の時、ka ≡ kb (mod n) ⇒ a ≡ b (mod n)

以上より示された。
(Q.E.D.)

どうでしたか?
ちなみに、最後の命題において、「kとnが互いに素」という条件がなければ、ka ≡ kb (mod n) ⇒ a ≡ b (mod n) は偽ですね。
aとbがnの倍数でなくとも、kがnの倍数であれば、kaもkbもnの倍数になりますから。

分かりましたか?

今度は、「フェルマーの小定理」と、「ウィルソンの定理」を紹介しようと思います。

それでは。

↓↓剰余類↓↓
21:17  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2008.10.21 (Tue)

合同式

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

問題1.船長様の命令です
問題2.二つのダイイング・メッセージ
 次回からの準備として、今回は合同式の基本を書いておきます。

次の式をご覧ください。

a ≡ b (mod n)
(a,bを整数、nを自然数とする)


nを法にして、aとbは合同、ということを表しています。

a - b が n で割り切れる、という意味ですが、

「a と b は、 n で割った余りが等しい」

と考えた方が分かりやすいと思います。


例えば、
1 ≡ 3 (mod 2)
81 ≡ 0 (mod 9)
7 ≡ -1 (mod 8)
です。


合同式においては、次の事柄が成り立ちます。 (ここより以下は、全て複号同順です)


・ a ≡ a (mod n)
・ a ≡ b (mod n) ⇔ b ≡ a (mod n)
・ a ≡ b (mod n) かつ b ≡ c (mod n) ならば、 a ≡ c (mod n)

a ≡ b (mod n) かつ、kは整数、mは自然数のとき、
・ a ± k ≡ b ± k (mod n)
・ ka ≡ kb (mod n)
・ am ≡ bm (mod n)

c,dを整数とし、a ≡ b (mod n) かつ、 c ≡ d (mod n) のとき、
・ a ± c ≡ b ± d (mod n)
・ ac ≡ bd (mod n)
kとnが互いに素の時、 ka ≡ kb (mod n) ⇔ a ≡ b (mod n)



それぞれ証明していきましょうか。上から二つ目までは自明(その下も自明かとは思いますが)なので、省きます。

「a ≡ b (mod n) かつ b ≡ c (mod n) ならば、 a ≡ c (mod n)」
(証明)
a ≡ b (mod n)
より、
b - a = kn ( k は整数)とおける。

また、
b ≡ c (mod n)
より、
c - b = ln ( l は整数)とおける。

これらより、
c - a = (c - b) + (b - a) = ln + kn = (l + k)n
ゆえに、
c - aはnの倍数であるので、
a ≡ c (mod n)
である。
(Q.E.D.)

「a ≡ b (mod n) かつ、kは整数、mは自然数のとき、
・ a ± k ≡ b ± k (mod n)
・ ka ≡ kb (mod n)
・ am ≡ bm (mod n)」

(証明)
まず、与えられた条件のもとで、a ± k ≡ b ± k (mod n)を証明する。
(a ± k) - (b ± k) = a - b
a ≡ b (mod n)より、a - bはnで割り切れる。
ゆえに、(a ± k) - (b ± k)もnで割り切れるので、a ± k ≡ b ± k (mod n)である。

次に、ka ≡ kb (mod n)を証明する。
ka - kb = k(a - b)
a - bはnで割り切れるので、k(a - b)もnで割り切れる。
ゆえに、ka ≡ kb (mod n)である。

最後に、am ≡ bm (mod n)を証明する。
am - bm = (a - b)(am-1 + am-2b +・・・+ abm-2 + bm-1)
であるので、 am - bmはnの倍数。
ゆえに、am ≡ bm (mod n)
(Q.E.D.)

今日はここらへんでご勘弁願います。
それでは。

↓↓剰余類↓↓
21:28  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2008.10.15 (Wed)

Prime Number

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

問題1.船長様の命令です
問題2.二つのダイイング・メッセージ
 素数が無限にあるということは、既知の事実であると思います。
 一応証明してみましょう。この証明は、後で述べる事柄と関連しておりますので、ご注意を。

<素数が無限個あることの証明>

背理法で証明する。
素数が有限個しかないと仮定すると、最大の素数Pというものが存在する。
ここで、
P!=1×2×3×・・・×Pであるので、
P!は全ての素数を因数に持つ。
ここで、
Q=P!+1となる数Qを考えると、Qは、どの素数で割っても1余る数である。
つまり、Qは、どの素数も約数に持たない。よって、Qの約数は1とQのみ。
したがって、
Qは素数である。
明らかに
Q>P
であるので、
これはPが最大の素数であることに矛盾

よって、素数は無限個ある。
(Q.E.D.)

さて、それではこの証明を踏まえて、次のことを考えてみましょう。

素数は、無限に存在するということは、今、上で証明されました。
しかし、その分布というものは、数が小さい間は密ですが、数が大きくなっていくにつれ、疎ら(まばら)になっていきます。
素数でない自然数は、「合成数」と言いますが、ある自然数からある自然数までの間は、素数は全く現れない、どの数も合成数である、という区間が存在します。
例えば、
90,91,92,93,94,95,96
という連続した7数は、全て合成数です。(89及び97は素数です)

90 = 2×32×5
91 = 7×13
92 = 22×23
93 = 3×31
94 = 2×47
95 = 5×19
96 = 25×3

といった具合に素因数分解ができます。

このように、合成数ばかりが続くような区間を、
「素数砂漠」と呼ぶことにします。

さて、ここで、次のことを考えます。

素数砂漠は、いくらでも長いものを作ることが可能です。(無限ではありません!

問題です。

「いくらでも長い素数砂漠が存在することを示せ」
この場合の「いくらでも長い」とは、「無限とまではいかないが、有限の範囲内でとてつもなく長い」といったようなニュアンスで考えてください。
先ほどの証明の考え方と基本的には同じです。

(証明)
ある自然数をNとする。
N!という数は、
2~Nまでの自然数1,2,3,4,・・・,N
で割りきることができる、合成数である。

ここで、
N!+2において、

N!は2の倍数
2は2の倍数

であるので、

N!+2は2で割りきることができる合成数である。

次にN!+3は、同様に考えると、3で割りきることができる合成数である。

N!+4は、4で割りきることができ、

N!+5は、5で割りきることができる。



このように考えていくと、

N!+2,N!+3,N!+4,・・・,N!+(N-1),N!+N

は、すべて合成数である。


これは、長さN-1の素数砂漠を表している。

すなわち、Nを有限の範囲で大きくすれば大きくするほど、素数砂漠の長さはいくらでも大きくなっていく。

よって、

いくらでも長い素数砂漠が存在する。


ということは、
例えばN=1億とでもすると、9999万9999個の合成数が連続した素数砂漠が存在することがすぐに確認できるわけです。

「素数は無限にある」ということと、「いくらでも長い素数砂漠が存在する」、一見同時に存在できないような命題のようですが、どちらも、同時に成り立っているのです。

「無限」と「有限」の世界は、このように奥が深いのです。

そして、「素数」の世界も、奥が深いのです。

それでは。


↓↓素数P↓↓
21:10  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2008.09.17 (Wed)

算数の問題 解答

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

問題1.船長様の命令です
問題2.二つのダイイング・メッセージ
前回の問題ですね。ゾロ目の問題です。

次の条件を満たす□(1以上1000以下の整数とします)はいくつあるでしょう。


条件:□の倍数の中に『各位の数字がすべて同じ整数(例えば、33や777といったもの)』が存在しない


それでは、解答です。

(解答)
(□をXとおいて考えます)
条件より、Xは1以上1000以下の自然数

Xの倍数を kX (kは整数)とおく。


kXが「ゾロ目」(各桁の数がすべて同じ)であるとき、それは、1以上9以下の整数aを用いて、

kX=11・・・11a

と表すことができる。


ここで、11・・・11は1がm個(mは自然数)並んでいるものとする。

このとき、11・・・11は明らかに2の倍数でも5の倍数でもない。

よって、Xが2の倍数又は5の倍数であるとき、kXがゾロ目になるためには、aはkXと同じだけ2又は5を因数(素因数)に含まなければならない。

ここで、例えばX=23=8のとき、11・・・11aは8の倍数となり、これを満たすaはa=8ただ一つのみ存在するが、
X=24=16のとき、11・・・11aは16の倍数となりえない(∵aは1以上9以下の整数)

よって、Xが16の倍数のとき、Xの倍数kXはゾロ目にはなりえない。


同様に考えて、Xが25(=53)の倍数のとき、Xが10(=5・2)の倍数のときも、
Xの倍数kXはゾロ目にはなりえない。



ここで、Xが2の倍数、5の倍数のときは上で吟味したが、他の倍数の場合を考える。


次の数列を考える。(bは2の倍数でも5の倍数でもない自然数)

1,11,111,1111,11111,・・・,11・・・11(1がb+1個並ぶ)

上の数列は、全部でb+1個の項が並んでいる。

上のb+1個の数をそれぞれを b で割った余りを考えると、

鳩ノ巣原理より、少なくとも一組は b で割ったあまりが等しい二数の組が存在する。

例えば、
その二数を
11・・・11・・・11と11・・・11
であるとする。

このとき、この二数の差は必ず b で割りきることができる。

この二数の差は、

11・・・11・・・11 - 11・・・11 = 11・・・1100・・・00

となる。

11・・・1100・・・00 = 11・・・11×100・・・00

であるが、100・・・00と b は、互いに素である。
(∵bは2の倍数でも5の倍数でもない自然数)

よって、上の数が b で割り切れることより、11・・・11は b の倍数であることが分かる。

つまり、2の倍数でも5の倍数でもない自然数の倍数は、必ずその中にゾロ目であるものを含む。


以上より、
1以上1000以下の整数の集合をU
Uの部分集合で、
16の倍数である整数の集合をA
25の倍数である整数の集合をB
10の倍数である整数の集合をC
とすると、求めるものは

n(A∪B∪C)
=n(A) + n(B) + n(C) - { n(A∩B) + n(B∩C) + n(C∩A) } + n(A∩B∩C)

=170

となる。

よって、条件を満たすX(□)は、
170個



どうでしょう?分かりましたか?
それでは。


↓↓分かりました↓↓

23:12  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2008.09.16 (Tue)

算数の問題

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>

問題1.船長様の命令です
問題2.二つのダイイング・メッセージ
数学と言っても差し支えありませんが。
なので、数学の問題として扱います。

次の条件を満たす□(1以上1000以下の整数とします)はいくつあるでしょう。


条件:□の倍数の中に『各位の数字がすべて同じ整数(例えば、33や777といったもの)』が存在しない



1000以下の自然数nの倍数にゾロ目がないときのnは全部でいくつあるでしょう、とのことです。

それでは。

↓↓難問です↓↓
22:42  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑

2008.08.27 (Wed)

素数

〔注意事項〕をご覧ください。(携帯の方はこちら

交流掲示板<http://penpenpensama.hp.infoseek.co.jp/Go.html>
さて、素数についてです。
次の問題をご覧ください。

2009は素数か?

さて、素数だと思っても、本当に素数なのか?素因数分解できないか?と思いますね。
以前紹介した、P≠NP予想でもあるように、今のところ(おそらく将来も発見されてはいないでしょうが)、素因数分解には便利な公式などがありませんから、地道に調べていくしかありません。
ん?なんだか下のやり方をしらなくてもすぐに答えが出せそうな・・・
今は何も考えずに、下をお読みください。

しかし、地道でも地道なりに、やり方はあります。

1~2009までの素数を調べる必要がありません。

2009が素因数分解できるとしたら、
それは2009=a×b(aは素数、bは整数)の形で表すことができます。
a≦bだとしても一般性を失わないません。すると、これは
「aは√2009以下」ということを表しています。
442<2009<452
であるので、
44<√2009<45
です。
よって、a≦45だということが分かります。
45以下の素数というと、
2,3,5,7,11,13,17,19,23,29,31,37,41,43
ですので、これらの素数が2009の素因数であるかどうかを調べるだけでOKです。

すると、7で割ることができることがわかります。
2009=7・287
(ここでも何も考えずに下へ進む!)
287は17の二乗である289よりも小さいので、2~13の素数を調べればよいわけです。
すると、また7で割れ、
2009=7・7・41
41は素数であるので、これで終わりです。

2009=7・7・41であるので、2009は素数ではない。

(例題が悪かったですね。
お詫びにもう一題。
2003が素数であるのか、合成数であるのか、お考えください。)

このように、
ある整数nが素数であるのか合成数であるのかを判断するには、
√n以下の素数を、nが素因数に持つか否かで判断すればよい。

ということになります。

続いては、エラトステネスの篩(ふるい)です。
これは、
ある整数n以下の素数をすべて見つけ出すための方法です。
基本的に考え方は上と同じです。
nまでの整数をリストアップしていき、√n以下の素数の倍数(1倍したものは除く)リストから削除していきます。すると、そのリストに残っているものは、すべて素数です。
理由は言うまでもありませんね。上で言った事柄からすぐに分かります。

素数には、もっと面白い性質というものがたくさんあります。
一度、足を踏み入れてはいかがでしょうか。

↓↓素数ってすごいかも↓↓
21:51  |  整数-math  |  TB(0)  |  CM(0)  |  EDIT  |  Top↑
 | BLOGTOP | 
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。