推 hchuang :perfect Shuffle 05/11 12:51
→ recorriendo :拆成disjoint cycle很簡單啊 1到2 2到3 3到1 就是一 05/11 16:15
→ recorriendo :個cycle了 然後考慮剩下的數字 05/11 16:15
→ a88241050 :樓上,3到4啊..哪有到1= = 05/11 17:20
推 TassTW :1樓正確, 不過連結不好讀; 3,4樓看錯題目了? 05/12 04:05
我又看了一下, 發現那和原 po 的題目有一些小差異
→ TassTW :原 po 那是 two-line notation 05/12 04:06
推文有點困難回答 還是回文好了
以下假設 n 為奇數:
1.
原 po 的 permutation 是這樣送:
1 |→ 1
2 |→ 3
3 |→ 5
: :
51 |→101
52 |→ 2
: :
101|→100
規則是 "乘 2 後減 1 (mod 101)"
2.
"減 1 "有點麻煩,
我們重新編號, 把所有的號碼都減1 會好看很多
原本的 permutation 就會變成 作用在 {0,1,...,100} = Z_101 上的
0 |→ 0
1 |→ 2
2 |→ 4
: :
50 |→100
51 |→ 1
: :
100|→99
所以原 permutation 就是 Z_101 上的 "乘2"
現假設 n 為奇數,
2 一定有反元素 (n+1)/2,
故 2 一定落在乘法群 Z_101^* 中
因此原題就等價於
"求 乘法群 Z_101^* 中, 2 這個元素的 order"
也就等價於
"找最小的正整數 k 滿足 2^k = 1 (mod 101)"
p.s.
n 為偶數的時候, n 送到 n本身
用相似的推理, 可以把問題轉化成 Z_{n-1}^* 上的元素 order 為何
3.
這就可以手算了
由費瑪小定理, k|100 => k = 1, 2, 4, 其中一個
5,10, 20,
25,50,100
手算 2^25 = 10 (mod 101), 並知道 k<25 都不成立後
就知道 2^50 = 100 = -1 也不成立
最後 2^100 = 1 => 100 確實是 2 的 order
4.
如果你要問對於一般的 n,
怎麼拆成 disjoint cycles 的話
那就等於是問 Z_n^* 這個乘法群的結構
根據中國剩餘定理
先將 n 質因數分解成 n= p_1^{r_1} ... p_m^{r_m}
就可得
Z_n^* = Z_{p_1}^{r_1}^* x ... x Z_{p_1}^{r_1}^*
再根據一些豆知識(咦?),
也就是利用 short exact sequences (of abelian groups) splits 的條件
可證
Z_n^* is cyclic <=> n = 2,4, p^r or 2p^r (p:odd prime)
就可以完整的拆解 Z_n^*
我必須承認, 我是為了想要打出上面紅色的部份
才回文回答這個問題的.......
原 po 的問題看似無聊,
但是考究一點, 可以扯出很有意思的東西
5.
例1: n = 101
其實不用用到 3., 因為 101 已經是質數了....
必然有 Z_101^* = Z_100 為一 cyclic group of order 100
例2: n = 9
知 Z_9^* 是一 cyclic group of order φ(9)= 6,
因此 2 落在 6-cycle 中,
又, 注意到 Z_9\{0} 有 8 個元素
因此仍有兩個不在 Z_9^* 中元素, 形成一個 2-cycle
驗證: 2 |→ 4 |→ 8 |→ 7 |→ 5 |→ 1 |→ 2 成一 6-cycle
3 |→ 6 |→ 3 成一 2-cycle
--
╭═──═───══╮╭═──═╯ ． . ‧ ╰══─═──╮
║細雪紛然，悄落無聲├╯ . . . ╰═╮╭
│衣阡陌田野以素衣裳║˙ .‧ .‥ ． ．殘雪濁淖，不復瑩潔╰╯
│我心啊！請白潔勝雪║ ． , ˙ ‧. ． . 曾經底光華已為陳蹟
║請無垢無瑕 │ 然我心啊，如磐石無轉
╰═══──═──═╯╴╴╴╴╴╴╴╴╴╴╴╴╴╴╴╴╴仍燁然如昔 ψTassTW
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 71.207.151.97
※ 編輯: TassTW 來自: 71.207.151.97 (05/12 05:33)
推 thisday : 05/12 12:19
推 herstein :太用心了~~~推 05/12 23:29
→ recorriendo :但是其實原PO是問任何一個permutation 而不只限定在 05/14 10:28
→ recorriendo :multiply by n mod m 種類的permutation 05/14 10:29
→ TassTW :1. 就如你所說, 沒有聰明的辦法囉 05/16 05:14
→ TassTW :2. 就如我上面所說, 我只是想寫出那段紅字 哈哈 05/16 05:14