p가 소수일 때\[ f(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0 \equiv 0 \pmod{p} \]는 최대 n개의 incongruent solution을 가진다. \( ( a_n \not \equiv 0 \pmod{p} ) \) n에 관한 귀납적 접근을 시도한다.n=1일 때 \(f(x) = a_1 x+a_0 \equiv 0 \pmod{p} \), 즉 \(a_1 x \equiv -a_0 \pmod{p} \) 이라는 일차식이 나오는데, a_1과 p의 최대공약수가 1이므로 해가 최대 한 개 존재한다.n=k-1일 때 \(f(x) \equiv 0 \pmod{p} \)의 해가 최대 k-1개 존재한다고 가정하자.n=k일 때\[f(x) \equiv 0 \pmod{p} \]이 ..
Theorem. 주어진 \(a,b\in \mathbb{Z}\)에 대하여 a,b가 둘 다 0이 되지 않을 때,\[ \exists x,y \in \mathbb{Z} \quad \mathrm{such \ that} \quad \gcd (a,b) = ax+ by \] \[ S = \{ au +bv | au+bv > 0 , \; u,v\in \mathbb{Z} \} \]존재성을 보이기 위해 WOP를 적용해야 할 것을 생각하면서 위 집합을 잡아줄 수 있다. 이 집합이 공집합이 아니라는 것은 다음과 같이 간단한 것을 생각해주면 알 수 있다.\[\mathrm{take} \; u = b , \quad v= -a + sgn (1) \]공집합이 아닌 자연수로 이루어진 집합이므로 Well Ordering Principle을 ..
\[ \phi (n) := \# \{ m \in \mathbb{N} | m \le n \; \text{and} \; (m,n)=1 \} \]Euler function은 n보다 작거나 같은 서로소의 개수에 대한 함수이다. Theorem 1.\[ \phi (n) = n \prod _{p|d} \left( 1 - \frac {1}{p} \right) \] 소인수분해를 한 후 포함과 배제의 원리를 적용하여 직접 함수값을 추론하면 된다.\[ \mathrm{for} \; n=1, \quad \phi(1) = 1, \quad \mathrm{True} \]\[ \mathrm{for} \; n>1, \; \mathrm{Let \ standard \ prime \ factorization \; } n= p_1 ^{a_1}..
산술함수 f에 대하여 f가 multiplicative하다는 것은 다음을 나타낸다.\[f(mn) = f(m) f(n), \quad \mathrm{whenever \ } (m,n)=1 \]모든 수에 대해 함수값이 0인 경우는 예외로 한다.completely multiplicative는 (m,n)=1이라는 조건을 무시해도 성립할 때를 말한다.이런 성질을 생각하면 좋은 이유는 산술의 기본정리에 의해 어떤 자연수에 대해 standard prime factorization이 유일하게 존재하는데, multiplicative를 이용하면 더 작은 단위의 곱으로 나타낼 수 있기 때문이다. 거기에 completely multiplicative면 그것보다도 더 작게 쪼개서 생각할 수 있다. theorem. f가 multipl..
\[ f(n) = a_k n^k + a_{k-1} n^{k-1} + \cdots + a_1 n + a_0 \qquad a_k , a_{k-1} , \cdots , a_0 \in \mathbb{Z} \]0 이상의 정수 \(n\)에 대해 \(f(n)\)이 소수인 함수는 존재하지 않는다. proof.0 이상의 정수 \(n\)에 대해 \(f(n)\)이 소수인 \(f\)가 존재한다고 하자.이때 \(f(n_0) \)가 소수 \(p\)가 되는 \(n_0\)를 하나 잡자.\[ \begin{align} f(n_0 + tp ) & = a_k (n_0 + tp)^k + a_{k-1} (n_0 + tp )^{k-1} + \cdots + a_1 (n_0 + tp) + a_0 \\ & = (a_k n_0 ^k + a_{k-1} ..
\[ \sum _{n=-\infty} ^\infty (-1)^n q^{n(3n-1)/2} = \sum _{n=-\infty} ^\infty (-1)^n q^{n(3n+1)/2} = (q;q)_\infty \]첫번째 식에 \(n\) 대신 \(-n\)을 넣었을 때 두번째 식이 되고, 결과적으로 의미가 있는 것은 세번째 식이라고 할 수 있겠다.Ramanujan's notation 중 하나를 생각한다. 이 글에서 음의 무한부터 양의 무한까지의 급수는 간단하게 \(\sum\)으로 나타낸다.left hand side ::\[ f(-q) = f(-q;-q^2 ) = \sum (-q)^{n(n+1)/2} (-q^2 )^{n(n-1)/2 } = \sum (-1)^n q^{n(3n-1)/2} \] right hand si..
\(|q|
q-binomial Theorem :: \(|q| , |z|
Gaussian Coefficient, q-Binomial Coefficient 1. 정의2. 조합3. 성질 3.1. first q-analogue of Pascal's formula 3.2. second q-analogue of Pascal's formula
q-series 1. 정의2. 예3. 팩토리얼 1. 정의\[ (a)_0 := (a;q)_0 := 1 , \quad (a)_n := (a,q)_n := \prod _{k=0} ^{n-1} (1-aq^k ), \qquad n \ge 1 \]\[ \qquad \qquad \qquad \qquad \qquad (a)_\infty := (a;q)_\infty := \prod _{k=0} ^{\infty} (1-aq^k ), \qquad |q|0 \)에 대해 \(q^a \)를 넣고, \(q\)가 1로 갈 때 로피탈의 정리를 쓰자.\[ \lim _{q \rightarrow 1 } \frac {(q^a)_n}{(1-q)^n}= \lim _{q \rightarrow 1 } \frac{1-q^a}{1-q} \frac{1-..