Fermat's Little Theorem of Circulant Matrix

해당 글에서는 $\mathbb{Z}/p\mathbb{Z}$ 상의 순환 행렬에 대해 페르마 소정리가 성립함을 증명한다.

Theoretical Background

1. 페르마 소정리

소수 $p$와 정수 $a$에 대해 $a\equiv a^p(\text{mod }p)$가 성립한다.

2. 순환 행렬

$\mathbb{Z}/p\mathbb{Z}$ 상의 $n\times n$ 행렬 $M$이 다음과 같은 성질을 만족하면 $M$은 순환 행렬이다.
$$\mathrm{\forall }i,j,a,b\in \mathbb{Z}/p\mathbb{Z}\text{ which satisfies }i-j\equiv a-b(\text{mod }n),M_{ij}=M_{ab}$$

Proof

1. Matrix Expression of polynomial multiplication

다항식 $f(x)={\displaystyle \sum _{k=0}^n{a}_k{x}^k}$를 다음과 같은 벡터에 대응시켜보자.
$$v=\left[\begin{array}{c}{a}_0\\ a_1\\ ⋮\\ a_n\end{array}\right]$$
다항식 $f,g$ 곱셈에서 $x^c$의 계수는 $a+b=c$를 만족하는 음이 아닌 가능한 모든 정수쌍 $a,b$에 대해 $f$의 $x^a$의 계수와 $g$의 $x^b$의 계수를 합한 값과 같으며, 두 $n$차 다항식을 곱하면 최대 $2n$차가 된다는 것은 익히 알려져 있다. 이를 고려할 때, '다항식 $f$를 곱한다'는 연산은 다음과 같은 $(2n+1)\times (n+1)$행렬로 표현할 수 있다.

$$\left[\begin{array}{cccc}{a}_0& 0& \cdots & 0\\ a_1& a_0& \cdots & 0\\ a_2& a_1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & a_n\end{array}\right]$$

2. Polynomial multiplication over $\mathbb{Z}/p\mathbb{Z}$

페르마 소정리에 의하여 0이 아닌 $x\in \mathbb{Z}/p\mathbb{Z}$는 $x^{p-1}\equiv 1(\text{mod }p)$를 만족하므로, $\mathbb{Z}/p\mathbb{Z}$에서 정의되며 근을 갖지 않는 다항식 $f$를 다음과 같은 $(p-1)\times (p-1)$ 순환 행렬에 대응시키면, 다항식 $f,g$와 이에 대응하는 행렬 $M_f,M_g$에 대해서 $f\times g$가 $M_f\times M_g$에 대응된다는 성질을 확인할 수 있다. 따라서 다항식을 $f$을 벡터가 아닌, 순환 행렬에 대응시키면 더 자연스러운 대응 관계를 관찰할 수 있다.

$$\left[\begin{array}{cccc}{a}_0& a_{p-2}& \cdots & a_1\\ a_1& a_0& \cdots & a_2\\ a_2& a_1& \cdots & a_3\\ ⋮& ⋮& \ddots & ⋮\\ a_{p-2}& a_{p-3}& \cdots & a_0\end{array}\right]$$

3. Fermat's Little Theorem of Circulant Matrix

(2.)에서의 관찰을 귀납적으로 적용하면, $\mathbb{Z}/p\mathbb{Z}$ 상에서 정의되고 근을 갖지 않는 $(p-2)$차 다항식 $f$에 대응되는 $(p-1)\times (p-1)$ 순환 행렬 $M$에 대해 $M^p$가 $\{f(x){\}}^p$에 대응된다. 페르마 소정리에 따라 $f(x)\equiv \{f(x){\}}^p(\text{mod }p)$이므로 $\{f(x){\}}^p$에 대응되는 $M^p$는 $f(x)$에 대응되는 $M$과 동일하여, $M\equiv M^p(\text{mod }p)$임을 알 수 있다.

 

4. Extension (Euler's Theroem of Circulant Matrix)

$\mathbb{Z}/n\mathbb{Z}$에서 위와 같은 과정을 진행할 수 있는지 확인해보자. 핵심 아이디어는 $\mathbb{Z}/p\mathbb{Z}$상에서 근을 갖지 않는 모든 다항식은 $p-2$차 이하로 나타나며, 다항식 곱셈을 행렬의 곱셈으로 표현할 수 있다는 것이었다. 마찬가지로 $\mathbb{Z}/n\mathbb{Z}$ 상에서 근을 갖지 않는 임의의 다항식은 오일러 소정리에 의해 $(\varphi (n)-1)$차 이하의 다항식으로 표현된다. 행렬과의 대응관계 역시 똑같이 정의할 수 있으므로, 다음과 같은 관계가 $\mathbb{Z}/n\mathbb{Z}$ 상에서 정의되며 근을 갖지 않는 $(\varphi (n)-1)$차 다항식에 대응되는 $\varphi (n)\times \varphi (n)$순환행렬 $M$에 대하여 $M\equiv M^{\varphi (n)}(\text{mod }n)$가 성립한다.