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

Wilsonの定理...

いままで何度も出て来てる定理ですが…

いつもさくさくと証明できない…^^;

オイラーの定理を使った上手い証明があったのでアーカイブス♪

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

「

*解法2が華麗ですね♪

オイラーのバーゼル問題を解いたときのような発想ね☆

完全トーティエント数...

完全数ってのがあるけど…

トーティエントの値においてもこういうこと考えられてるのねぇ…^^

http://ja.wikipedia.org/wiki/完全トーティエント数 より Orz〜

「完全トーティエント数（perfect totient number）は、自然数のうち、以下の等式を満たす数 n である。

ここで φ はオイラーのトーティエント関数である。例えば 327 は

φ(327) = 216, φ(216) = 72, φ(72) = 24, φ(24) = 8, φ(8) = 4, φ(4) = 2, φ(2) = 1

と 1 になるまで次々とφ関数の値を計算し、それらの総和が 216 + 72 + 24 + 8 + 4 + 2 + 1 = 327 と元の数に等しくなるので完全トーティエント数である。

一般に完全トーティエント数 n は以下の式を満たす。

http://upload.wikimedia.org/math/5/2/2/52296a4ffd502080525160e308f34318.png

完全トーティエント数は無数にあり、そのうち最小の数は3である。完全トーティエント数を小さい順に列記すると

3, 9, 15, 27, 39, 81, 111, 183, 243, 255, 327, 363, 471, 729, 2187, 2199, 3063, 4359, 4375, …

ほとんどの完全トーティエント数は3の倍数であり、3の倍数でない完全トーティエント数のうち最小の数は4375である。特に3の累乗数(3,9,27,81,243,729,2187,…)は全て完全トーティエント数である。これは3の累乗数 3^k が

http://upload.wikimedia.org/math/b/1/e/b1e823ca91732d072fa670ab14a90012.png

を満たすことから証明できる。

Venkataramanは1975年に素数pが p=4×3^k+1 の形で表されるとき、3pが完全トーティエント数になることを発見した。一般に、素数p>3に対して3pが完全トーティエント数であるとき、p≡1(mod 4) である（Mohan,Suryanarayana 1982）。しかし、この形をした3pの全てが完全トーティエント数になる訳ではない。例えばp=17の場合 p≡1(mod 4) を満たし、3p=51 となるが51は完全トーティエント数ではない。」

*確認…^^

φ(3^k)=3^k-3^(k-1)=3^(k-1)*(3-1)=2*3^(k-1)

φ(2*3^(k-1))=φ(3^(k-1))=2*3^(k-2)

…

φ(2*3)=φ(3)=2

合計=2*(3^(k-1)+3^(k-2)+…+1)=(3-1)(3^(k-1)+3^(k-2)+…+1)=3^k=n

*φ(4375)=φ(5^4*7)=(5^4-5^3)*6=5^3*4*6=3000

φ(5^3*2^3*3)=(5^3-5^2)*(2^3-2^2)*2=5^2*2^2*2^2*2=5^2*2^5=800

φ(5^2*2^5)=(5^2-5)*(2^5-2^4)=5*2^2*2^4=5*2^6=320

φ(5*2^6)=4*(2^6-2^5)=2^2*2^5=2^7=128

φ(2^7)=2^6

…

合計=3000+800+320+128+128-1=4375

どうやれば見つけられるんだろうか知らん…^^;…?

また...この値が応用できる問題ってあるのか知らん…^^;…?

ノントーティエント...

http://ja.wikipedia.org/wiki/ノントーシェント より Orz〜

「ノントーティエント（英: nontotient）は、自然数の内、オイラーのトーティエント関数φの値域に含まれない数であり、 φ(x)=n においてどのような自然数xもこの方程式を満たさないような自然数nのことである。言い換えると、全てのxにおいて「x以下の数で互いに素である自然数の個数」（=φ(x)）がn個ではないようなnがノントーティエントである。また、ノントーティエントでないものをトーティエントと呼ぶことがある。

1は φ(x)=1 において x=1,2 という解をもつのでノントーティエントではない。しかし1を除く全ての奇数はノントーティエントである。偶数のノントーティエントは無数に存在し、その内最小の数である14から小さい順に列記すると

14, 26, 34, 38, 50, 62, 68, 74, 76, 86, 90, 94, 98, 114, 118, 122, 124, 134, 142, 146, 152, 154, 158, 170, 174, 182, 186, 188, 194, 202,206, 214, 218, 230, 234, 236, 242, 244, …

ノントーティエントの集合は密度1を持つ。つまり殆ど全ての数はノントーティエントである。しかし、pを素数とすると、p-1はノントーティエントでないから、トーティエントの逆数の和は発散する。

2pがノントーティエントであることと、2p+1が合成数であることは同値である。特に、2pがトーティエントであるとき、pはソフィー・ジェルマン素数である。また、4pがノントーティエントであることと、2p+1,4p+1がともに合成数であることも同値である。

画像：http://toyokeizai.net/articles/-/368?page=3 より 引用 Orz〜

「ソフィ・ジェルマン。数学史上数少ない女性数学者である。彼女は、100以下のすべてのn について、x, y, z のいずれかがn で割り切れる場合についてフェルマーの最終定理が正しいことを証明した。」

http://ja.wikipedia.org/wiki/ソフィー・ジェルマン より Orz〜

「ソフィー・ジェルマンの定理

2p + 1 が素数であるような素数 p について、x^p + y^p = z^p が成り立つとき、x, y, z のいずれかが p で割り切れねばならない。

たとえば x⁵ + y⁵ = z⁵ が成り立つとき、x, y, z のいずれかは 5 の倍数である。また、この定理に現れる 2p + 1 が素数であるような素数 p をソフィ・ジェルマン素数という。」

http://ichigaku-rakukou.net/column/1787/ ;

http://d.hatena.ne.jp/sessendo/20090329/p2 参照

*証明は探してもないみたいね…^^;…

http://ja.wikipedia.org/wiki/ソフィー・ジェルマン素数 より Orz〜

*「ソフィー・ジェルマン素数（Sophie Germain prime）はフランスの数学者ソフィー・ジェルマンによって名付けられた素数で、2p + 1 もまた素数であるような素数 p のことである。それに対し、2p + 1 のほうを安全素数 (safe prime) と呼ぶ。例えば 11 と 2 × 11 + 1 = 23 はともに素数であるので 11 はソフィー・ジェルマン素数、23 は安全素数である。ソフィー・ジェルマン素数は無数に存在するかどうか分かっていない。最も小さいものは 2 である。

ソフィー・ジェルマン素数を 2 から小さい順に列記すると

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, …

2 と 3 を除くソフィー・ジェルマン素数は 6n - 1 の形の素数である。また 2 と 5 を除くソフィー・ジェルマン素数の一の位は 1, 3, 9 のいずれかである。

2010年現在知られているものの中で最大のソフィー・ジェルマン素数は 183027 × 2²⁶⁵⁴⁴⁰ − 1 であり、79911 桁の数である。

ソフィー・ジェルマン素数 p が p ≡ 3 (mod 4) を満たすとき 2p + 1 はメルセンヌ数 2^p - 1 の約数となる。(*この証明は...http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1482806479 参照 ☆)」

φ(p)=p-1 となるため、p-1で表される数はノントーティエントではない。またφ(p²)=(p-1)p であるため、(p-1)pの形で表される矩形数もノントーティエントではない。さらにp-1で表される異なる数同士の積もノントーティエントにはならない。」

たとえば...

2=φ(3)

4=φ(5)

6=φ(7)

8=φ(3)*φ(5)=φ(15)

10=φ(11)

12=φ(3)*φ(7)=φ(21)

φ(n)=φ(p*q*q*…)=(p-1)(q-1)(r-1)…

なので…2が1個ならnは素数、2が2個なら素数が2個,…k個なら素数がk個…

14=2*7で、14+1=15は素数じゃないのでノントーティエント

16…16+1=17

18…18+1=19

20=2^2*5…(3-1)(11-1)

22…23

24=2*12…(3-1)(13-1)

26=2*13…26+1=27は素数でないのでノントーティエント

ってなことですね ^^

オイラーの定理…a^φ(n)≡1 (mod n)

自分で言うのもなんですが ^^;…

この欄に訪問するのは超お久…Orz〜

知らぬ間に...最初の勉強しようとしてたサイトが消えている…^^;;…

と思ったら…ありましたぁ☆

http://aozoragakuen.sakura.ne.jp/suuron/suuron.html

今回は…別のところから…^^

http://www.tcp-ip.or.jp/~n01/math/euler.pdf より 引用 Orz〜

「定義 1 

自然数 n に対して,n 以下の自然数で n との最大公約数が 1 であるものの個数を φ(n) で表す.

φはオイラー関数と呼ばれる. 

(*オイラーの φ 関数（ファイかんすう、phi function）)

(*オイラーのトーシェント関数（Euler's totient function）)

φ(1) = 1

である。

定理 3 

p^n と互いに素でないそれ以下の自然数は p^(n−1) 個ある

[証明]

p^n と互いに素でない自然数は p*x とかける. 

x は 1 ≤ x ≤ pn−1 の全ての自然数の値を取り得,

なおかつそのどの x についても p*x が重複することはない(つまり p の倍数).

よってその個数は p^(n−1) である.　[証明おわり]

定理 4 

画像：http://ja.wikipedia.org/wiki/オイラーのφ関数 より Orz〜

φ(n)の最初の1000個の値

定理 8    (オイラーの定理)

自然数 n と互いに素である自然数 a について,

が成り立つ.

[証明] 

n 以下の自然数で n と互いに素な数を

r1,r2,r3,··· ,rφ(n)　　　　　　 (1) 

と表す.これらに,n と互いに素である自然数 a をかけた数,

ar1, ar2, ar3, · · · , arφ(n) 　　　(2) 

を考える.これらも全て n と互いに素である.

また,i̸=j=⇒ari

である.なぜならば,もし ari ≡ arj とすると,a(ri − rj) ≡ 0 つまり ri − rj は n で割り切れ,ri ≡ rj となってしまい,仮定と矛盾する.つまり (2) の各数は (1) のどれか一つと合同になり,なおかつ重複することはない.したがってこれらをすべててかけ合わせたものも合同になる.すなわち,

aφ(n)r1r2r3 ···rφ(n) ≡ r1r2r3 ···rφ(n) ( mod n )

よって

 aφ(n) ≡ 1

この定理の特殊な場合が次の定理である.

定理 9 (フェルマーの小定理)

p の倍数でない自然数 a について,

が成り立つ.

これらの定理は a が正の整数として証明したが,整数全体に拡張してもよい. 

問題 4 

2009^2009 の下 3 桁を求めよ.

[解]

φ(1000) = φ(2^3*5^3)
= 2^2*5^2*(2−1)(5−1) = 400

2009^2009 ≡ 9^2009 ( mod 1000) 

≡ 9^(400×5+9)

≡ 9^9
≡ (81^2)^2 × 9

≡ 561^2 × 9 

≡721×9

≡489··(·こたえ)

*こういう問題が解ける武器になるのって偉大だわ☆

これらの定理は n を法として 1 を得る最小の冪を与えるものではないことを注意しなければならない.たとえば

p = 7, a = 4

とすると,フェルマーの小定理は

4^6≡1 (mod7) 

となることを主張しているわけだが,

4^3=64≡1 (mod7)

なので 6 より小さい冪 3 で既に 1 に合同になっている.この小さい冪というのは必ず p − 1 の約数になっている.しかしながら,p の倍数で無いあらゆる整数 a について 1 と合同になる最小の冪は p − 1 である.これらの証明はここでは記述しない.　[証明おわり] 　」

*たとえば…4^6≡1 (mod 7)

ならば…6の約数である 1,2,3で…4^1≡±1, 4^2≡1, 4^3≡±1　でなければならないものねぇ ^^…じっさいは…4, 4^2 は違うわけだけど…

素数pのとき、p-1は偶数なので、a^{(p-1)/2}≡±1 であることは言えますね ^^ 　

最小公倍数

3. 最小公倍数

二つ以上の整数 a, b, c,・・・ に共通な倍数をそれらの整数の公倍数という． 0は常に公倍数である． それを除けば公倍数の絶対値は a, b, c,・・・ のいずれの絶対値よりも小さくはないので， 公倍数の中に正で最小のものがある．それを最小公倍数(least common multiple 略して L.C.M.)という．
二つ以上の整数 あ、b、c、・・・ に共通な約数をそれらの整数の公約数という． 1は常に公約数である．公約数の絶対値は a, b, c,・・・ のいずれの絶対値よりも大きくはないので， 公約数の中に最大のものがある．それを最大公約数(greatest common measure 略して G.C.M.)という．

定理
二つ以上の整数の公倍数は，最小公倍数の倍数である．
二つ以上の整数の公約数は，最大公約数の約数である．
a, b の最小公倍数を l ，最大公約数を d とすれば ab=dl
a, b が互いに素で，他の整数 c と b との積 bc が aで 割りきれるなら，実は c が a で割りきれる．
証明

a, b, c,・・・の最小公倍数を l とし, m を任意の公倍数とする． m を l で割った商を q ，余りを r とすると
m=ql+r, 0 ? r < l
となる． l も m も a の倍数であるから l=al', m=am' とおくと
r=m-gl=a(m'-ql')
より, r は a の倍数である．同様に b, c, ・・・の倍数でもあり， r は a, b, c,・・・ の公倍数となる．ところが l は正で最小の公倍数 であったから，もし r が0でないとすると, lより小さい正の公倍数がある ことになり, l の最小性に反する．
∴ r=0
つまり m は l の倍数である．
a, b, c,・・・ の最大公約数を d とし, m を任意の公約数とする． l を d とm の最小公倍数とする． a は m の倍数であり， d の倍数である．つまり m と d の公倍数であるから(1)より a は l の 倍数である．同様にb, c, ・・・ も l の倍数である． つまり l は a, b, c,・・・ の公約数である．d が最大の公約数なので，
l ? d
一方, l はd とm の最小公倍数なので d ? l
∴ l=d
d と m の最小公倍数 l が d に一致した．d は m の倍数， つまり任意の公約数 m は最大公約数 d の約数である．
l は a, b の最小公倍数であるから適当な整数 a' と b' を用いて，
l=ab'=ba'
とおける． ab は a, b の公倍数だから(1)から ab は l の倍数である．
ab=ml
とする．よって
ab=ml=ma'b, ab=ml=mab'
∴ a=ma', b=mb'

つまり m は a, b の公約数である．(2)より最大公約数dの約数なので，d=me とおける．
一方 d は a, b の最大公約数なので a=da", b=db" とおける．よって
a=da"=mea", b=db"=meb"

一方，a=ma', b=mb' であるから，ma'=mea", mb'=meb"が成り立つ．
∴ a'=ea", b'=eb"

その結果，
l=ab'=aeb", l=a'b=ea"b
∴ l/e=ab"=a"b

ところがこれは l/e が a, b の公倍数であることを示している． l が最小の公倍数なのでその最小性により e=1 ．
∴ m=d つまり　ab=dl

a, b の最大公約数が 1 なのでa, b の最小公倍数は ab である． 仮定から bc は a の倍数であり，したがってa と b の公倍数である． よって bc は ab の倍数であり，
bc/ab=c/a が整数

つまりc は a の倍数である．□
この定理の証明において，前節の「除法の原理」が基本定理として用いられてることが わかる．日頃当然のように論証で使っていることが，「除法の原理」を基礎に厳密に示される．

問題
a, b は互いに素な正の整数とするとき，次の問に答えよ．

1. 分数 (7a+2b)/(3a+b) は既約分数である．
2. ps-qr=1 なる正の整数 p, q, r, s に対して， 分数 (pa+bb)/(ra+sb) は既約分数である．
3. (11n-42)/(3n-13) が既約分数にならないような 自然数 n を，小さい方から順に三つ求めよ．

1.
解法１
(7a+2b, 3a+b)=(2(3a+b)+a, 3a+b)=(a, 3a+b)=(a,b)=1

解法2
7a+2b=M, 3a+b=N とおくと逆に解けて
a=M-2N, b=-3M+7N
したがって M とN の最大公約数を d とすれば a も b も d で割れる。
(a,b)=1 なので、d=1 つまり、与式は既約分数。

2.
pa+qb=M, ra+sb=N とおくと逆に解けて
a=sM-qN, b=-rM+pN
したがって M と N の最大公約数を d とすれば a も b も d で割れる。
(a,b)=1 なので、d=1 つまり、既約分数である。

3.
(11n-42, 3n-13)=(4(3n-13)-n, 3n-13)=(-n, 3n-13)=13
分子、分母が13 の倍数になるときのみ既約でない。ゆえに n=13,26,39

画像：原論（幾何学原本）ヴェネツィア, 1482年, 初版.
http://www.kanazawa-it.ac.jp/dawn/148201.html　より Orz〜