AOPS 문제 퍼온 풀이 #001

객지 시험 공부하기 싫어서 또다시 블로그로 도망쳤다. 정수론 시험 범위랑도 겹치는 내용이어서 풀어볼 법도 했는데, 풀이를 '보임' 당해버렸다...

왜 AOPS는 백준처럼 게시물 index가 없는 걸까. ^[각주:1] AOPS 102910번 이런 식으로 링크 걸어놓으면 되게 포스팅하기 편할 것 같은데...

문제 링크 : 스포일러 주의!

statement :

소수 $p$에 대해 $p \equiv -1 (\text{mod} \ 4)$일 때, $\prod_{j=1}^{p-1} (j^2 + 1) \equiv 4(\text{mod} \ p)$임을 보여라.

(cf : \(p \equiv 1 (\text{mod} \ 4)\)라면?)

---

임의의 $j$에 대해, $j^2 + 1$은 $\mathbb{F}_p$ 상에서 다항식 $P(x) = (x-1)^{(p-1)/2}-1 = 0$의 distinct한 근이 된다.

$P(x)$는 $\frac{p-1}{2}$차 다항식이고, 근과 계수와의 관계에 의해 근의 곱은 $2$가 된다.

문제에 주어진 식은 근들의 곱을 제곱한 것이고, 당연히 $4$가 된다. $\blacksquare$

$(\frac{-1}{p})$이기 때문에 $\mathbb{F}_p$상에는 $-1$의 제곱근이 존재하지 않는다. 

따라서 $-1$의 제곱근 $\alpha$를 이용하여 $\mathbb{F}_p$를 확장한 체 $\mathbb{K} = \mathbb{F}_p[\alpha]$를 잡자.

$Q(x) = x^{p-1}-1$를 잡으면,

 $Q(x)$는 $1$부터 $p-1$까지를 근으로 가지므로 $Q(x) = (x-1)(x-2) \cdots (x-(p-1))$로 쓸 수 있다.

이 때 주어진 식은

$\prod_{j=1}^{p-1} (j^2 + 1) = \prod_{j=1}^{p-1} (\alpha - j)(-\alpha-j) = Q(\alpha)Q(-\alpha) = ((-1)^{(p-1)/2}-1)^2 = 4 \blacksquare$

하지만 아직은 확장체 같은 걸 풀이에 자유자재로 쓸 자신이 없다...

1. 있긴 한데, "c6h1561242" 처럼 되게 멋없는 string이다. [본문으로]