정답
\(x^6+1\equiv0\pmod{157}\) 의 해가 되는 \(A\) 의 원소의 개수는 \(4\)개이고, 주어진 합의 값은 \(-2\)이다.
출제 의도
소수 위의 곱셈군에서 원시근과 지수 비교를 이용해 합동식의 해를 구하게 하고, 르장드르 기호의 성질(특히 곱셈성, 제곱의 값, 전체 비제로 원소에 대한 합이 \(0\)이 됨)을 이용하여 복잡해 보이는 합을 간단한 합으로 변형해 계산하는 능력을 평가한다.
풀이 과정
먼저 집합 \(A=\{5^i\mid i\le100,\ i\in\mathbb{Z}_{>0}\}\subset(\mathbb{Z}/157\mathbb{Z})^\times\) 에서 합동식
$$ x^6+1\equiv0\pmod{157} $$
을 만족하는 원소의 개수를 구한다. 소수 \(157\) 에 대해 \(5\)는 원시근이므로 \((\mathbb{Z}/157\mathbb{Z})^\times=\langle5\rangle\) 이고 위 군의 차수는 \(156\)이다.
어떤 해 \(x\) 는 반드시 \(x\equiv5^k\) (어떤 정수 \(k\))의 꼴이다. 또한 \(-1\) 은 홀수 소수에서 항상 \(g^{(p-1)/2}\) 의 꼴이므로 여기서는
$$ -1\equiv5^{\frac{157-1}{2}}=5^{78}\pmod{157} $$
이다. 따라서
$$ x^6\equiv-1\iff 5^{6k}\equiv5^{78}\pmod{157}. $$
위 곱셈군의 차수가 \(156\) 이므로 지수를 비교하여
$$ 6k\equiv78\pmod{156} $$
을 얻는다. \(\gcd(6,156)=6\) 이므로 양변을 \(6\)으로 나누면
$$ k\equiv13\pmod{26} $$
이다. 이제 \(1\le k\le100\) 이라는 조건을 고려하면
$$ k=13,39,65,91 $$
의 네 값만 가능하다. 각각에 대해 \(x=5^k\in A\) 이므로, \(A\) 안에서의 해의 개수는
$$ 4 $$
개이다.
다음으로 르장드르 기호를 이용해 다음 합
$$ \sum_{i=1}^{155} \left\{ \left(\frac{5^i}{157}\right) \left(\frac{i^3}{157}\right) \left(\frac{157-i}{157}\right) + \left(\frac{5^i-1}{157}\right) \right\} $$
의 값을 구한다. 먼저 첫 번째 항을 르장드르 기호의 곱셈성을 이용해 단순화한다. 소수 \(p\equiv1\pmod4\) 이면 \(\left(\frac{-1}{p}\right)=1\) 이므로 \(157\equiv1\pmod4\) 에서
$$ \left(\frac{157-i}{157}\right) = \left(\frac{-i}{157}\right) = \left(\frac{-1}{157}\right)\left(\frac{i}{157}\right) = \left(\frac{i}{157}\right) $$
이다. 따라서
$$ \left(\frac{i^3}{157}\right)\left(\frac{157-i}{157}\right) = \left(\frac{i^3}{157}\right)\left(\frac{i}{157}\right) = \left(\frac{i^4}{157}\right). $$
\(i\) 가 \(1\le i\le155\) 이므로 \(157\) 으로 나눈 나머지가 \(0\) 이 아니고, 어떤 비제로 원소의 제곱의 르장드르 기호는 항상 \(1\) 이다. 따라서
$$ \left(\frac{i^4}{157}\right)=1 $$
이고, 전체 첫 항은
$$ \left(\frac{5^i}{157}\right)\left(\frac{i^4}{157}\right) = \left(\frac{5^i}{157}\right) $$
으로 정리된다. 결국 주어진 합은
$$ S= \sum_{i=1}^{155} \left[ \left(\frac{5^i}{157}\right) + \left(\frac{5^i-1}{157}\right) \right] = S_1+S_2 $$
로 나눌 수 있다.
먼저
$$ S_1=\sum_{i=1}^{155}\left(\frac{5^i}{157}\right) $$
을 구한다. \(5\)가 원시근이므로 \(5^1,5^2,\dots,5^{156}\) 은 \(157\)에서의 모든 비제로 나머지 \(\{1,2,\dots,156\}\) 와 일대일 대응한다. 르장드르 기호를 모든 비제로 원소에 대해 더하면
$$ \sum_{a=1}^{156}\left(\frac{a}{157}\right)=0 $$
이므로
$$ \sum_{i=1}^{156}\left(\frac{5^i}{157}\right)=0. $$
따라서
$$ S_1 = -\left(\frac{5^{156}}{157}\right). $$
그러나 \(5^{156}\equiv1\pmod{157}\) 이고 \(\left(\frac{1}{157}\right)=1\) 이므로
$$ S_1 = -1. $$
다음으로
$$ S_2=\sum_{i=1}^{155}\left(\frac{5^i-1}{157}\right) $$
을 계산한다. 앞에서 본 것처럼 \(i=1,\dots,155\) 에 대해 \(5^i\) 는 모든 비제로 원소 중 \(1\) 을 제외한 \(155\)개의 원소를 한 번씩 나타낸다. 즉 집합
$$ R=\{5^i\mid1\le i\le155\} $$
는 \(\{2,3,\dots,156\}\) 와 같다.
함수 \(a\mapsto a-1\) 은 \(\mathbb{Z}/157\mathbb{Z}\) 에서 전단사이므로 \(\{a-1\mid a\in R\}\) 는 \(\{2-1,3-1,\dots,156-1\}=\{1,2,\dots,155\}\) 와 같다. 즉
$$ \{5^i-1\mid1\le i\le155\} = \{1,2,\dots,155\} $$
이 어떤 순서로 나타난 것에 불과하다. 르장드르 기호의 합은 순서에 영향을 받지 않으므로
$$ S_2 = \sum_{a=1}^{155}\left(\frac{a}{157}\right). $$
다시 전체 합이 \(0\) 이라는 사실을 사용하면
$$ \sum_{a=1}^{155}\left(\frac{a}{157}\right) = -\left(\frac{156}{157}\right). $$
여기서 \(156\equiv-1\pmod{157}\) 이고 \(157\equiv1\pmod4\) 이므로 \(\left(\frac{-1}{157}\right)=1\) 이다. 따라서
$$ \left(\frac{156}{157}\right)=\left(\frac{-1}{157}\right)=1, \qquad S_2=-1. $$
이제
$$ S=S_1+S_2 = (-1)+(-1)=-2 $$
임을 얻는다.
정리하면,
- \(x^6+1\equiv0\pmod{157}\) 의 해가 되는 \(A\) 의 원소의 개수는 \(4\)개,
- 주어진 르장드르 기호의 합의 값은 \(-2\)
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>