문제 링크 홀수 소수 ppp에 대해, 1,2,⋯⌊p⌋+11,2, \cdots \lfloor \sqrt{p} \rfloor + 11,2,⋯⌊p​⌋+1의 수 중 ppp에 대한 이차비잉여가 반드시 존재함을 보여라. This section is intentionally left blank to protect you from spoiler. 가장 작은 이차비잉여를 b≤p−1b \le p-1b≤p−1라고 하고, 귀류법으로 b≥⌊p⌋+2b \ge \lfloor \sqrt{p} \rfloor + 2b≥⌊p​⌋+2라고 하자. 그렇다면 b ∣ p+rb \ | \ p+rb ∣ p+r을 만족하는 정수 0≤r≤b−10 \le r \le b-10≤r≤b−1이 존재한다. 이 때 p+r=abp + r = abp+r=ab라고 놓으면, a≥⌊p⌋+2a \ge\lfloor \sqrt{p} \rfloor + 2a≥⌊p​⌋+2일 경우 \(p = ab-r > ab..

객지 시험 공부하기 싫어서 또다시 블로그로 도망쳤다. 정수론 시험 범위랑도 겹치는 내용이어서 풀어볼 법도 했는데, 풀이를 '보임' 당해버렸다... 왜 AOPS는 백준처럼 게시물 index가 없는 걸까. AOPS 102910번 이런 식으로 링크 걸어놓으면 되게 포스팅하기 편할 것 같은데... 문제 링크 : 스포일러 주의! statement :소수 ppp에 대해 p≡−1(mod 4)p \equiv -1 (\text{mod} \ 4)p≡−1(mod 4)일 때, ∏j=1p−1(j2+1)≡4(mod p)\prod_{j=1}^{p-1} (j^2 + 1) \equiv 4(\text{mod} \ p)∏j=1p−1​(j2+1)≡4(mod p)임을 보여라. (cf : p≡1(mod 4)p \equiv 1 (\text{mod} \ 4)p≡1(mod 4)라면?)임의의 jjj에 대해, j2+1j^2 + 1j2+1은 Fp\mathbb{F}_pFp​ 상에서 다항식..