[군론](8)[순환군과 오일러 ϕ 함수]

 

오일러 $\phi$함수

ϕ(n) = |{$k \in \mathbb{Z} \ | \ 1 \le k \le n, \ gcd(n, k) = 1$}|
    즉, n보다 작거나 같은 수 중 서로소의 개수
    정수론 정리 8 참고

• 계산 성질
  ϕ(p) = p-1 (단, p = 소수)
  ϕ($p^k$) = $p^k-p^{k-1}$ (단, p = 소수)
  ϕ(mn) = ϕ(m)ϕ(n) (단, gcd(m, n) = 1)

 

순환군의 생성자의 수는 ϕ(n)이다

임의의 순환군 G = <a>에 대해 |G| = n일때,
n의 약수 d에 대해 항상 n = dk인 k가 존재하므로,
$a^{dk} = (a^k)^d = a^n = e$이고, 항상 위수가 d인 부분군을 생성자 $a^k$를 통해 만들 수 있다
-> 즉, 부분군의 생성자의 수 = n의 서로소의 수 = ϕ(n)

 

예) $\mathbb{Z}_{10}$의 생성자의 수?
    $\phi(10) = |{1, 3, 7, 9}| = 4$
    실제로 생성자는 {1, 3, 7, 9}

순환군에서 d|n일때, 위수가 d인 원소의 수 = ϕ(d)

• 증명
  G=<a>, |G| = n이고 d|n이라 하자
  d | n이므로 위수가 d인 유일한 부분군 H가 존재한다.
  이떄의 H의 생성원을 b라 하자
      <b> = H, |b| = |<b>| = |H| = d
  이때, H = <b^k>인 k의 수를 찾으면 된다
      |b^k| = |<b^k>| = |H| = d
      즉, k의 수를 찾는 것은 위수가 d인 원소의 수를 찾는 것이다
  $|b^k| = d = \frac{d}{gcd(d, k)}$
  따라서, gcd(d, k) = 1
      즉, 조건을 만족하는 k는 d와 서로소
  -> k의 수 = ϕ(d)

예) $\mathbb{Z}_{12}$의 위수가 6인 원소의 수?
    ϕ(6) = ϕ(2)ϕ(3) = 1 * 2 = 2개
    실제로 2, 10이 <2>의 생성자 (즉, 위수가 6인 원소)