문제 링크 스포 방지를 위해 더보기 기능을 쓰니까 수식이 깨지는 문제가 있어서 그냥 밑으로 내리기로 했다. statement : \(\omega := \omega^p = 1\)의 한 허근$$ X := \sum_{\text{k : Quadratic Residue of mod }p}\omega^{k} $$ $$ Y := \sum_{\text{k : Quadratic Irresidue of mod }p}\omega^{k} $$ \(XY \in \mathbb{Z}\)임을 보여라. 이차잉여 개념을 이용해서 해결할 수 있는데, 수업 시간에 배우기도 했던 중요한 Lemma를 사용할 수 있다. 일단 \(X,Y\)가 굉장히 보기 싫으니까 이렇게 바꾸자. $$ X = \frac{1}{2}\sum_{k=1}^{p-1}(1+..

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

Vieta Jumping은 꽤 난도가 높아 보이는 수올 문제들에서 종종 보이는 테크닉이다. 아니 사실 나한테만 어렵지 현역 수올러들은 되게 잘 쓰는 것 같다. 주로 이변수 대칭 이차식의 정수해를 bound 시킬 때 쓰인다. 이렇게 말해봐야 이해하는 데 도움이 되지 않으니, 아래의 예시를 따라오면서 감을 잡는 것을 권장한다.Problem 1. (IMO '88 #6) 음 아닌 정수 \(a,b\)가 \(ab+1 | a^2+b^2\)를 만족할 때, \(k = \frac{a^2+b^2}{ab+1} \)은 완전제곱수임을 보여라. 우선 \(b = 0\)인 경우는 \(k = a^2\)이 되어 완전제곱수가 됨을 알 수 있다. fixed \(k\)에 대해 \(S := \{ (a,b) | a \ge b, \ \frac{a^..

시험기간인데 포스팅은 하고 싶어서 내뱉는 짧은 주제.이산수학이 맞는지는 모르겠지만... 이것과 연관된 이산수학 문제가 하나 있으니까 이 카테고리에 포스팅하기로 한다. 1. Definition of Beatty Sequence 양의 무리수 \(r\)에 대해서 Beatty Sequence \(\mathcal{B}_r\)을 다음과 같이 정의한다. $$ \mathcal{B}_r := \{ \lfloor r \rfloor, \lfloor 2r \rfloor, \cdots, \lfloor nr \rfloor \cdots \} $$ 2. Rayleigh's theorem 두 양수 무리수 \(r,s\)가 \(\frac{1}{r}+\frac{1}{s} = 1\)을 만족할 때, \(\mathcal{B}_r\)과 \(\ma..

https://www.codechef.com/LTIME54 1. Smart Strategy (SMRSTR) Tag : Implementation, Number Theory \(N\)개의 수 \(D_1 , \cdots , D_N \)이 있을 때, \(Q\)개의 정수 \(X_1 , \cdots , X_Q \)에 대해 다음 과정을 수행하는 프로그램 작성하여라. procedure f(X):for i = 1 .. N:X = floor ( X / D[i] )return X \(1 \le \text{TESTCASE} \le 1,000\)\(1 \le N \le 10^5, \ \sum N \le 3 \cdot 10^{5} \)\(1 \le Q \le 10^5, \ \sum Q \le 3 \cdot 10^{5} \)\(..

그리피스 전자기학을 읽다 보면 언쇼 정리(Earnshaw's theorem)이라는 걸 볼 수 있는데, statement는 다음과 같다. 점전하들로만 이루어진 계에는 안정 평형점이 존재하지 않는다. 증명은 가우스 법칙을 이용해서 간단하게 할 수 있다. 안정 평형점 \(\vec{x}\)가 존재한다고 해 보자. 그렇다면 \(\vec{x}\)는 다음의 두 성질을 만족시켜야 한다: (1) \(E(\vec{x}) = 0\)(2) 충분히 작은 \(\delta x\)에 대해, \(E(\vec{x}+\delta x)\)는 \(x\)를 향한다. 그렇다면 아주 작은 구면, (2)에서 언급된 \(\delta x\)만큼의 크기를 갖는 구면 \(\mathcal{S}\)를 가우스면으로 설정해 보자. 구면 \(\mathcal{S}\..