代數學-請高手回答

Question

Find the number of generators of a cyclic group of order 72.

Answer 1

Ans: 72-72/2-72/3+72/6=24 個
1. 設原cyclic group 為G={ e, a, a², ..., a^71 },則
任意a^k, k與72互質者,均為G之 generator
原因如下:
設b=a^k, k>1, 則e, b, b², ..., b^71均不相同

若b^x=b^y, 71>x>y,則同乘b^y之反元素 b^(-y)
=> b^(x-y)=e 即 a^[k(x-y)]=e
=> k(x-y)為72之倍數
=> k為72之因數 (不合,因k與72互質)

故任意a^k (k與72互質,含k=1)均為G之generator

而1,2,3,...,72與72互質者共有 72 - 2倍數 - 3倍數 + 6倍數
=72-36-24+12
=24 個