尤拉函數 Euler φ function(筆記)

最近看書一直碰到尤拉函數，寫個筆記複習一下。

定義：尤拉φ函數

若n為自然數，定義φ(n)為不大於n且與n互質的自然數的個數。

Note: φ(1)＝1

尤拉φ函數的算法：

若，其中p₁, p₂, …, p_r均為質數，則φ(n)即為所有不比n大且不是p₁, p₂, …, p_r這些質數的倍數的數之個數，即

也可以用另一個觀點來說明尤拉φ函數的算法：

首先要先說明，若a和b互質，則φ(ab)＝φ(a)×φ(b)：

若a＝b＝1，顯然成立。

若ab≠1，不失一般性，假設a＞b，因為不大於a的自然數中，有φ(a)個數與a互質，設為a₁, a₂, …,a_φ(a)，則對於1≦i≦φ(a)，{ a_i, a_i＋a, a_i＋2a, …, a_i＋(b－1)a}是一個模b的完全剩餘系(complete residue system)^註，所以有φ(b)個數與b互質，當然也與ab互質，故總共有φ(a)×φ(b)個數與ab互質。

^註：模n的完全剩餘系指的是有n個元素的集合，其中每一個元素在模n時都互不同餘，也就是說這n個元素模n後與{0, 1, 2, …, n－1}相同。

舉例來說，我們考慮不大於72且與72互質的數，因為72＝9×8，則可以列出如下的9行8列的陣列，再將與9不互質的數刪掉，則就只剩下φ(9)＝6行。剩下的每一行有8個數，恰是模8的完全剩餘系，只有φ(8)＝4個數與8互質(即框起來的數)，這些數即所有不大於72且與72互質的數，共有φ(9)×φ(8)＝24個。即φ(72)＝24。

1	2	3	4	5	6	7	8	9
10	11	12	13	14	15	16	17	18
19	20	21	22	23	24	25	26	27
28	29	30	31	32	33	34	35	36
37	38	39	40	41	42	43	44	45
46	47	48	49	50	51	52	53	54
55	56	57	58	59	60	61	62	63
64	65	66	67	68	69	70	71	72

實際上，只要一個算術函數(arithmetic function，定義域為正整數的函數) f，滿足f(ab)＝f(a)f(b)，其中a和b互質，就稱函數f為積性函數(multiplicative function)，因此對於任意的自然數n，將n作質因數分解成，則。上面的敘述即在說明φ是一個積性函數，故。而任意質數p的冪次p^k都只有p這一個質因數，因此不大於p^k且與p^k不互質的數只有p、2p、…、p^k共p ^k­-1個數，故φ(p^k)＝p^k－p^k-1＝p^k(1－1/p)。所以可以得到φ(n)＝n(1－1/p₁) (1－1/p₂)…(1－1/p_r)，其中p₁、p₂、…、p_r是n所有的質因數。

正五邊形面積(課堂筆記)

已進入期末考週，進度也上完了，前天在課堂上不經易的問了學生：「正五邊形的面積怎麼算？」沒想到學生們竟然真的很認真的想要計算這個問題。(說實在的，我也沒有真的去算過它。)

若要用基礎幾何來算，我的第一個想法是，要算五邊形面積，不如算三角形面積。如果ABCDE是邊長為一的正五邊形，作//，//，其中F、G在直線CD上，則三角形AFG的面積就會等於正五邊形ABCDE的面積。

要算三角形AFG的底邊長和高，我們可以回想下面這個國中題目中常見的三角形：，，則很容易計算出∠P＝36°，且三角形PQR相似於三角形QTR，故可算出這個等腰三角形的腰與底邊的比為，比值為黃金比例。再利用商高定理，可以算出此三角形的高與底邊的比為。

在正五邊形ABCDE中，三角形ACD、 AHI、ABI都與三角形PQR相似，因此可以算得，A到底邊的距離為，故三角形AFG面積為，也就是我們要求的正五邊形ABCDE的面積。

如果用三角函數處理這個問題，只要連接正五邊形的正中心點與頂點，就可以得到五個頂角都是72°的等腰三角形，簡單畫一下就可以得到面積為。

一道幾何的問題(筆記)

前幾天，學校一位老師丟了一題給我，後來他說，這是有人丟在網路上的題目，據說是196x年的奧林匹亞的題目，題目如下：

三角形ABC邊長為a、b、c，面積為Δ，試證：

 我的證法如下：

                              

                              

                              

                              

又已知三角形的三內角會滿足tanA＋tanB＋tanC＝tanA tanB tanC，令x＝tanA , y＝tanB , z＝tanC

故
                              

                              

                              

                              

                              

                              

故  

                              

猜拳輸、贏的平方和與標準差(課堂筆記)

前幾天教到數據分析單元的平均數與標準差，讓學生作一個活動：

先任找幾個同學，兩兩互相猜拳決定輸贏，每人都記下自己輸贏的次數，然後計算所有贏的次數的平方和，與輸的次數的平方和，比較兩個數值的大小。

例如說，找9個人，每個人都與其他8人猜拳，記下輸贏的次數：

	A	B	C	D	E	F	G	H	I
贏	4	2	6	4	5	3	2	3	7
輸	4	6	2	4	3	5	6	5	1

贏的次數的平方和：4²+2²+6²+4²+5²+3²+2²+3²+7²=168

輸的次數的平方和：4²+6²+2²+4²+3²+5²+6²+5²+1²=168

這兩個數值會相等，原因為何？

才教完標準差，學生的思考方向果真就往標準差的方向去思考。

學生的討論：

設贏的次數為X：x₁, x₂,…, x₉，輸的次數為Y：y₁, y₂,…, y₉。首先X和Y的算術平均數會相等，而且值為μ=(x_i+y_i)/2=4，所以∣x_i–μ∣=∣y_i–μ∣，因此X和Y的標準差一定會相等。而σ_x²=(Σx_i²–9μ²)/9，σ_y²=(Σy_i²–9μ²)/9，所以Σx_i²=Σy_i²。

我後來跟學生說，我們學過Y=aX+b，則σ_y=∣a∣σ_x。既然x_i+y_i=8一定會成立，即y_i=–x_i+8，那麼X和Y的標準差相等，不就一定會成立嗎！

還有一個學生，直接用簡單的代數，就得到這個結果：

設共有n個學生，則只要知道贏的總次數與輸的總次數會相等，即可得
Σx_i²–Σy_i²=Σ(x_i²–y_i²)= Σ(x_i+y_i) (x_i–y_i)=(n–1)Σ(x_i–y_i)= (n–1) (Σx_i–Σy_i)=0