문제 링크 홀수 소수 \(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..

객지 시험 공부하기 싫어서 또다시 블로그로 도망쳤다. 정수론 시험 범위랑도 겹치는 내용이어서 풀어볼 법도 했는데, 풀이를 '보임' 당해버렸다... 왜 AOPS는 백준처럼 게시물 index가 없는 걸까. 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\) 상에서 다항식..