Extension of FLT to Matrix base / 페르마 소정리의 행렬로의 확장
1. 다항식의 곱셈과 행렬
다항식은 수 사이의 관계를 표현하며, 다항식의 계수만을 적어 다항식을 벡터로 표현할 수 있습니다. 다항식을 곱하면 새로운 다항식으로 전이되며 벡터에 행렬을 곱하면 새로운 벡터로 전이된다는 사실을 생각해보면 다항식의 곱셈을 행렬로 표현하는 것이 새로운 관찰을 제공할 수 있을 듯 합니다.
우선 다음과 같이 다항식 f와 벡터 v를 대응시켜봅시다.
f(x)=anxn+an−1xn−1+⋯+a0v=[a0a1⋮an]다항식 사이의 곱셈에서 xc의 계수는 a+b=c를 만족하는 음이 아닌 정수 a,b에 대해 두 다항식에서 a차항, b차항의 계수를 곱한 후 모두 더한 값이 됩니다. 따라서 ‘다항식 f를 곱한다‘는 연산에 해당하는 행렬은 다음과 같이 대각선 방향으로 동일한 값이 위치하게 됩니다. n차 다항식은 (n+1)×1꼴의 벡터로 표현되므로 이러한 행렬의 꼴은 (2n+1)×(n+1)이 된다는 사실도 알 수 있습니다.
[a00⋯0a1a0⋯0a2a1⋯0⋮⋮⋮00⋯an]2. Z/nZ에서의 다항식 곱셈
다음 식은 페르마 소정리입니다. 이는 소수 p에 대해 k의 값에 무관하게 항상 성립하는 등식입니다.
k≡kp (mod p)또한 k가 0이 아니라면, 다음이 성립합니다.
kp−1≡1 (mod p)따라서 1 이상 p 미만의 정수 집합을 정의역으로 갖는 다항식 f는 법 p에서 항상 p−2차 이하임을 알 수 있습니다. 여기서 1.을 다시 떠올려 본다면, 법 p에서의 다항식과 그 곱셈은 항상 일정한 크기의 벡터와 행렬로 표현할 수 있겠다는 생각을 할 수 있습니다. 다음은 페르마 소정리를 이용해 정리한, 법 p에서 ‘다항식 f를 곱한다‘에 해당하는 행렬입니다.
[a0an⋯a1a1a0⋯a2a2a1⋯a3⋮⋮⋮anan−1⋯a0]그럼 다항식 g(x)=1에 여러 다항식 a(x),b(x)를 곱하는 상황을 생각해봅시다. 두 다항식을 곱하는 연산에 대응되는 행렬이 각각 A,B라면 다음과 같은 식으로 표현할 수 있습니다.
a(x)b(x)g(x)⇔AB[10⋮0]b(x)⇔B[10⋮0]위 수식의 두번째 줄을 보면, 결국 a(x)b(x)g(x)가 a(x)b(x)와 같다는, 우리가 이미 잘 알던 대수적 지식을 이끌어 낼 수 있음을 확인하였습니다. 잠깐, 어차피 g(x)=1을 곱하여 다항식에 해당하는 벡터를 얻을 수 있다면, 이 행렬은 ‘다항식을 곱하는 연산‘이 아니라 ‘다항식’ 그 자체로 보아도 괜찮지 않을까요? 다시 말해, 다음과 같이 대응시켜도 된다는 이야기입니다.
anxn+an−1xn−1+⋯+a0⇔[a0an⋯a1a1a0⋯a2a2a1⋯a3⋮⋮⋮anan−1⋯a0]3. Screw Matrix에 대한 페르마 소정리
그렇다면 위와 같은 대응관계에서 우리가 얻을 수 있는 것은 무엇인지 생각해봅시다. 위의 대응관계는 다항식을 행렬로 변환하는 방법을 묘사하지만, 동시에 특수한 꼴의 행렬을 다항식으로 변환하는 방법을 묘사합니다. 행렬보다는 다항식이 분석하기 용이한 면이 여럿 있기 때문에 이러한 변환은 몇 가지 사실을 알려줄 수 있을 듯 합니다. 예를 들면, 행렬에서의 페르마 소정리죠.
우선은 2.에서 발견한 대응관계를 통해 다항식으로 변환할 수 있는 특수한 행렬을 Screw Matrix라고 정의합시다. (같은 수들이 나열되어 있는 꼴이 왠지 나사 같아 보이지 않나요?) 조금 더 엄밀하게 정의하자면, Screw Matrix는 다음과 같은 명제를 만족하는 행렬 M입니다.
∀i,j,k∈{0,1,⋯,p−2}Aij=Axy where x=(i+k) mod (p−2),y=(j+k) mod (p−2)법 p에서 x≠0일 때 다항식 f(x)의 p제곱은 f(x)와 합동이므로 임의의 Screw Matrix에 대응하는 다항식으로부터 다음과 같이 Screw Matrix M에 대한 페르마 소정리가 성립함을 알 수 있습니다.
M≡Mp (mod p)