通過移位形成的置換群的置換數(shù)

1、通過移位形成的置換群的置換數(shù)有這樣一個結(jié)論，通過移位形成的置換群的置換數(shù)是gcd(NM)，其中N是置換群的元素個數(shù)，M是移位的位數(shù)。例如N=6M=2的置換群的置換數(shù)是gcd(62)=2012345234501形成的置換是[240][351]?？紤]一下為什么是這樣的，一個直觀的入手點(diǎn)就是嘗試幾個例子，然后分析一下置換是怎樣形成的，清楚了這個自然也就明白了置換數(shù)會是多少。假設(shè)我們移位m，并且從base位置開始尋找置換，那么置換將會是(mxb

2、ase)%n(x是自然數(shù))得到的數(shù)字。例如N=9M=6時012345678678012345從base=0位置對應(yīng)開始[61%9=662%9=363%9=0]從base=1位置對應(yīng)開始[(611)%9=7(621)%9=4(631)%9=1]從base=2位置對應(yīng)開始[(612)%9=8(622)%9=5(632)%9=2]。對于這個例子觀察發(fā)現(xiàn)，形成的置換貌似就是模gcd(NM)的同余類。看看這是不是正確的，前面的分析過程使我們將置換

3、轉(zhuǎn)換為(mxbase)%n這樣的一個式子，也就是說這個式子的結(jié)果根據(jù)base的不同為什么會形成模gcd(mn)的同余類。經(jīng)過試錯的思考，我得出了下面的分析，在這里base(m(y–x))%n=0，當(dāng)x=0時，my%n=0，也就是要證明滿足此式子的y0的最小值是ngcd(nm)，我們假設(shè)bngcd(nm)時，mb|n，顯然mb|m，那么mb就是n和m的最小公倍數(shù)，但是bmnmgcd(nm)的，右邊才是最小公倍數(shù)，所以是矛盾的。（這個證明關(guān)