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

平方剰余を考える由来...

平方剰余の相互法則をガウスは生涯に７通りもの方法で証明したと言われていますが…

画像：http://www.aprender-mat.info/japones/historyDetail.htm?id=Gauss より 引用 Orz〜

https://ja.wikipedia.org/wiki/平方剰余の相互法則 より Orz〜

「ガウスはこの法則に対して生涯で7つの異なる証明を与えた。その一つの動機は、三次や四次の相互法則を証明することにあった。現在では200近くもの証明が知られている。しかし、どれもそれほど簡単ではない。三次や四次の相互法則は、ヤコビ、アイゼンシュタインによって独立に証明された（1844年にアイゼンシュタインが証明を公表）。より高次のまた一般的な代数的整数における一般的な相互法則の証明は（ヒルベルトの第9問題）、高木貞治やエミール・アルティンによってなされた。」

そもそもこの平方剰余を考える切っ掛けってのがよくわからなかったのよ…?

以下のサイトからすると…

どうも、２次合同方程式をとくために考えることとなったみたいなのね ^^…?

http://akademeia.info/index.php?n%BC%A1%B9%E7%C6%B1%CA%FD%C4%F8%BC%B0より 引用 Orz〜

「

法が素数の2次合同式 

奇素数pを法とする2次方程式 http://s-akademeia.sakura.ne.jp/mimetex/mimetex.cgi?x^2~+~ax+~b~%5cequiv~0~%5cpmod{p} について考えてみる。

法が奇素数の2次合同式 

この2次合同式において、もしaが奇数ならば、pを奇素数として、合同式を次のように修正できる。

http://s-akademeia.sakura.ne.jp/mimetex/mimetex.cgi?x^2~+~(a+p)~x~+~b~%5cequiv~%5c,~%5cpmod{p}
http://s-akademeia.sakura.ne.jp/mimetex/mimetex.cgi?x^2~+~2ax~+~b~%5cequiv~%5c,~%5cpmod{p}　

（∵xの係数は偶数であると仮定しても一般性を失わないから）

http://s-akademeia.sakura.ne.jp/mimetex/mimetex.cgi?(x+a)^2~+~b-a^2~%5cequiv~%5c,~%5cpmod{p}

ゆえに、2次合同式の問題は奇素数pに対して、次の合同式を解く問題に帰着させられる。

http://s-akademeia.sakura.ne.jp/mimetex/mimetex.cgi?x^2~%5cequiv~a~%5c,~%5cpmod{p}

なお、この合同式が解を持つとき、aは法pの平方剰余であるという。

また、解を持たないとき、aは法pの非平方剰余であるという。」

but…

上の内容(式の２行目と最後の式でいいこと)に着いて行けないわたし…

^^;;…?

↑

鍵コメT様からわかりやすい解説を頂戴しました♪

↓

・鍵コメT様からのもの Orz〜

奇素数pを法として，
x^2+ax+b≡0⇔x^2+(a+p)x+b≡0.
この2式の一方は，xの係数は偶数．それを改めて2aとおき，
(x+a)^2≡a^2-b.
このように，奇素数pを法とする1元2次の合同式は，
x^2≡kを解くことに帰着されます．

*なるほど納得できました☆〜m(_ _)m〜☆

原始根を使ったウィルソンの定理の証明の意味がわかった…^^

ウィルソンの定理のエレガントな証明はすでにアップしてますが…

Wikiに載ってる証明が簡単ですね ☆

原始根に慣れて来てやっとわかったり♪

画像：https://en.wikipedia.org/wiki/Joseph-Louis_Lagrange より Orz〜

*彼が最初に証明されたようですけど…

どうやってされたのか我知らず…^^;

https://ja.wikipedia.org/wiki/ウィルソンの定理 より Orz〜

「ウィルソンの定理は初等整数論における素数に関する次のような定理である。

p が素数ならば (p-1)! ≡ -1 (mod p) が成り立つ。p>1の場合、逆も成り立つ。

p が大きくなるにつれて計算量が膨大になるため、素数かどうかを判定するために用いるには実用的ではない。

証明

p = 2 の場合は成り立つので、以下pは奇素数とする。

pは素数だから法pに関する原始根aが存在する。このとき、フェルマーの小定理より、

aは原始根だから、a¹, a², … ,a^p-1(≡1)はそれぞれpを法として還元すると、1, 2, … ,p-1の並べ替えである。よって、

となる。一方、

が成り立つ。

b=a^p(p-1)/2とおくと、b² ≡ 1 (mod p) だからb ≡ ±1 (mod p) である。

示したいのはb ≡ -1 (mod p) なのでb ≡ 1 (mod p) と仮定して矛盾を導く。

aは原始根だから、フェルマーの小定理より、p(p-1)/2はp-1で割り切れる。

ゆえにp/2は整数となるが、これはpが奇数であることに反する。Q.E.D.」

これよりも、以下のサイトのものの方がわかり易いですね♪

http://mathtrain.jp/isuu より 引用 Orz〜

*原始根の定義が r^(p-1)≡1　mod p 

・・・p-1乗で初めてこれを満たす数が原始根 r

= 原始根 rは、p-1が最小の乗数になる数なので...

r^m≡1 なら、mはp-1の倍数なのね ^^

*ルジャンドルさんが証明した方法も見つけたのでまたいずれ ^^

循環小数の性質…☆...平方剰余の相互法則とルジャンドル記号の威力…☆

平方剰余の相互法則とルジャンドル記号の具体的な使い方を...

以下のサイトからお勉強 Orz〜^^☆

http://tsujimotter.hatenablog.com/entry/2014/04/08/212954 より 引用 Orz〜

「《定理１》

p を2, 5 以外の素数としたとき、循環小数 1/p は (p-1) 桁で循環する。また、その循環節の長さは(p-1) の約数となる。」

これは、1/p=m(循環節e)/99…99(e個の9)

10^e-1=p*m

10^(p-1)≡1　mod p (pは10と互いに素) なので、

循環節e=p-1 or p-1の約数である可能性までは言えますね…^^

http://tsujimotter.hatenablog.com/entry/2014/04/08/213119 より 引用 Orz〜

ここからが面白い☆

ですね ^^

これは…

なるほど!!

ここから、平方剰余の相互法則と言われる以下の法則を駆使していくわけね…

画像：http://sci-fi.blog.jp/archives/16383256.html より 引用 Orz〜

https://ja.wikipedia.org/wiki/平方剰余の相互法則 より Orz〜

「この法則は、レオンハルト・オイラーによって予想され、カール・フリードリッヒ・ガウスによって証明された（ガウス日誌によれば、1796年4月8日。発表されたのは1801年の『整数論』において）。ガウスはこの法則に対して生涯で7つの異なる証明を与えた。その一つの動機は、三次や四次の相互法則を証明することにあった。現在では200近くもの証明が知られている。しかし、どれもそれほど簡単ではない。三次や四次の相互法則は、ヤコビ、アイゼンシュタインによって独立に証明された（1844年にアイゼンシュタインが証明を公表）。より高次のまた一般的な代数的整数における一般的な相互法則の証明は（ヒルベルトの第9問題）、高木貞治やエミール・アルティン（ドイツ語版、英語版）によってなされた。（アルティン相互法則を参照）」

*p は mod 8 で、1,3,5,7だから…^^

*Pは　mod 5 で、1,2,3,4 で…

x^2-p≡0　mod p

を満たすxがあるとき、(p/5)=1

だから…^^

*8m±1=5n±1

8m+1=5n+1・・・40k+1

8m+1=5n-1・・・40k+9

8m-1=5n+1・・・40k+31

8m-1=5n-1・・・40k-1

*8m±3=5n±2

8m+3=5n+2・・・40k+27

8m+3=5n-2・・・40k+3

8m-3=5n+2・・・40k-3

8m-3=5n-2・・・40k+13

ね ^^

*これすなわち、p を40で割った余りが1,3,9,13,27,31,37,39 のいずれかのものは、10を原始根として持たない…逆に、(5),7,11,(15),17,19,21,23,(25),29,33,(35) のものは、10を原始根として持つといえるわけね ^^

当然、2,5は10を原始根として持たない…

*but…

7,11が10を原始根として持たない理由が説明できないなぁ…^^;…?

p-1>10のときだけのよう…?

↓

http://www.freeml.com/bl/8882569/79856/ より 引用 Orz〜

「

p = 2 ; 1

p = 3 ; 2
p = 5 ; 2 3
p = 7 ; 3 5
p = 11 ; 2 6 7 8
p = 13 ; 2 6 7 11
p = 17 ; 3 5 6 7 10 11 12 14
p = 19 ; 2 3 10 13 14 15
p = 23 ; 5 7 10 11 14 15 17 19 20 21
p = 29 ; 2 3 8 10 11 14 15 18 19 21 26 27
p = 31 ; 3 11 12 13 17 21 22 24
p = 37 ; 2 5 13 15 17 18 19 20 22 24 32 35
p = 41 ; 6 7 11 12 13 15 17 19 22 24 26 28 29 30 34 35
p = 43 ; 3 5 12 18 19 20 26 28 29 30 33 34
p = 47 ; 5 10 11 13 15 19 20 22 23 26 29 30 31 33 35 38 39 40 41 43 44 45
p = 53 ; 2 3 5 8 12 14 18 19 20 21 22 26 27 31 32 33 34 35 39 41 45 48 50 51
p = 59 ; 2 6 8 10 11 13 14 18 23 24 30 31 32 33 34 37 38 39 40 42 43 44 47 50 52 54 55 56
p = 61 ; 2 6 7 10 17 18 26 30 31 35 43 44 51 54 55 59
p = 67 ; 2 7 11 12 13 18 20 28 31 32 34 41 44 46 48 50 51 57 61 63
p = 71 ; 7 11 13 21 22 28 31 33 35 42 44 47 52 53 55 56 59 61 62 63 65 67 68 69
p = 73 ; 5 11 13 14 15 20 26 28 29 31 33 34 39 40 42 44 45 47 53 58 59 60 62 68
p = 79 ; 3 6 7 28 29 30 34 35 37 39 43 47 48 53 54 59 60 63 66 68 70 74 75 77
p = 83 ; 2 5 6 8 13 14 15 18 19 20 22 24 32 34 35 39 42 43 45 46 47 50 52 53 54 55 56 57 58 60 62 66 67 71 72 73 74 76 79 80
p = 89 ; 3 6 7 13 14 15 19 23 24 26 27 28 29 30 31 33 35 38 41 43 46 48 51 54 56 58 59 60 61 62 63 65 66 70 74 75 76 82 83 86
p = 97 ; 5 7 10 13 14 15 17 21 23 26 29 37 38 39 40 41 56 57 58 59 60 68 71 74 76 80 82 83 84 87 90 92　」

*原始根がちょっぴり身近になったような気がする…^^

"平方剰余だったら原始根でない"…がわかった☆…^^;v

https://ja.wikipedia.org/wiki/ウィルソンの定理 より Orz〜

「ウィルソンの定理

p が素数ならば (p-1)! ≡ -1 (mod p) が成り立つ。p>1の場合、逆も成り立つ。

証明

p = 2 の場合は成り立つので、以下pは奇素数とする。pは素数だから法pに関する原始根aが存在する。このとき、フェルマーの小定理より、

aは原始根だから、a¹, a², … ,a^p-1(≡1)はそれぞれpを法として還元すると、1, 2, … ,p-1の並べ替えである。よって、

となる。一方、

が成り立つ。b=a^p(p-1)/2とおくと、b² ≡ 1 (mod p) だからb ≡ ±1 (mod p) である。示したいのはb ≡ -1 (mod p) なのでb ≡ 1 (mod p) と仮定して矛盾を導く。aは原始根だから、フェルマーの小定理より、p(p-1)/2はp-1で割り切れる。ゆえにp/2は整数となるが、これはpが奇数であることに反する。Q.E.D.」

aを原始根に限定する理由がよくわからなかったんだけど…原始根でないときは…p-1以下で循環してしまうから、1〜(p-1) のすべての剰余が現れないからなのね ^^

http://unnikki.web.fc2.com/numbers/abcdefg2.html より 引用 Orz〜

「原始根の一覧

pを素数として、法 pのもとで(p-1)乗してはじめて1になる数を原始根といいます。

たとえば法11のもとで2は10乗しないと1にならないので(2¹⁰=1024=11×93+1)2は法11のもとでの原始根です。しかし法7のもとでは、2³=7+1と、2^7-1より小さいべき乗で1となってしまうので、2は法7のもとで原始根ではありません。法が pのとき原始根は（1,2,..., pのなかに）  φ( φ( p)) =  φ( p-1) 個存在します。

*たとえば...

φ(6)=φ(2)*φ(3)=(2-1)*(3-1)=2

φ(12)=φ(2^2)*φ(3)=(2^2-2)*(3-1)=4

平方剰余の理論より、「 p≡±1 mod 8」⇔「2は法 pのもとで平方剰余である」⇒「2は法pのもとで原始根でない」ことがいえます。」

画像：https://ja.wikipedia.org/wiki/アドリアン＝マリ・ルジャンドル より Orz〜

↑

ルジャンドルとは別人の肖像画でしたのねぇ ^^;

「2005年までに凡そ2世紀もの間、ルジャンドルの肖像画はフランスの政治家であるルイ・ルジャンドルの肖像画と間違われていた。 単純にルイ・ルジャンドルの肖像画に"ルジャンドル"と書かれてあったものを政治家のルジャンドルではなく数学者のルジャンドルであると判断してしまったのが誤りの原因とされている。」

↓

こっちも本物かどうかなんてどうしてわかったんだろ…^^;…?

*x^2-2≡0　mod p を満たすxがあるとき、2は法 pの平方剰余と呼ばれる。

平方剰余の第2補充法則:

左辺(m /p )はルジャンドル記号で、

mが平方剰余のとき1, そうでないとき-1、割り切れるとき 0

の右辺=1

つまり、2は 法 p (p≡±1　mod 8)　の平方剰余…

まではわかるんだけど…

「2は法 pのもとで原始根でない」に今のわたしには結びつけられない…^^;…?

!! 解☆↓☆決 !!

・鍵コメT様からのもの Orz〜

2≡a^2 (mod p)であれば，a^(p-1)≡1 (mod p)から2^((p-1)/2)≡1 (mod p).
これより，2は原始根ではありません．

*おおっ!! ☆ 

お陰さまで了解できましたぁ♪ 〜m(_ _)m〜v

レピュニット…v2

画像：http://achikochitazusaete.web.fc2.com/ouminotera/douganji/kannon.html より 引用 Orz〜

「十一面観音像は全国に数多くあるらしいが、国宝あるいは重要文化財に指定されている像は、この滋賀県が一番多いという。４１体。国宝に指定されている像は６体で、聖林寺、法華寺、室生寺、観音寺、道明寺、渡岸寺である。渡岸寺の十一面観音については、多くの方がその美しさを書いているが、・・・」

*湖北には古刹がいっぱい残ってるてるという話は読んだことがあるんだけど...すっかり忘れてた…^^;...いつの日か行ってみたいな…♪

レピュニットとは、

1,11,111,1111,…のようなすべての桁が1である数のこと.。

(10^n-1/9)ですね。

これが、平方数の場合…

下二桁は 11

平方数の　mod 4では、0, 1

11≡ 3　mod 4 なので平方数にはなれない…

一桁のときは 1でこれは明らか。

wikiでは…

「100 を法として 11 と合同な平方数は存在しないから、レピュニットで平方数となるものは 1 のみである。一般に、レピュニットで累乗数となるものは 1 のみであることが知られている (Bugeaud, Mignotte 1999a)。」

*この mod 100 で11と≡な平方数は存在しないからという理由がわからない…?…^^;

レピュニットに素数が11以外あるか？

2,3の倍数個は駄目、また、5,7,11,13,17,19,23,29,31,37,41,43,47,53,...の倍数個は駄目なので…

(2^10-1)/11=1023/11=93…なはっ ^^

(10!+1)/11=3628801/11=329891(prime)…ははっ ^^

11111=41*271

1111111=239*4649

11111111111=21649*513239

1111111111111=53*79*265371653

11111111111111111=2071723*5363222357

1111111111111111111=prime=R(19)

11111111111111111111111=prime=R(23)

11111111111111111111111111111=3191*16763*43037*62003*77843839397

1111111111111111111111111111111=2791*6943319*57336415063790604359

1111111111111111111111111111111111111

=2028119*247629013*2212394296770203368013

11111111111111111111111111111111111111111

=83*1231*538987*201763709900322803748657942361

1111111111111111111111111111111111111111111

=

1111111111111111111111111111111111111111111111111

=

1111111111111111111111111111111111111111111111111111111

=

1111111111111111111111111111111111111111111111111111111111111

=

111111111111111111111111111111111111111111111111111111111111111111111

=R(67)

以上は計算できましぇん…^^;

wiki より…

R(67)=

n = 2, 19, 23, 317, 1031, ...のときに、R_n は素数となる。レピュニットの素数が無限にあるかどうかは知られていない。」

*あるんだけど...

無限個あるかどうかは知られてないんですねぇ ^^;

http://tsujimotter.hatenablog.com/entry/11-11-repunit より 引用 Orz〜

「1111のような偶数桁のレピュニットは

「平方数マイナス平方数」の形で必ずかくことができます。

たとえば 11 は、

11=62−52

ですし、1111は、

1111=562−452

となりますね。」