The number of elements of order k in an abelian group.

The number of elements of order $k$ in an abelian group.

i) Cyclic Group

In a cyclic group of order $N$, there exist $\phi(k)$ elements of order $k$ if $k$ divides $N$ and $0$ if not.
Proof.
Let $G=<a>$ and $|a^m|=\frac{N}{\text{gcd}(N,m)}=k$, then $\text{gcd}(N,m)=N/k$. If $k$ divides $N$, $N/k|m, m=pN/k$. $\text{gcd}(N,pN/k)=N/k$, $\text{gcd}(k,p)=1$. So there exist $\phi(k)$ $p$'s, meaning there exist $\phi(k)$ $m$'s such that $|a^m|=k$. Therefore, there exist $\phi(k)$ elements of order $k$ if $k$ divides $N$ and $0$ if not.


ii) Abelian Group - prime number

Let $a_1$ be an element of order $p$, where $p$ is a prime. Then $a_1, a_1^2, a_1^3,...,a_1^{p-1}$ are of order $p$. - There are $p-1$ elements of order $p$ in $<a_1>$.

Let $a_2$ be an element of order $p$ that cannot be generated by $a_1$. Then $a_2, a_2^2, a_2^3,...,a_2^{p-1}$ are of order $p$. Consider $a_1a_2$, of which the order can be either $1$ or $p$. (See here for reason.) If the order is $1$, $a_1a_2=e$, so it is a contradiction to the fact that $a_2$ cannot be generated by $a_1$. So $a_1a_2$ is of order $p$. By the same logic, $a_1^ma_2^n$ where $n,m=1,2,3,...,p-1$ are of order $p$. Furthermore, we can say all the elements of $<a_1,a_2>$ except for the identity element, $a_1^ma_2^n$ where $n,m=0, 1,2,3,...,p-1$, except for the case $m=n=0$, are of order $p$.  - There are $p^2-1$ elements of order $p$ in $<a_1,a_2>$.

Expanding this by introducing $a_3$ which cannot be generated by $a_1$ nor $a_2$, $a_1^ma_2^na_3^o$ where $n,m,o=0, 1,2,3,...,p-1$, except for the case $m=n=o=0$, are of order $p$. - There are $p^3-1$ elements of order $p$ in $<a_1,a_2,a_3>$.

Repeating the process, we can conclude that there are $p^i-1$ elements of order $p$ in the subgroup $<a_1,a_2,...,a_i>$, where $i$ is a positive integer. Any element not in the subgroup $<a_1,a_2,...,a_i>$ cannot be of order $p$ since if there is, we should have repeated the process by setting it as a new $a_{i+1}$. Therefore, there are $p^i-1$ elements of order $p$.

iii) Abelian Group - square-free number

Let $a$ be an element of order $w$, where $w$ is a square-free integer. So, $w=p_1p_2...p_k$. Then $a^{w/p_i}$ is of order $p_i$ for $i=1,2,...,k$. By Bézout Identity, $\text{gcd}(w/p_1,w/p_2,...,w/p_k)=1$, so there exist integers $x_1, x_2,...,x_k$ such that $(w/p_1)x_1+(w/p_2)x_2+...+(w/p_k)x_k=1$, which means that $a$ can be generated by $a^{w/p_1}, a^{w/p_2},...,a^{w/p_k}$, of orders, respectively $p_1, p_2, ...,p_k$.

This concludes that every element of order $w$ can be shown as a product of elements of orders $p_1,p_2,...,p_k$.

By the result of ii), there are $p_1^{i_1}-1$ elements of order $p_1$, $p_2^{i_2}-1$ elements of order $p_2$, ..., $p_k^{i_k}-1$ elements of order $p_k$. Therefore, there exist $(p_1^{i_1}-1)(p_2^{i_2}-1)...(p_k^{i_k}-1)$ elements of order $w$.

iv) Abelian Group - prime power number

Let $a_1$ be an element of order $p^h$, where $p$ is a prime. Then by the result of i), there are $\phi(p^h)=p^h-p^{h-1}$ elements of order $p^h$ in the cyclic subgroup $<a_1>$.

Let $a_2$ be an element of order $p^h$ that cannot be generated by $a_1$. Consider $z\in<a_1,a_2>$. Its order can be $p^i$, where $i=0,1,2,...,h$ (See here for reason.) - There are $p^{2h}$ elements of order $1,p,p^2,...,p^h$ in $<a_1,a_2>$. By the same logic, there are $p^{2(h-1)}$ elements of order $1,p,p^2,...,p^{h-1}$ in $<a_1,a_2>$. Therefore, there are $p^{2h}-p^{2(h-1)}$ elements of order $p^h$ in $<a_1,a_2>$.

Expanding this by introducing $a_3$ which cannot be generated by $a_1$ nor $a_2$. - There are $p^{3h}-p^{3(h-1)}$ elements of order $p^h$ in $<a_1,a_2,a_3>$.

Repeating the process, we can conclude that there are $p^{ih}-p^{i(h-1)}$ elements of order $p^h$ in the subgroup $<a_1,a_2,...,a_i>$, where $i$ is a positive integer. Any element not in the subgroup $<a_1,a_2,...,a_i>$ cannot be of order $p^h$. Therefore, there are $p^{ih}-p^{i(h-1)}$ elements of order $p^h$.

v) Abelian Group - composite number

Let $a$ be an element of order $w$, where $w$ is a composite number. So, $w=p_1^{h_1}p_2^{h_2}...p_k^{h_k}$. Then $a^{w/p_i^{h_i}}$ is of order $p_i^{h_i}$ for $i=1,2,...,k$. By Bézout Identity, $\text{gcd}(w/p_1^{h_1},w/p_2^{h_2},...,w/p_k^{h_k})=1$, so there exist integers $x_1, x_2,...,x_k$ such that $(w/p_1^{h_1})x_1+(w/p_2^{h_2})x_2+...+(w/p_k^{h_k})x_k=1$, which means that $a$ can be generated by $a^{w/p_1^{h_1}}, a^{w/p_2^{h_2}},...,a^{w/p_k^{h_k}}$, of orders, respectively $p_1^{h_1}, p_2^{h_2}, ...,p_k^{h_k}$.

This concludes that every element of order $w$ can be shown as a product of elements of orders $p_1^{h_1},p_2^{h_2},...,p_k^{h_k}$.

By the result of iv), there are $p^{i_1h_1}-p^{i_1(h_1-1)}$ elements of order $p_1^{h_1}$, $p_2^{i_2h_2}-p^{i_2(h_2-1)}$ elements of order $p_2^{h_2}$, ..., $p_k^{i_kh_k}-p^{i_k(h_k-1)}$ elements of order $p_k^{h_k}$. Therefore, there exist $(p^{i_1h_1}-p^{i_1(h_1-1)})(p_2^{i_2h_2}-p^{i_2(h_2-1)})...(p_k^{i_kh_k}-p^{i_k(h_k-1)})$ elements of order $w$.

 

---

Below is the Korean translation. 아래는 한국어 번역입니다. 영어로 먼저 작성했으며 한국어 번역은 Gemini가 번역해주었습니다.

가환군에서 위수가 $k$인 원소의 개수

i) 순환군 (Cyclic Group)

위수가 $N$인 순환군에서, $k$가 $N$의 약수라면 위수가 $k$인 원소는 $\phi(k)$개 존재하며, 약수가 아니라면 0개 존재한다.

증명:

$G=\langle a \rangle$라 하고, $|a^m|=\frac{N}{\text{gcd}(N,m)}=k$라고 하자. 그러면 $\text{gcd}(N,m)=N/k$이다. $k$가 $N$의 약수라면, $N/k$는 $m$의 약수이므로 $m=p(N/k)$로 쓸 수 있다. 이때 $\text{gcd}(N, pN/k)=N/k$이려면 $\text{gcd}(k,p)=1$이어야 한다. 따라서 이러한 조건을 만족하는 $p$는 $\phi(k)$개 존재하며, 이는 곧 $|a^m|=k$를 만족하는 $m$이 $\phi(k)$개 존재함을 의미한다. 그러므로 위수가 $k$인 원소는 $k|N$일 때 $\phi(k)$개 존재하고, 그렇지 않으면 0개 존재한다.

ii) 가환군 - 소수 위수 (Abelian Group - prime number)

위수가 소수 $p$인 원소 $a_1$을 생각하자. 그러면 $a_1, a_1^2, a_1^3, \dots, a_1^{p-1}$은 모두 위수가 $p$이다. 즉, 순환 부분군 $\langle a_1 \rangle$ 안에는 위수 $p$인 원소가 $p-1$개 있다.

이제 $a_1$에 의해 생성되지 않는 위수 $p$인 원소 $a_2$를 생각하자. 원소 $a_1 a_2$의 위수는 1 또는 $p$가 될 수 있다. 만약 위수가 1이라면 $a_1 a_2 = e$이므로 $a_2 = a_1^{-1}$이 되어 $a_2$가 $a_1$에 의해 생성되지 않는다는 사실에 모순된다. 따라서 $a_1 a_2$의 위수는 $p$이다. 동일한 논리로 $m, n = 1, 2, 3, \dots, p-1$인 $a_1^m a_2^n$의 위수는 모두 $p$이다. 나아가 $\langle a_1, a_2 \rangle$의 원소 중 항등원($m=n=0$인 경우)을 제외한 $a_1^m a_2^n$ 형태의 모든 원소는 위수가 $p$라고 할 수 있다. 따라서 $\langle a_1, a_2 \rangle$ 안에는 위수 $p$인 원소가 $p^2-1$개 존재한다.

이 과정을 $a_1, a_2$에 의해 생성되지 않는 $a_3$를 도입하여 확장하면, $m, n, o = 0, 1, 2, \dots, p-1$인 $ a_1^ma_2^na_3^o $ 중 $m=n=o=0$인 경우를 제외하고는 모두 위수가 $p$이다. 즉, $\langle a_1, a_2, a_3 \rangle$ 안에는 위수 $p$인 원소가 $p^3-1$개 존재한다.

이 과정을 반복하면, 양의 정수 $i$에 대하여 부분군 $\langle a_1, a_2, \dots, a_i \rangle$ 안에는 $p^i-1$개의 위수 $p$인 원소가 있다는 결론을 얻을 수 있다. 이 부분군에 속하지 않는 원소는 위수가 $p$일 수 없는데, 만약 존재한다면 그 원소를 새로운 $a_{i+1}$로 설정하여 과정을 반복했을 것이기 때문이다. 그러므로 위수가 $p$인 원소는 총 $p^i-1$개 존재한다.

iii) 가환군 - 제곱 인수가 없는 수 (Abelian Group - square-free number)

$w$가 제곱 인수가 없는 정수(square-free integer)이고, $a$의 위수가 $w$라고 하자. 그러면 $w=p_1 p_2 \dots p_k$로 소인수분해된다. 이때 각 $i=1, 2, \dots, k$에 대해 $a^{w/p_i}$의 위수는 $p_i$이다. 베주 항등식(Bézout Identity)에 의해 $\text{gcd}(w/p_1, w/p_2, \dots, w/p_k)=1$이므로, $(w/p_1)x_1 + (w/p_2)x_2 + \dots + (w/p_k)x_k = 1$을 만족하는 정수 $x_1, x_2, \dots, x_k$가 반드시 존재한다. 이는 곧 $a$가 각각 위수가 $p_1, p_2, \dots, p_k$인 원소들 $a^{w/p_1}, a^{w/p_2}, \dots, a^{w/p_k}$에 의해 생성될 수 있음을 의미한다.

결론적으로 위수가 $w$인 모든 원소는 위수가 $p_1, p_2, \dots, p_k$인 원소들의 곱으로 나타낼 수 있다.

ii)의 결과에 따라, 위수 $p_1$인 원소는 $p_1^{i_1}-1$개, 위수 $p_2$인 원소는 $p_2^{i_2}-1$개, $\dots$, 위수 $p_k$인 원소는 $p_k^{i_k}-1$개 존재한다. 따라서 위수가 $w$인 원소의 개수는 $(p_1^{i_1}-1)(p_2^{i_2}-1)\dots(p_k^{i_k}-1)$개이다.

iv) 가환군 - 소수의 거듭제곱 (Abelian Group - prime power number)

$p$가 소수일 때, 위수가 $p^h$인 원소 $a_1$을 생각하자. i)의 결과에 의해 순환 부분군 $\langle a_1 \rangle$ 안에는 위수가 $p^h$인 원소가 $\phi(p^h)=p^h-p^{h-1}$개 존재한다.

이제 $a_1$에 의해 생성되지 않는 위수 $p^h$인 원소 $a_2$를 생각하자. $z \in \langle a_1, a_2 \rangle$인 원소 $z$의 위수는 $i=0, 1, 2, \dots, h$인 $p^i$가 될 수 있다. 이때 $\langle a_1, a_2 \rangle$ 안에서 위수가 $1, p, p^2, \dots, p^h$인 원소(즉, 위수가 $p^h$ 이하인 모든 원소)의 개수는 $p^{2h}$개이다. 같은 논리로 위수가 $1, p, p^2, \dots, p^{h-1}$인 원소의 개수는 $p^{2(h-1)}$개이다. 그러므로 $\langle a_1, a_2 \rangle$ 안에서 위수가 정확히 $p^h$인 원소의 개수는 $p^{2h}-p^{2(h-1)}$개이다.

이 과정을 $a_1, a_2$에 의해 생성되지 않는 $a_3$를 도입하여 확장하면, $\langle a_1, a_2, a_3 \rangle$ 안에서 위수가 $p^h$인 원소의 개수는 $p^{3h}-p^{3(h-1)}$개가 된다.

이 과정을 반복하면, 양의 정수 $i$에 대하여 부분군 $\langle a_1, a_2, \dots, a_i \rangle$ 내에 위수가 $p^h$인 원소는 $p^{ih}-p^{i(h-1)}$개 존재한다는 결론을 얻는다. 이 부분군에 속하지 않는 원소는 위수가 $p^h$일 수 없다. 따라서 위수가 $p^h$인 원소의 총 개수는 $p^{ih}-p^{i(h-1)}$개이다.

v) 가환군 - 합성수 (Abelian Group - composite number)

$w$가 합성수이고 $a$의 위수가 $w$라고 하자. $w=p_1^{h_1} p_2^{h_2} \dots p_k^{h_k}$로 소인수분해될 때, 각 $i=1, 2, \dots, k$에 대해 $a^{w/p_i^{h_i}}$의 위수는 $p_i^{h_i}$이다. 베주 항등식에 의해 $\text{gcd}(w/p_1^{h_1}, w/p_2^{h_2}, \dots, w/p_k^{h_k})=1$이므로, $(w/p_1^{h_1})x_1 + (w/p_2^{h_2})x_2 + \dots + (w/p_k^{h_k})x_k = 1$을 만족하는 정수 $x_i$들이 존재한다. 이는 $a$가 각각 위수가 $p_1^{h_1}, p_2^{h_2}, \dots, p_k^{h_k}$인 원소들에 의해 생성될 수 있음을 뜻한다.

따라서 위수가 $w$인 모든 원소는 위수가 $p_1^{h_1}, p_2^{h_2}, \dots, p_k^{h_k}$인 원소들의 곱으로 표현될 수 있다.

iv)의 결과에 따라, 위수 $p_1^{h_1}$인 원소는 $p_1^{i_1 h_1}-p_1^{i_1(h_1-1)}$개, 위수 $p_2^{h_2}$인 원소는 $p_2^{i_2 h_2}-p_2^{i_2(h_2-1)}$개, $\dots$, 위수 $p_k^{h_k}$인 원소는 $p_k^{i_k h_k}-p_k^{i_k(h_k-1)}$개 존재한다. 그러므로 위수가 $w$인 원소의 총 개수는 다음과 같다.

$(p_1^{i_1 h_1}-p_1^{i_1(h_1-1)})(p_2^{i_2 h_2}-p_2^{i_2(h_2-1)}) \dots (p_k^{i_k h_k}-p_k^{i_k(h_k-1)})$

 

 

연습문제

군에서 위수가 21인 원소의 개수가 될 수 있는 정확한 수는 다음 중 무엇인가?

1. 21600

2. 21602

3. 21604

(현대대수학 바이블 10판 p.109)

 

위수가 35인 가환군 $G$의 모든 원소가 방정식 $x^{35}=e$를 만족한다고 하자. $G$가 순환군임을 증명하라. 만약 35를 33으로 바꾸더라도 이 주장은 유효할까? - 참고: 유한군의 모든 원소들의 위수는 그 군의 위수를 나눈다 ( 라그랑주 정리의 따름정리 2 ) 

(현대대수학 바이블 10판 p.107)