원분 다항식

1. 개요

원분 다항식은 양의 정수 n에 대해 정의되는 다항식으로, 1의 원시 n제곱근들을 근으로 갖는다. 이는 뫼비우스 함수, 재귀적 정의를 통해 정의될 수 있으며, 기약 다항식이고 차수는 오일러 피 함수 φ(n)이다. 원분 다항식은 1의 거듭제곱근, 뫼비우스 반전 공식, 제곱 인수가 없는 정수 등과 밀접한 관련이 있으며, 계수는 정수이다.

2. 정의

양의 정수 $n$에 대하여, $n$번째 원분 다항식 $\backslash Phi\_n\backslash in\backslash mathbb\; Z[x]$은 다음과 같이 정의된다.

:$\backslash Phi\_n(x)\; =\; \backslash prod\_\{1\backslash le\; k\backslash le\; n\}^\{\backslash gcd\backslash \{k,n\backslash \}=1\}(x-\backslash exp(2\backslash pi\; ik/n))$

여기서 $\backslash gcd\backslash \{k,n\backslash \}=1$은 $k$와 $n$이 서로소라는 조건이며, 이 경우 $\backslash exp(2\backslash pi\; ik/n)$는 모든 1의 원시 $n$제곱근에 해당한다. ($\backslash exp(2\backslash pi\; ik/n)$은 흔히 $e^\{2\backslash pi\; ik/n\}$으로 쓴다.) 이 정의에 따라, $\backslash Phi\_n(x)$는 1의 원시 $n$제곱근들을 근으로 갖는 일계수 다항식이며, $\backslash phi(n)$차 다항식이다 ($\backslash phi$는 오일러 피 함수).

또, $\backslash Phi\_n(x)$는 다음과 같이 정의될 수 있다.

:$\backslash Phi\_n(x)\; =\; \backslash prod\_\{1\backslash le\; d\backslash le\; n\}^\{d\backslash mid\; n\}(x^d-1)^\{\backslash mu(n/d)\}$

여기서 $\backslash mu$는 뫼비우스 함수이다.

다른 정의로는 다음과 같은 수식이 있다.

:

셋째 정의는 재귀적이며, 이를 통해 $\backslash Phi\_n(x)$가 정수 계수 다항식임을 쉽게 알 수 있다. $\backslash Phi\_n(x)$가 기약 다항식임은 세 정의로부터 자명하지 않다. $\backslash Phi\_n(x)$이 $\backslash exp(2\backslash pi\; i/n)$의 $\backslash mathbb\; Q$에 대한 최소 다항식이라는 사실은 원분 다항식의 정의로 삼을 수 있다.

2.1. 1의 원시 n제곱근을 이용한 정의

양의 정수 $n$에 대하여, $n$번째 원분 다항식 $\backslash Phi\_n\backslash in\backslash mathbb\; Z[x]$은 다음과 같이 정의된다.

:$\backslash Phi\_n(x)\; =\; \backslash prod\_\{1\backslash le\; k\backslash le\; n\}^\{\backslash gcd\backslash \{k,n\backslash \}=1\}(x-\backslash exp(2\backslash pi\; ik/n))$

여기서 $\backslash gcd\backslash \{k,n\backslash \}=1$은 $k$와 $n$이 서로소라는 조건이며, 이 경우 $\backslash exp(2\backslash pi\; ik/n)$는 모든 1의 원시 $n$제곱근에 해당한다. ($\backslash exp(2\backslash pi\; ik/n)$은 흔히 $e^\{2\backslash pi\; ik/n\}$으로 쓴다.) 이 정의에 따라, $\backslash Phi\_n(x)$는 1의 원시 $n$제곱근들을 근으로 갖는 일계수 다항식이며, $\backslash phi(n)$차 다항식이다 ($\backslash phi$는 오일러 피 함수).

2.2. 뫼비우스 함수를 이용한 정의

양의 정수 $n$에 대하여, $n$번째 원분 다항식 $\backslash Phi\_n\backslash in\backslash mathbb\; Z[x]$은 다음과 같이 정의된다.

:$\backslash Phi\_n(x)\; =\; \backslash prod\_\{1\backslash le\; d\backslash le\; n\}^\{d\backslash mid\; n\}(x^d-1)^\{\backslash mu(n/d)\}$

여기서 $\backslash mu$는 뫼비우스 함수이다.

다른 정의로는 다음과 같은 수식들이 있다.

:$\backslash begin\{align\}$
\Phi_n(x)
& = \prod_{1\le k\le n}^{\gcd\{k,n\}=1}(x-\exp(2\pi ik/n)) \\
& = (x^n-1)\prod_{1\le d\end{align}


첫째 정의에서, $\backslash gcd\backslash \{k,n\backslash \}=1$은 $k$와 $n$이 서로소라는 조건이며, 이 경우 $\backslash exp(2\backslash pi\; ik/n)$는 모든 1의 원시 $n$제곱근에 해당한다. ($\backslash exp(2\backslash pi\; ik/n)$은 흔히 $e^\{2\backslash pi\; ik/n\}$으로 쓴다.) 이 정의에 따라, $\backslash Phi\_n(x)$는 1의 원시 $n$제곱근들을 근으로 갖는 일계수 다항식이며, $\backslash phi(n)$차 다항식이다 ($\backslash phi$는 오일러 피 함수). 셋째 정의는 재귀적이며, 이를 통해 $\backslash Phi\_n(x)$가 정수 계수 다항식임을 쉽게 알 수 있다.

2.3. 재귀적 정의

양의 정수 $n$에 대하여, $n$번째 원분 다항식$\backslash Phi\_n\backslash in\backslash mathbb\; Z[x]$은 다음과 같이 재귀적으로 정의될 수 있다.

:

이 정의를 통해 $\backslash Phi\_n(x)$가 정수 계수 다항식임을 쉽게 알 수 있다. $\backslash Phi\_n(x)$는 다음과 같이 정의할 수도 있다.

:$\backslash Phi\_n(x)\; =\; \backslash prod\_\{1\backslash le\; k\backslash le\; n\}^\{\backslash gcd\backslash \{k,n\backslash \}=1\}(x-\backslash exp(2\backslash pi\; ik/n))$
:$\backslash Phi\_n(x)\; =\; \backslash prod\_\{1\backslash le\; d\backslash le\; n\}^\{d\backslash mid\; n\}(x^d-1)^\{\backslash mu(n/d)\}$

첫째 정의에서 $\backslash gcd\backslash \{k,n\backslash \}=1$은 $k$와 $n$이 서로소라는 조건이며, 이 경우 $\backslash exp(2\backslash pi\; ik/n)$는 모든 1의 원시 $n$제곱근에 해당한다. ($\backslash exp(2\backslash pi\; ik/n)$은 흔히 $e^\{2\backslash pi\; ik/n\}$으로 쓴다.) 이 정의에 따라, $\backslash Phi\_n(x)$는 1의 원시 $n$제곱근들을 근으로 갖는 일계수 다항식이며, $\backslash phi(n)$차 다항식이다 ($\backslash phi$는 오일러 피 함수). 둘째 정의에서, $\backslash mu$는 뫼비우스 함수이다.

3. 성질

다음 성질들이 성립한다.

*$\backslash Phi\_n(x)$는 $\backslash mathbb\; Q[x]$의 기약 다항식이다. $\backslash Phi\_n$은 일계수 다항식이므로 원시 다항식이며, 따라서 $\backslash mathbb\; Z[x]$의 기약원이기도 하다.
*$\backslash Phi\_n(x)$의 차수는 $\backslash phi(n)$이며, 특히 $n\backslash ge3$일 때 짝수이다.
:$\backslash deg\backslash Phi\_n=\backslash phi(n)$
*모든 1의 $n$제곱근은 어떤 유일한 $n$의 (양의) 약수에 대한 원시 제곱근이므로, 다음 항등식이 성립한다.
:$x^n-1=\backslash prod\_\{d\backslash mid\; n\}\backslash Phi\_d(x)$
*이에 대한 뫼비우스 반전 공식은 다음과 같다.
:$\backslash Phi\_n(x)=\backslash prod\_\{d\backslash mid\; n\}(x^d-1)^\{\backslash mu(n/d)\}$
*$\backslash textstyle\; n\text{'}=\backslash prod\_\{p\backslash mid\; n\}p$가 $n$의 제곱 인수가 없는 약수 가운데 가장 큰 하나일 때, 다음이 성립한다. 이에 따라, 원분 다항식의 계산은 제곱 인수가 없는 지표의 경우로 귀결된다.
:$\backslash Phi\_n(x)=\backslash Phi\_\{n\text{'}\}(x^\{n/n\text{'}\})$

3.1. 기약성

$\backslash Phi\_n(x)$는 $\backslash mathbb\; Q[x]$의 기약 다항식이다. $\backslash Phi\_n$은 일계수 다항식이므로 원시 다항식이며, 따라서 $\backslash mathbb\; Z[x]$의 기약원이기도 하다.
$\backslash Phi\_n(x)$의 차수는 $\backslash phi(n)$이며, 특히 $n\backslash ge3$일 때 짝수이다.
:$\backslash deg\backslash Phi\_n=\backslash phi(n)$
모든 1의 $n$제곱근은 어떤 유일한 $n$의 (양의) 약수에 대한 원시 제곱근이므로, 다음 항등식이 성립한다.
:$x^n-1=\backslash prod\_\{d\backslash mid\; n\}\backslash Phi\_d(x)$
이에 대한 뫼비우스 반전 공식은 다음과 같다.
:$\backslash Phi\_n(x)=\backslash prod\_\{d\backslash mid\; n\}(x^d-1)^\{\backslash mu(n/d)\}$
$\backslash textstyle\; n\text{'}=\backslash prod\_\{p\backslash mid\; n\}p$가 $n$의 제곱 인수가 없는 약수 가운데 가장 큰 하나일 때, 다음이 성립한다. 이에 따라, 원분 다항식의 계산은 제곱 인수가 없는 지표의 경우로 귀결된다.
:$\backslash Phi\_n(x)=\backslash Phi\_\{n\text{'}\}(x^\{n/n\text{'}\})$

3.2. 차수

* $\backslash Phi\_n(x)$의 차수는 $\backslash phi(n)$이며, 특히 $n\backslash ge3$일 때 짝수이다.
*:$\backslash deg\backslash Phi\_n=\backslash phi(n)$

3.3. 1의 거듭제곱근과의 관계

모든 1의 $n$제곱근은 어떤 유일한 $n$의 (양의) 약수에 대한 원시 제곱근이므로, 다음 항등식이 성립한다.
:$x^n-1=\backslash prod\_\{d\backslash mid\; n\}\backslash Phi\_d(x)$
이에 대한 뫼비우스 반전 공식은 다음과 같다.
:$\backslash Phi\_n(x)=\backslash prod\_\{d\backslash mid\; n\}(x^d-1)^\{\backslash mu(n/d)\}$
$\backslash textstyle\; n\text{'}=\backslash prod\_\{p\backslash mid\; n\}p$가 $n$의 제곱 인수가 없는 약수 가운데 가장 큰 하나일 때, 다음이 성립한다. 이에 따라, 원분 다항식의 계산은 제곱 인수가 없는 지표의 경우로 귀결된다.
:$\backslash Phi\_n(x)=\backslash Phi\_\{n\text{'}\}(x^\{n/n\text{'}\})$

3.4. 뫼비우스 반전 공식

뫼비우스 반전 공식에 따라 다음이 성립한다.

:$\backslash Phi\_n(x)=\backslash prod\_\{d\backslash mid\; n\}(x^d-1)^\{\backslash mu(n/d)\}$

3.5. 제곱 인수가 없는 정수

다음 성질들이 성립한다.
* $\backslash textstyle\; n\text{'}=\backslash prod\_\{p\backslash mid\; n\}p$가 $n$의 제곱 인수가 없는 약수 가운데 가장 큰 하나일 때, 다음이 성립한다. 이에 따라, 원분 다항식의 계산은 제곱 인수가 없는 지표의 경우로 귀결된다.
*:$\backslash Phi\_n(x)=\backslash Phi\_\{n\text{'}\}(x^\{n/n\text{'}\})$

3.6. 계수

모든 정수는 어떤 원분 다항식의 계수이다. 특히, (낮은 차수에서와 달리) 원분 다항식의 계수는 $\backslash -1,0,1\backslash \}$로 이루어질 필요가 없다. $n\backslash ge2$에 대하여, $\backslash Phi\_n(x)$의 계수들은 “회문”을 이룬다 ($a\_0=a\_\{\backslash phi(n)\}=1,a\_1=a\_\{\backslash phi(n)-1\},\backslash dots$). $n\backslash ge3$에 대하여, $\backslash Phi\_n(x)$의 가운데 항 계수(즉, $n/2$차항 계수)는 0이거나 ($n\backslash in\backslash \{2^2,2^3,\backslash dots\backslash \}$) 홀수이다 ($n\backslash not\backslash in\backslash \{2^2,2^3,\backslash dots\backslash \}$).

3.7. 값

원분 다항식의 특정 수에서의 값들은 다음과 같다.

*$\backslash Phi\_n(0)=1$

*$\backslash Phi\_n(1)=\backslash begin\{cases\}$
0 & n=1 \\
p & \exists p\in\{2,3,5,7,11,\dots\}\colon n\in\{p,p^2,p^3,\dots\} \\
1 & n\ne1\land\not\exists p\in\{2,3,5,7,11,\dots\}\colon n\in\{p,p^2,p^3,\dots\}
\end{cases}


*$\backslash Phi\_n(-1)=\backslash begin\{cases\}$
-2 & n=1 \\
0 & n=2 \\
1 & n\in\{3,5,7,9,\dots\} \\
-n & n\in\{4,6,8,10,\dots\}
\end{cases}

4. 예

4.1. 작은 지표

처음 몇 원분 다항식은 다음과 같다.
:Φ₁(x) = x - 1
:Φ₂(x) = x + 1
:Φ₃(x) = x² + x + 1
:Φ₄(x) = x² + 1
:Φ₅(x) = x⁴ + x³ + x² + x +1
:Φ₆(x) = x² - x + 1
:Φ₇(x) = x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
:Φ₈(x) = x⁴ + 1
:Φ₉(x) = x⁶ + x³ + 1
:Φ₁₀(x) = x⁴ - x³ + x² - x + 1
:Φ₁₁(x) = x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
:Φ₁₂(x) = x⁴ - x² + 1
:Φ₁₃(x) = x¹² + x¹¹ + x¹⁰ + x⁹ + x⁸ + x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² + x + 1
:Φ₁₄(x) = x⁶ - x⁵ + x⁴ - x³ + x² - x + 1
:Φ₁₅(x) = x⁸ - x⁷ + x⁵ - x⁴ + x³ - x + 1

원분 다항식의 계수가 반드시 {-1, 0, 1}에 속하는 것은 아니다. 예를 들어, 105번째 원분 다항식 Φ₁₀₅(x)의 7차항 계수는 -2이다. 105는 서로 다른 세 소수(3, 5, 7)의 곱이며, 이는 이러한 반례가 나타나는 첫 번째 경우이다.

4.2. Φ_p

소수 $p$에 대하여,
:$\backslash Phi\_p(x)=\backslash frac\{x^p-1\}\{x-1\}=x^\{p-1\}+\backslash cdots+x+1$
이다. $\backslash Phi\_p(x)$가 기약 다항식임을 보이는 것은 아이젠슈타인 판정법에 따라 더 쉽다.

4.3. Φ_pq

임의의 두 소수 p
두 소수 p:Φ_pq(x) = (x^pq-1)(x-1) / (x^p-1)(x^q-1)
이다.

특히, Φ_pq(x)는 φ(pq)=(p-1)(q-1)차 다항식이며, 계수는 {-1,0,1}로 이루어지며, 계수 1의 항이 계수 −1의 항보다 하나 더 많다(Φ_pq(1)=1). 또한, Φ_pq(x)의 가운데 항 계수((p-1)(q-1)/2차항 계수)는 (-1)^r(p,q)이다.