如果你想問的是為什麼 R(k)=ϕ(k), 我再補充說明一下, 假設 s 為一 order 為 k 的 elements, 因為一個 k 次多項式至多不會有超過 k 個根, 所以 {s^1,s^2...,s^k} 所形成的就是所有滿足 x^k=1 mod p 的解集合, 也就是說這些數就是generator的候選人, 然後我在裡面有打一段是在證明假設 l<k 且與 k 不互質, 則 s^l 的 order 必定小於 k, 所以這些 s^l 就都可以從 order 為 k 的候選名單中給刪掉了, 那麼到這裡的結論就是 order 為 k 的數最多只會有 ϕ(k) 這麼多, 此時利用 lemma 我們又知道至少得要有 ϕ(k) 這麼多, 所以結論就是 R(k)=ϕ(k)
5 則留言:
不好意思我也想問問題... 可是我不知道要如何才能在這邊發表文章...?
抱歉佔用了原po的文章
To Dudu:
首先你要通過認證, 認證的方式就是在網頁的右邊那一欄點選"公告"進去, 裡面的最下面那一篇文章有教你怎麼用你的學號來申請, 等申請通過之後, 你用你的帳號登入, 網頁的右上角就會有發新文章的按鈕出現了
一個想法是, 要證明(Zp/{0},*)為一cyclic group就相當於證明(Zp/{0},*)至少有一個 primitive root, 也就是存在一個 r 使得 r^(p-1)=1 mod p 且 r^((p-1)/q)≠1 mod p, 其中 q 為 p-1 的任意質因數, 1<r<p
先提一下, 下方的證明會用到以下這個lemma:
Σ_{m|n} ϕ(m) = n
(這個lemma雖然不會很複雜, 但因為敘述上有點麻煩, 在這裡我就先不證了)
首先令 R(k) 為 (Zp/{0},*) 中 order 為 k 的 elements 的個數, 因為由 cyclic subgroup 的概念我們可以知道當 k 不整除 p-1, R(k)=0, 所以
Σ_{k|(p-1)} R(k) = p-1 -----(1)
假設 s 為一 order 為 k 的 residue
假設 l<k 且 gcd(l,k)=d>1,
則 (s^l)^(k/d) = (s^k)^(l/d) = 1 mod p
也就是說 s^l 的 order 至多為 k/d < k
所以 R(k)≦ϕ(k)
=> Σ_{k|(p-1)} R(k)
≦ Σ_{k|(p-1)} ϕ(k) = p-1 (根據lemma)
可是因為由(1)我們又知道事實上
Σ_{k|(p-1)} R(k) = p-1 = Σ_{k|(p-1)} ϕ(k)
則 R(k) = ϕ(k), for all k|(p-1)
所以 R(p-1) = ϕ(p-1)
這說明了(Zp/{0},*)具有 ϕ(p-1) > 0 個 generator
以 p=7 為例,
R(1)=1, R(2)=1, R(3)=2, R(6)=2
<1>=1
<6>={6,1}
<2>={2,4,1}
<4>={4,2,1}
<3>={3,2,6,4,5,1}
<5>={5,4,6,2,3,1}
不好意思想請問一下
(1)為什麼q 為 p-1 的任意質因數而不是因數
(2)所以 R(p-1) = ϕ(p-1)這個是怎嚜得到的我不是很懂
謝謝
(1) 嗯, 改成因數也可以, 我那邊寫得有點囉嗦, 其實簡單的寫 r^l≠1 mod p, l=1,..,p-2 就可以了
(2) 因為前一句話說的是, 如果 k 是 p-1 的因數, 則 R(k)=ϕ(k), 而 R(p-1)=ϕ(p-1) 只是其中的特例而已
如果你想問的是為什麼 R(k)=ϕ(k), 我再補充說明一下, 假設 s 為一 order 為 k 的 elements, 因為一個 k 次多項式至多不會有超過 k 個根, 所以 {s^1,s^2...,s^k} 所形成的就是所有滿足 x^k=1 mod p 的解集合, 也就是說這些數就是generator的候選人, 然後我在裡面有打一段是在證明假設 l<k 且與 k 不互質, 則 s^l 的 order 必定小於 k, 所以這些 s^l 就都可以從 order 為 k 的候選名單中給刪掉了, 那麼到這裡的結論就是 order 為 k 的數最多只會有 ϕ(k) 這麼多, 此時利用 lemma 我們又知道至少得要有 ϕ(k) 這麼多, 所以結論就是 R(k)=ϕ(k)
張貼留言