AOPS 퍼온 풀이 #002

문제 링크

홀수 소수 \(p\)에 대해, \(1,2, \cdots \lfloor \sqrt{p} \rfloor + 1\)의 수 중 \(p\)에 대한 이차비잉여가 반드시 존재함을 보여라.

---

This section is intentionally left blank to protect you from spoiler.

---

가장 작은 이차비잉여를 \(b \le p-1\)라고 하고, 귀류법으로 \(b \ge \lfloor \sqrt{p} \rfloor + 2\)라고 하자.

그렇다면 \(b \ | \ p+r\)을 만족하는 정수 \(0 \le r \le b-1\)이 존재한다. 이 때 \(p + r = ab\)라고 놓으면, \(a \ge\lfloor \sqrt{p} \rfloor + 2\)일 경우 \(p = ab-r > ab-b = b(a-1) > p\)이므로 모순이다. 따라서 \(a \le \lfloor \sqrt{p} \rfloor + 1\)이고, 가정에 따라 \((\frac{a}{p}) = 1\)이다.

이 때 \(1 = (\frac{r}{p}) = (\frac{p+r}{p}) = (\frac{ab}{p}) = (\frac{a}{p})(\frac{b}{p}) = -1\)이므로 모순. 따라서 \(b \le \lfloor \sqrt{p} \rfloor + 1\)이 성립해야 한다. \(\blacksquare\)