アットランダム≒ブリコラージュ

フェルマーの小定理（第二形式）

有名なフェルマーの小定理の証明・・・^^v

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Fermat.html　より Orz〜
「フェルマーの小定理

ｐ を素数，ｘをｐで割り切れない整数とする。 このとき，ｘ^(ｐ−１)−１はｐで割り切れる。即ち，

ｘ^(ｐ−１) ≡１ (mod ｐ)

が成立する。

フェルマーの小定理は次の形（第二形式）で表されることもあります。
上の形を第一形式ということにします。

ｐ を素数，ｘを整数とする。 このとき，ｘ^ｐ−ｘはｐで割り切れる。即ち，

ｘ^ｐ ≡ｘ (mod ｐ)

が成立する。

第一形式のフェルマーの小定理の両辺にｘを掛けたのが，第二形式ですから，第一形式から，第二形式が導かれます。また，ｘがｐで割り切れない場合，ｘにはｐを法とした逆元ｙが存在します。このｙを第二形式の両辺に掛けると，第一形式が得られます。
以上から，第一形式と第二形式が同値であること示されました。

(* ここはよく分からないわたし...^^;...)

フェルマーの小定理の証明
　フェルマーの小定理の証明は色々あります。ここでは２項定理を使った証明を紹介します。

まず，次の補助定理を証明します。


（補助定理）　ｐを素数，ａ，ｂを整数とすると，

（ａ＋ｂ）ｐ ≡ ａｐ＋ｂｐ (mod ｐ)


が成立する。

証明

　２項係数 pCi=p(p-1)* ・・・*(p-i+1)/i ! の式の形を注意すると，これは，i=1，．．．p-1 に対して，ｐはpCiを割り切ることが分かります。実際 i !＝１・２・．．．i はｐと互いに素ですから，分子の内，(p-1)* ・・・*(p-i+1)を割り切ります。従って，pCiのｐはpCiに実際に現れ，従ってｐの倍数になります。従って ，２項展開
（ａ＋ｂ）^ｐ ＝ ａ^ｐ ＋pC1ａ^(ｐ-1)ｂ^1 ＋pC2ａ^(ｐ-2)ｂ^2 ＋pC3ａ^(ｐ-3)ｂ^3 ＋．．．＋ pC(p-1)ａ^1ｂ^(p-1) ＋ｂ^ｐ
の右辺の中間項はすべてｐで割り切れます。従ってこの両辺をｐを法として考えれば，求める式が得られます。（証明終）

上の補助定理で，ａ＝１，ｂ＝１と置くと，

２^ｐ＝（１＋１）^ｐ ≡ １^ｐ＋１^ｐ ≡１＋１≡２(mod ｐ)

が得られます。また，ａ＝２，ｂ＝１と置くと，

３^ｐ＝（２＋１^）ｐ ≡ ２^ｐ＋１^ｐ ≡２＋１≡３(mod ｐ)

が得られます。以下同様にして，任意の正整数に対して，

ｎ^ｐ≡ｎ(mod ｐ)

が得られます。

更に，（-１）^ｐ≡-１(mod ｐ)が任意の素数に対して，成立します。実際，ｐ＝２のときは　(-１)^2≡１(mod ２)で成立します。更に，ｐ＞２なら，ｐは奇数ですから，
（-１）^ｐ＝-１が成立します。以上から，全ての整数ｎに対して

ｎｐ≡ｎ(mod ｐ)

が成立することが分かります。　　　　　　　　　　　　　　　　」

わかりやすい♪

「応用：フェルマーの素数判定
フェルマーの小定理は，色々なところで理論的根拠として良く使われますが，数値的な応用もあります。それはフェルマーの小定理の対偶を使った，素数判定法です。次はフェルマーの小定理の対偶です。

ｎ，整数，ａをgcd(ａ,ｎ）＝１となる整数としたとき，
ａ^ｎ-１ ≡１ (mod ｎ)

とならなければｎは合成数である。

例えば，２^２３0≡６７ (mod ２３１)　ですから，２３１は合成数であることが分かります。
更に，２^１２０９0≡９８０１ (mod １２０９１)　ですから，１２０９１は合成数であることが分かります。

全ての合成数が上の方法で判定することはできません。例えば，２９３４１はｇｃｄ（ａ,２９３４１）＝１となるａに対してａ^２９３４０≡１(mod ２９３４１）となります。しかし，実は，２９３４１は合成数です。ですから，この合成数は上の判定法では，合成数であるとは判定してくれません。
合成数で，上の判定法では判定できない合成数をカーマイケル（Carmichael）数と言います。このような数は無限にあることが1992年に証明されました。・・・」

対偶は真だけど...上の式を満たすものは素数であることは真じゃない。
だって...素数なら上の式を満たすことは...合成数は満たさないことと同値じゃないから...^^;
カーマイケル数ってたまに見かけますが...いずれ調べてみたいと思います♪

画像：ピエール・ド・フェルマー
www.isis.ne.jp/mnn/ senya/senya0435.html　より Orz〜

2909：(5^n-5)/205 が正整数になる最小の n

問題2909・・・http://blog.livedoor.jp/enjoy_math/archives/cat_50002692.html　より Orz〜

(5^n-5)/205 が正整数になる最小の n を求めよ。



































解答

・わたしの

(5^(n-1)-1)/41 で考えても同じ。
フェルマーの定理から...5^40≡1 mod.41
もし、n-1<40以下のものがあるとしたら,,,
40 の約数のはず・・・つまり...1,2,4,5,8,10,20
なぜなら...5^m≡1 なら、(5^m)^(40/m)≡1 のはずだから...
5^1≡5
5^2≡25
5^4≡25^2≡10
5^8≡10^2≡18
5^10≡18*25≡40
5^20≡40^2≡1
ビンゴ♪
つまり...n=21 のときが最小 ^^v

2908：完全数は連続する数の和で表わされる

問題2908・・・http://blog.livedoor.jp/enjoy_math/archives/cat_50002692.html　より Orz〜

「任意の完全数は、連続する自然数の和で表すことができる。」

ことを証明せよ。




















































解答

上記サイトより Orz〜

偶数の完全数はメルセンヌ素数（メルセンヌ数のうち、素数のもの）と一対一対応がついていて、特に以下のような関係式がオイラーによって証明されています。

「全ての偶数の完全数に対し、あるメルセンヌ素数 M が存在し、
　M(M+1)/2　と表わされる。」

これは１からＭまでの連続自然数和そのものですから、直ちに定理の正しさが確認できます。
・・・
次に、奇数の完全数について。
一般に奇数は、0以上の整数mを使って2m+1と表すことができるので、m+(m+1)とすればこれは連続自然数和です。

従って奇数に関しては明らかなんですが、注意すべきこととして、奇数の完全数は未だひとつも見つかっていません。そもそも存在するのか、しないのかもわかっていない未解決問題です。


なるほど♪

* メルセンヌ素数：M=2^n-1
M(M+1)/2=2^(n-1)*(2^n-1)
これが素数なら...
約数の和＝(1+2+2^2+・・・+2^(n-1))*(1+2^n-1)
=(2^n-1)*2^n
=2*(M(M+1)/2)
で成り立ってる♪

2907：13日の金曜日

問題2907・・・http://blog.livedoor.jp/enjoy_math/archives/cat_50002692.html　より Orz〜

13日の金曜日は毎年必ずやってくるでしょうか？
























































解答

・わたしの

31/7≡3
28/7≡0
31/7≡3
30/7≡2
31/7≡3
30/7≡2
31/7≡3
31/7≡3
30/7≡2
31/7≡3
30/7≡2
31/7≡3

3
3+3=6
6+2=1
1+3=4
4+2=6
6+3=2
2+3=5

8月までに必ずあることになる。
うるう年の場合...
3
3+1=4
4+3=0
0+2=2
2+3=5
5+2=0
0+3=3
3+3=6
6+2=1
1+3=4

10月までに必ずあることがわかる。

神様の作品...ラマヌジャン

たしかに神秘的だ♪
人間の頭脳から...産まれたこと自体が信じられないような怪奇な式...^^;
これって証明されてるんでしょうか・・・？
e とか π とかの本質（繋がり/連関）に気付いてたとしか思えないですよね...

画像：Junko先生のコロキウム室 http://www.junko-k.com/collo/collo245.htm#1798　より K.F.さんご提供の記事 Orz〜

画像：ラマヌジャン
https://www.toyokeizai.net/life/column/detail/AC/32f3113590a5e3f018dc37ec20df7402/page/5/　より Orz〜

http://blog.goo.ne.jp/traumeswirren/e/096309231eef709a79a49f85d5925613　より Orz〜
「・・・例を挙げましょう。５つの豆を山に分けるやり方としては、次のように７とおりあります。

　○｜○｜○｜○｜○
　○○｜○｜○｜○
　○○｜○○｜○
　○○○｜○｜○
　○○○｜○○
　○○○○｜○
　○○○○○

同じように４つの豆なら５とおり、６つの豆なら11とおりになります。こういうのを分割数といって、次のような数列ができます。

　１、２、３、５、７、11、15、22、30、42……

つまり10個の豆があれば山の作り方は42とおりあるということです。100個の豆だと……190,569,292と、２億とおり近くあるんですね。別にこの数字自体は大きいというほどのことでもなく、２の28乗よりも小さい（つまり２、４、８、16、32……という数列の28番目よりも小さい数字だということです）んですが、問題は分割数の数列を予測することが全くできなかった（つまり一般式が見つけられなかった）んです。上の５つの豆のように山の分け方のルールはなんとなく見えても、一般式となると多くの偉大な数学者たちもお手上げだったようです。……で、ラマヌジャンは (画像) ような式を考えました。・・・
じゃあ、もっとすごい例をお見せしましょう。
(画像)
バカなことをって思うでしょうね。１から３まで足したって６になるし、10まで足せば55になるのは常識、それを無限に続けたらマイナスになるなんて、ちょっとどうかしてるんじゃないの？って。この式をインドからの手紙で見せられたイギリスの大学教授たちもそう思いました。ところがリーマン予想と密接な関係をなしているゼータ関数の表現としてはこれは十分意味のある、いやもしかすると∞無限大なんてものよりこちらの方が自然に根ざした解答なのかもしれないんです。しかし、これまた独力でそんなことを発見する頭脳って。……孤高の天才ってよく使われる言葉ですが、実際にその名前に値する人はあまりいないと思います。」

http://www.aa.alpha-net.ne.jp/t2366/すべてナマギーリ女神のおかげなんだ.htm　より Orz〜
「ラマヌジャンは友人から数学の非凡さ、その発想の由来を尋ねられたとき、こう答えたという。「信じられないかもしれないが、すべて毎日お祈りしているナマギーリ女神のおかげなんだ」と。そう答えられた友人も信じられなかっただろうが、少年ラマヌジャンは、意外にも母親譲りの信仰深さで、本気でそう思っていた。というのは、ラマヌジャンの母親は並大抵ではないナマギーリ女神に対する信仰を抱いていた。母親には長い間、子供が生まれなかったので、毎日欠かさず女神に祈りを捧げていたが、彼女の話によると、ラマヌジャンが生まれたのはこのナマギーリ女神のおかげなのだった。ある日のこと、彼女は突然トランス状態に陥り、この女神の宣告を聞いた。「コーマラタンマルは子供を生み、余によって特別の祝福を受けるであろう」そしてラマヌジャンが生まれた、と。・・・名前の由来は次のようなことらしい。ヒンドゥー信仰の衰えがきざしていた12世紀、ヒンドゥー復活をもたらしたラーマーヌジャンなる聖者が生まれたが、このラーマーヌジャンと生まれた日が占星術的に一致していた。そこでラマヌジャンと名づけた。その意味は、ラーマー神の弟ということである。
とにかくラマヌジャンは信仰厚き南インドのドラヴィダ人バラモンの社会に生まれたのであった。だからといって豊かであったわけではなく、経済的には非常に貧しく、学校も奨学金でやっと行けたという環境にすぎなかったが、インドの伝統に従ってそれでもバラモンはバラモンだった。バラモンは人口の３％ほどしかいないそうであるが、誇り高き精神的貴族であり、修行者であり、不浄を嫌う高潔な菜食主義者でもある。
その赤貧洗うがごときではあったが誇り高いバラモン社会がラマヌジャンの孤高の精神を育てた。少年ラマヌジャンはとても感じやすく、頑固で、「エキセントリックだった」という。なにしろ、生後3年間というもの、ラマヌジャンは一言も口を開かなかったという伝説がある。そのため父親はこの子はオシではないかと思い、ラマヌジャンにタミール語を書くアチャラ・アビシェカムという訓練をしたというし、学校へ行き始めてからも、登校拒否を繰り返した。嫌なものはやりたくないという彼の頑固で「エキセントリックな性格」は生まれつきで、表面的には官立高校に入ってからも、数学を除き、あらゆる必須科目をさぼる「不良学生」に過ぎなかった。むろん学校へ通うなどということよりも、空想、思考、瞑想といったものを好んだからである。その代わり、人一倍感じやすいラマヌジャンは、学校の成績が悪かったり、奨学金を取り消されたときなど、その恥辱のあまりなんども家出していた。それからまた、忘れた頃にのこのこと家に戻ってくるのである。英語のテストでは3点しか取れないときもあったが、数学では抜群の成績を残したラマヌジャンの唯一の心の支えは、この数学であった。そして、16歳のときカーの「数学基礎要覧」を手にしてから、その才能は一挙に花開いた。彼が持ち歩いていたノートには、誰も知らない公式、いや自分が発見した不思議な公式が次々に書き上げられ、後にその公式群の奇妙さ、不思議さが世界の数学界を驚かせることになるのである。その頃、ラマヌジャンが勤めていたのは、マドラスの港湾信託局だった。すでに彼は「インド数学協会誌」に「ベルヌーイ数の諸性格」という処女論文をだしていたが、それだけが唯一の業績であって、港湾局へ就職する前は書く紙にこと欠くような失業者であった。・・・そして25歳になっていた彼は、ある日、一面識もないイギリス数学界の大御所ハーディ宛てに一通の手紙を書いたのだった。
「拝啓。自己紹介させていただきます。私はマドラス港湾局経理部にて、年収２０ポンドで働いている一事務員でございます。23歳くらいで(実際は25歳----注）通常の学校課程は終えましたが、大学には行っておりません。学校を出た後、余暇を数学研究に励んでまいりました。正規の教育は受けていませんが、独学で研究し、発散級数に関するいくつかの成果は、当地では驚くべきと形容されています。」
こんな書き出しで次には数学公式がずらずらと並べられている手紙が、ハーディの目に留まったのは、世紀の不思議のようなものである。ハーディが通常の数学者だったなら、これだけ読まれただけで手紙は捨てられる運命にあっただろう。天才数学者ラマヌジャンも生まれなかった。ところがハーディは並みの数学者、並みの洞察家ではなかったのである。彼も最初は手紙に書き並べられた奇妙な公式をみて、タワゴトと思ったのだが、次の瞬間、「これらの公式がインチキだとすれば、いったい誰がそれを捏造するだけの想像力をもっているだろうか？」と思い直し、友人リトルウッドと１週間かけて隅々まで検討したのであった。そして得られた結果が「偽者ではない。これは本物の天才だ！」というものであった。こうして無名の天才ラマヌジャンが発見されたのだが、こんな経過そのものが「世にも不思議な物語」である。一通の手紙がラマヌジャンの運命を変えた----こういう経過を見ると、ラマヌジャンのいう「すべてナマギーリ女神のおかげ」という言葉も真実味を帯びてくるというものだ。・・・」

いつも素敵な話だなあって嬉しくなります♪