ASP 討論版

	昌爸工作坊論壇
\|─	數論(部份)


回覆	搜尋	返回	管理

作者	標題: 數論(部份)
yani IP Address: [ 211.74.13.108 ]	發表於: 2002/4/14 上午 05:57:30 以下所討論的數皆整數，p為質數。主題﹕a^x≡1(n) 若a與n不互質,則a^x=1(n)無解，理由﹕a^x-kn為d的倍數≠1。故僅討論a,n互質時。令a屬於Un，Un表示小於n且於n互質之正整數，φ(n)表示Un的個數。例﹕U2={1},U3={1,2},U4={1,3},U5={1,2,3,4},U6= {1,5},U8={1,3,5,7},U9={1,2,4,5,7,8},U12= {1,5,7,11},U15={1,2,4,7,8,11,13,14},U21= {1,2,4,5,8,10,11,13,16,17,19,20},U30= {1,7,11,13,17,19,23,29}。Up={1,2,3,…p-1},p是質數。 φ(2)=1,φ(3)=2,φ(4)=2,φ(5)=4,φ(6)=2,φ(8)=4,φ(9) =6,φ(12)=4,φ(15)=8,φ(21)=12,φ(30)=8,φ(p)=p-1。定理1﹕a^φ(n)≡1(n)。推理1﹕若(a,p)=1則a^φ(p)≡a^(p- 1)≡1(n)。推理2﹕對所有的b，b^p≡b(p)﹕此證明牽扯到群論，略。命題2:若n≧3時，φ(n)為偶數﹕因若a屬於Un則n-a亦屬於Un 定理3﹕若Un={a,b,c,d,…,t},則(abcd…t)^2≡1(n) 定理4﹕a^2≡1(p)之解為a≡1(p)或-1(p) 定理5﹕若p為4m+1型，則a^2≡-1(p)之解為a≡[(p-1)/2]! (p)。定理6﹕若p為4m+3型，則a^2≡-1(p)無解。可由定理1之推理1證明之。定理7﹕(p-1)!≡-1(p)。推理﹕(p-2)!≡1(p)﹕by Wilson，有不只一種證明，在此亦可用定理3,4證明之。命題8﹕若m,n有相同的質因數，則φ(m)/φ(n)=m/n 定理9﹕對所有的m∣n，φ(n)=Σφ(m) 定理10﹕a>1, n∣φ(a^n-1)。證明﹕考慮mod(a^n-1) 命題2,8是自己想的，怕有錯，故稱之為命題。餘皆已被證實的定理或推理。
yani IP Address: [ 61.59.139.231 ]	回覆於: 2002/4/16 上午 09:13:14 更正﹕定理9應改為﹕φ(n)=Σφ(m)，對所有的m∣φ(n) 命題8﹕若m,n有相同的質因數，則φ(m)/φ(n)=m/n，是指m,n有完全相同的質因數。例﹕φ(6):φ(12):φ(18):φ(24):φ(36)=2:4:6:8:12=6:12:18:24:36 若m=p^2，n=p則Un={1,2,…,p-1},Um={1,2,…,p-1,p+1,p+2,…,2p-1,…,(k-1) p+1,…,kp-1,…,pp-1},k<=p，φ(m)=p(p-1),φ(n)=p-1則φ(m)/φ(n)=p=m/n。若m=p^aq…t，n=pq…t。p,q,..,t皆相異質數，令Un={1,…,n-1}共有φ(n)個元素,則Um必={1,…,n-1,n+1,…2n+1,…,…,p^(a-1)n-1}，φ(m)= p^(a-1)φ (n)，φ(m)/φ(n)=m/n 仿上面證明，在一般情形下，命題8仍成立。但底下要介紹更強大的定理﹕ 定理11﹕以下的1,2,…r為下標。若n=p1^(α1)p2^(α2)…pr^(αr)為標準分解式，則φ(n)=n(1-1/p1)(1-/p2)…(1-1/pr)___尤拉公式。證明﹕設A1=#{0<x1<=n﹕x1為p1之倍數}，A2=#{0<x2<=n﹕x2為p2之倍數}， A1∪A2#{0<x<=n﹕x為p1p2之倍數},以此類推。則由包含排斥原理知﹕φ(n)=n-(A1+A2+…+Ar)+[A1∪A2+A1∪A3+…+A2∪A3+… +A_(r-1)∪Ar] -[∪A(i,j,k)]+[∪A(i,j,k,m)]-.+…+(-1)^r(A1∪A2∪…∪Ar)，其中∪表聯集，∪A(i,j,k)表在A1,A2,A3,…,Ar中任取三個作聯集之元素個數之總和，以此類推。 φ(n)=n-{n/p1+n/p2+…+n/pr}+{n/(p1p2)+n/(p1p3)+…+n/(p_(r-1)pr)} -{n/ (p1p2p3)+……+n/(p_(r-2)p_(r-1)pr)}+.-…+(-1)^rn/(p1p2…pr) =n(1-1/p1)(1-1/p2)…(1/pr) 例如: 120=2^335, φ(120)=120 -#(不大於120之﹕2的倍數+3的倍數+5的倍數) +#(不大於120之﹕23的倍數+35的倍數+52的倍數) -#(不大於120之235的倍數) =120 -(120/2+120/3+120/5)+[120/(23)+120/(25)+120/(35)]-120/ (235) =120[1-1/2-1/3/-1/5+1/(23)+1/(25)+1/(35)-1/(235)] =120(1-1/2)(1-1/3)(1-1/5) 另證定理11﹕仿上，由簡單的包含排斥原理知﹕φ(p1p2)=p1p2-p2-p1+1=(p1-1) (p2-1)，再由數學歸納知φ(p1p2…pr)=(p1-1)(p2-1)(p3-1)…(pr-1)。若n=p1^(α1)p2^(α2)…pr^(αr)，再由命題8(至此可稱定理8了)知φ(n)/φ (p1p2…pr)=n/(p1p2…pr) φ(n)=n*(p1-1)(p2-1)(p3-1)…(pr-1) /(p1p2…pr)=n(1-1/p1)(1-1/p2)… (1/pr) 定理11或8之推理:若p∣m則φ(pm)=pφ(m) 定理11之推理﹕若p不整除m則φ(pm)=(p-1)φ(m)，再推理﹕若m為奇數，則φ(2m)= φ(m)
yani IP Address: [ 61.59.139.231 ]	回覆於: 2002/4/16 上午 09:49:05 總結﹕φ(n)表示小於n且於n互質之正整數個數定理1﹕若m是最小的正整數,滿足a^m≡1(n)，則m∣φ(n)___Lagrange 推理﹕若(a,n)=1，則a^φ(n)≡1(n)___Euler 推理﹕若(a,p)=1，則a^(p-1)≡1(p)___Fermat 推理﹕任意整數b，b^p≡b(p)___Fermat 定理2﹕若n≧3時，φ(n)為偶數定理3﹕若對所有的a屬於Un，Πa²≡1(n) 定理4﹕a²≡1(p)之解為a≡1(p)或-1(p) 定理5﹕若p為4m+1型，則a²≡-1(p)之解為a≡[(p-1)/2]!(p) 定理6﹕若p為4m+3型，則a²≡-1(p)無解。定理7﹕(p-1)!≡-1(p)___Wilson 推理﹕(p-2)!≡1(p) 定理8﹕若m,n有完全相同的質因數，則φ(m)/φ(n)=m/n 定理9﹕φ(n)=Σφ(m)，對所有的m∣φ(n) 定理10﹕a>1, n∣φ(a^n-1) 定理11﹕若n=p1^(α1)p2^(α2)…pr^(αr)為標準分解式，則φ(n)=n(1-1/p1)(1-/p2)…(1-1/pr)___Euler 推理﹕若p∣m則φ(pm)=pφ(m) 推理﹕若p不整除m則φ(pm)=(p-1)φ(m) 推理﹕若m為奇數，則φ(2m)=φ(m)
Waster IP Address: [ 203.198.23.26 ]	回覆於: 2002/4/14 上午 07:45:31 真的非常感謝,因為這裡有很多我未見過的定理和推理
yani IP Address: [ 211.74.14.92 ]	回覆於: 2002/4/14 上午 08:59:44 慚愧﹗我也不太懂﹗又懶﹗真希望我以前的數論老師來幫我。
yani IP Address: [ 211.74.13.178 ]	回覆於: 2002/4/14 上午 09:12:56 更正﹕ 若a與n不互質 "設(a,n)=d" 則a^x=1(n)無解，理由﹕a^x-kn為d的倍數≠1。故僅討論a,n互質時。令a屬於Un，Un表示小於n且 " 與 " n互質之正整數
飄 IP Address: [ 61.216.59.170 ]	回覆於: 2002/4/14 上午 10:14:53 yani不愧是yani 你的東西都是寶謝謝你的分享
血 IP Address: [ 61.224.56.160 ]	回覆於: 2002/4/14 下午 03:11:41 命題2:若n≧3時，φ(n)為偶數﹕因若a屬於Un則n-a亦屬於Un a屬於Un若且唯若n-a亦屬於Un, 所以這個命題成立除非a有機會等於n-a,但是這是不可能的,因為若存在a屬於Un使得a=n-a 則a=n/2,當n大於等於3的時候,a=n/2將不落在Un內,矛盾 QED 命題8﹕若m,n有相同的質因數，則φ(m)/φ(n)=m/n 我覺得命題8不對耶... suppose m = 6, n = 2,有相同質因數 but φ(6) = #{1, 5} = 2, φ(2) = #{1} = 1 所以φ(6) / φ(2) = 2 不等於 6 / 2 Besides, yani寫的這些東西不錯看耶~~~ 不過有好多定理我不會證明,哈
yani IP Address: [ 150.117.202.150 ]	回覆於: 2020/5/29 上午 07:25:40 我的命題8是﹕ 若m,n有”完全”相同的質因數，則φ(m)/φ(n)=m/n 18年了，大家都升格當長輩了吧。
克勞棣 IP Address: [ 220.137.56.242 ]	回覆於: 2020/5/30 下午 10:43:44 怎樣叫做「若m,n有”完全”相同的質因數」？ m=2223557 n=2233577 這樣算不算「有”完全”相同的質因數」？