수학생 Juicy

(중국인의 나머지 정리) $n_{1},~n_{2},~\cdots ,~n_{r}$을 $i\neq j$에 대해 $gcd(n_{i},~n_{j})=1$인 양의 정수라 하자. 그러면 연립 선형 합동식 $$\left\{\begin{matrix} x\equiv a_{1} & (mod~n_{1}) \\ x\equiv a_{2} & (mod~n_{2}) \\ & \vdots \\ x\equiv a_{r} & (mod~n_{r}) \\ \end{matrix}\right.$$ 은 법 $n_{1}n_{2}\cdots n_{r}$에 대해 유일한 공통 해를 가진다. 1. $N=\prod_{i=1}^{r}n_{i}$에 대하여 $N_{i}=\frac{N}{n_{i}}$라 한다. 2. $N_{i}x_{i}\equiv 1~(mod~n..

Thm. $n$은 양의 정수, $p$는 소수이면 $n!$을 나누는 가장 큰 $p$의 거듭제곱의 지수는 $\sum_{k=1 }^{\infty }\left [ \frac{n}{p^{k}} \right ]$이다. 여기서 $p^{k}>n$이면 $\left [ \frac{n}{p^{k}} \right ]=0$이므로 급수는 유한하다. 따라서 $n!=\prod_{1\leq p\leq n}^{}p^{\sum_{k=1}^{\infty }\left [ \frac{n}{p^{k}} \right ]}$ Thm. 양의 정수 $n$과 소수 $p$에 대하여 $$\left [ \frac{n}{p^{k+1}} \right ]=\left [ \frac{\left [ \frac{n}{p^{k}} \right ]}{p} \right ]$$..

양의 정수 $n$에 대해 $n=p_{1}^{k_{1}}p_{2}^{k_{2}}\cdots p_{r}^{k_{r}}$이 $n$의 소인수분해이면 다음이 성립한다. (1) 약수의 개수 $=(k_{1}+1)(k_{2}+1)\cdots (k_{r}+1)$ (2) 약수들의 합 $=\frac{p_{1}^{k_{1}+1}-1}{p_{1}-1}\frac{p_{2}^{k_{2}+1}-1}{p_{2}-1}\cdots \frac{p_{r}^{k_{r}+1}-1}{p_{r}-1}$

큰 숫자를 소수인지 아닌지 판단해보고 싶은적이 한번씩은 있을 것이다. 처음부터 일일히 세어 나갈 수도 없는 노릇이고 일일히 하나씩 나누어 보기에도 너무 힘들다. 그렇다면 큰 숫자가 소수인지 아닌지 어떻게 판단할 수 있을까? Thm. 정수 $a>1$가 합성수이면 $p\leq \sqrt{a}$인 소인수 $p$가 존재한다. 즉, 정수 $a>1$가 $p\leq \sqrt{a}$인 모든 소수로 나누어지지 않으면 $a$는 소수이다. 2022를 소인수 분해 해보자. 1. 2022는 2로 나누어진다. => $2022=2\times 1011$ 2. 1011의 각자리 숫자를 더하면 3이 되므로 1011은 3으로 나누어진다. => $2022=2\times 1011=2\times 3\times 337$ 3. 337은 2로도 ..

Def. (나눗셈 알고리즘) 주어진 정수 $a,~b(b>0)$에 대하여 다음을 만족하는 유일한 정수 $q,~r$이 존재한다. $$a=bq+r,~0\leq r

나눗셈 정리 (Division Algorithm) $ a $가 양의 정수이고, $ b $가 임의의 정수이며, 다음 식을 만족하는 정수 $ q $와 $r$은 유일하게 존재한다. $$ b=qa+r , ~~~~0\leq rb$가 성립한다. 아르키메데스의 원리를 알았으니, 나눗셈 정리를 증명해보자. pf) $b\geq 0$이면 아르키메데스의 원리에 의하여 $na>b$를 만족하는 양의 정수 $n$이 존재한다. (예를들어, $n=b+1$) 이제, $q+1$을 $na>b$를..