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$