[BOJ 3904] The Teacher's Side of Math

이 문제는 서로 다른 두 소수 $p,q$에 대해서 $p^{1/n}+q^{1/m}(n,m\in \mathbb{N}_{\ge 1}$의 최소 다항식을 구하는 문제이다. 아래 두 개의 lemma를 증명하며 최소 다항식을 구하는 방법을 알아보자.

 

$K$가 $F$의 field extension이라 하자. 

Lemma 1. $\forall \alpha \in K$, $\alpha$ acting by left-multiplication on $K$ is a $F$-linear transformation of $K$.

 

Proof. 임의의 $x, y\in K$와 $a, b\in F$를 잡자. 그럼 $\alpha(ax+by)=\alpha ax+\alpha by = a(\alpha x)+b(\alpha y)$가 된다. 따라서 이것은 $F$-linear transformation이다.

 

Lemma 2. $K$ is isomorphic to the subfield of the ring of $n\times n$ matrices over $F$.

 

Proof. $\varphi$를 $\alpha$에서 $F^{n}\rightarrow F^{n}$ 사이의 선형 변환으로 대응시키는 함수라고 하자. 먼저 $\alpha +\beta$를 생각해보자. 이것은 $x\in K$에 $(\alpha+\beta)x$로 작용한다. 이때 저 식은 $\alpha x+\beta x$로 쓸 수 있으므로 $\varphi(\alpha+\beta)=\varphi(\alpha+\beta)$가 된다. 또한 action의 정의에 의해 선형 변환을 $\phi_{\alpha}$라고 하면 $\phi_{\alpha \beta}=\phi_{\alpha}(\phi_{\beta})$이다. 따라서 $\varphi(\alpha \beta)=\varphi(\alpha)\varphi(\beta)$ 이다. $\varphi$임이 ring homomorphism임을 증명했다. $K$가 field이므로 $\varphi$는 injective거나 0이다. 하지만 $\varphi \ne 0$이므로 $\varphi$는 injective하다. 따라서 $M$의 subfield 중 $K$와 isomorphic 한 것이 존재한다. 

 

그럼 행렬 중에서 $\alpha$에 대응되는 것을 $M_{\alpha}$라고 잡자. 이때 다음 상황을 생각할 수 있다.

\[M_{\alpha}x=\alpha x (x\in K)\]

$x\ne 0 $이라면 $\alpha$는 eigenvalue의 정의에 의해 $M_{\alpha}$의 eigenvalue가 된다. 따라서 $M_{\alpha}$의 특성 다항식은 $\alpha$를 근으로 가진다. 우리가 $[F(\alpha):F]=n$ 임을 알고 있다면 $\alpha$가 $n$차 최소 다항식을 가짐을 알 수 있다. 그럼 matrix를 $n \times n$ 크기로 잡으면 그것의 특성 다항식이 $\alpha$의 최소 다항식이 된다. 다음과 같은 field extension을 고려하자. 

\[[\mathbb{Q}(p^{1/n}+q^{1/m}):\mathbb{Q}]=[\mathbb{Q}(p^{1/n}+q^{1/m}):\mathbb{Q}(p^{1/n})][\mathbb{Q}(p^{1/n}):\mathbb{Q}]=n[\mathbb{Q}(p^{1/n}+q^{1/m}):\mathbb{Q}(p^{1/n})]\]

그럼 결국 degree of extension이 $nm$이 되는데 이는 증명을 못했다.(나중에 추가할 예정) 따라서 $nm \times nm$ 행렬을 구상하면 된다. 행렬을 구상할 때 다음과 같은 사실을 이용한다. 각각의 column과 row가 한 basis에 대응된다고 했을 때 각 column에 해당하는 basis에 $\alpha$를 곱해서 나온 값을 basis들의 선형 결합으로 표현할 수 있다. 예를 들어보자. 우리가 $\sqrt{2}+\sqrt{3}$의 최소 다항식을 구하고 싶다. 이들의 basis는 $1,\sqrt{2},\sqrt{3},\sqrt{6}$이다. 1번 row부터 4번 row까지 앞서 나온 basis의 순서대로 대응시키자. column도 마찬가지로 하자. 그럼 다음과 같은 4개의 사실을 얻는다.

\[1\cdot (\sqrt{2}+\sqrt{3}) = \sqrt{2}+\sqrt{3}\]

\[\sqrt{2}\cdot (\sqrt{2}+\sqrt{3}) = 2+\sqrt{6}\]

\[\sqrt{3}\cdot (\sqrt{2}+\sqrt{3}) = \sqrt{6}+3\]

\[\sqrt{6}\cdot (\sqrt{2}+\sqrt{3})=2\sqrt{3}+3\sqrt{2}\]

이것을 그대로 행렬에 대응시키면

\[\begin{bmatrix} 0 & 2 & 3 & 0 \\ 1 & 0 & 0 & 3 \\ 1 & 0 & 0 & 2 \\ 0 & 1 & 1 & 0 \end{bmatrix}\]

이것의 특성 방정식을 구하면 $x^{4}-10x^{2}+1$이 되고 $x=\sqrt{2}+\sqrt{3}$일 때의 값이 $0$이 된다.

아래는 이것을 구현한 코드이다.

 

# 보려면 클릭

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef vector<int> poly;
int mat[21][21];
 
void det(poly &ret, int M[][21], int siz){
    if(siz == 2){
        if(M[0][0] == 1e9){
            if(M[1][1] == 1e9) ret[2] = 1;
            else ret[1] = M[1][1];
        }
        else{
            if(M[1][1] == 1e9) ret[1] = M[0][0];
            else ret[0] = M[1][1] * M[0][0];
        }
        if(M[0][1] == 1e9){
            if(M[1][0] == 1e9) ret[2] -= 1;
            else ret[1] -= M[1][0];
        }
        else{
            if(M[1][0] == 1e9) ret[1] -= M[0][1];
            else ret[0] -= M[1][0] * M[0][1];
        }
        return;
    }
    int c[21][21];
    for(int j = 1;j < siz;j++){
        for(int k = 1;k < siz;k++){
            c[j - 1][k - 1] = M[j][k];
        }
    }
    if(M[0][0]){
        poly a(21);
        int mu = 1;
        det(a, c, siz - 1);
 
        if(M[0][0] == 1e9){
            for(int j = 20;j > 0;j--){
                a[j] = a[j - 1];
            }
            a[0] = 0;
        } 
        else mu *= M[0][0];
        for(int j = 0;j < 21;j++){
            ret[j] += a[j] * mu;
        }
    }
    
    for(int i = 1;i < siz;i++){
        for(int j = 1;j < siz;j++){
            c[j - 1][i - 1] = M[j][i - 1];
        }
        if(M[0][i] == 0) continue;
        
        poly a(21);
        int mu = 1;
        if(i % 2) mu = -1;
        det(a, c, siz - 1);
 
        if(M[0][i] == 1e9){
            for(int j = 20;j > 0;j--){
                a[j] = a[j - 1];
            }
            a[0] = 0;
        }
        else mu *= M[0][i];
        for(int j = 0;j < 21;j++){
            ret[j] += a[j] * mu;
        }
    }
}
int main(){
    int i, j;
    int n, p, m, q, siz, pt;
    while(1){
        pt = 0;
        scanf("%d %d %d %d",&p, &n, &q, &m);
        if(p == 0) break;
        siz = n * m;
        for(i = 0;i < n;i++){
            for(j = 0;j < m;j++){
                if(i + 1 == n) mat[j][pt] += p;
                else mat[(i + 1) * m + j][pt]++;
                if(j + 1 == m) mat[i * m][pt] += q;
                else mat[i * m + j + 1][pt]++;
                pt++;
            }
        }
        for(i = 0;i < siz;i++){
            for(j = 0;j < siz;j++){
                mat[i][j] = -mat[i][j];
            }
            mat[i][i] = 1e9;
        }
        
        poly ans(21);
        det(ans, mat, siz);
        for(i = siz;i >= 0;i--){
            printf("%d ", ans[i]);
        }
        printf("\n");
        for(i = 0;i < siz;i++){
            for(j = 0;j < siz;j++){
                mat[i][j] = 0;
            }
        }
    }
}

# 닫기