수학생 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_{i})$가 되는 $x_{i}$를 찾는다.

3. $\sum_{i=1}^{r}a_{i}N_{i}x_{i}$은 주어진 연립선형합동식의 법 $n_{1}n_{2}\cdots n_{r}$에 대하여 유일한 공통해이다.

ex) 다음 연립 선형 합동식의 해를 구하시오.

$$\left\{\begin{matrix}
x\equiv 2 & (mod~3) \\
x\equiv 3 & (mod~5) \\
x\equiv 2 & (mod~7) \\
\end{matrix}\right.$$

sol)

$$\left\{\begin{matrix}
x\equiv 2 & (mod~3) & N_{1}=35 & x_{1}=2 \\
x\equiv 3 & (mod~5) & N_{2}=21 & x_{2}=1 \\
x\equiv 2 & (mod~7) & N_{3}=15 & x_{3}=1 \\
\end{matrix}\right.$$

그러므로 법 $3\cdot 5\cdot 7=105$에 대해 유일한 공통 해 $x=2\cdot 35\cdot 2+3\cdot 21\cdot 1+2\cdot 15\cdot 1\equiv 23~(mod~105)$을 갖는다.

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 ]$$\

이 성립한다.

말은 어려워 보이지만 실제로 문제를 풀어보면 그렇게 어렵지 않다.

ex) $500!$을 나누는 $7$의 가장 큰 거듭제곱의 지수를 구하시오.

sol) $\left [ \frac{500}{7} \right ]+\left [ \frac{500}{7^{2}} \right ]+\left [ \frac{500}{7^{3}} \right ]+\left [ \frac{500}{7^{4}} \right ]+~\cdots ~=\left [ \frac{500}{7} \right ]+\left [ \frac{\left [ \frac{500}{7} \right ]}{7} \right ]+~\cdots ~=71+\left [ \frac{71}{7} \right ]+~\cdots ~=71+10+1+0+\cdots =82$

양의 정수 $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로도 3으로도 5로도 7으로도 나누어지지 않는 것 같다! 그렇다면 337은 소수일까?

4. $\sqrt{337}$의 대략적인 크기를 구해보자. $18^{2}=324,~19^{2}=361$이므로 $\sqrt{337}=18.\textbf{XX}$이다.

5. 즉, 위 정리에 의해 18보다 작거나 같은 소수(2, 3, 5, 7, 11, 13, 17)로 나누어지지 않으면 337은 소수가 된다. 

6. 그러므로 337은 소수이다.

$\therefore2022=2\times 3\times 337 $로 소인수분해 된다.

Def. (나눗셈 알고리즘)

주어진 정수 $a,~b(b>0)$에 대하여 다음을 만족하는 유일한 정수 $q,~r$이 존재한다.

$$a=bq+r,~0\leq r<b$$

$a$를 $b$로 나누는 연산에서 $q$를 몫(quotient), $r$은 나머지(remainder)라 부른다.

Def. (약수와 배수)

정수 $a,~b$에 대하여

(1) $a\neq 0$

(2) $b=ac$인 정수 $c$가 존재한다.

을 만족할 때, $b$는 $a$로 나누어진다고 표현하고 $a~|~b$로 쓴다.

**이때 $a$는 $b$의 약수 $b$는 $a$의 배수가 된다. 

**$a$와 $b$는 음수가 될 수도 있다 (정수)

Def. (최대공약수)

$a,~b$를 적어도 둘 중 하나는 0이 아닌 정수라 하자. $a,~b$의 최대공약수(greatest common divisor)는 $gcd(a,~b)$로 쓰고 다음을 만족하는 양의 정수 $d$이다.

(1) $d~|~a,~d~|~b$

(2) $c~|~a$ 이고, $c~|~b$ 이면 $c\leq d$

Def. (서로소)

정수 $a,~b$에 대해 $gcd(a,~b)=1$인 경우 서로소(relatively prime)라 한다.

Thm1.

$a~|~c,~b~|~c$ 그리고 $gcd(a,~b)=1$이면 $ab~|~c$이다.

Thm2.

적어도 하나는 0이 아닌 주어진 정수 $a,~b$에 대해

$$gcd(a,~b)=ax+by$$

를 만족하는 $x,~y$가 존재한다.

** 디오판투스 방정식 $ax+by=c$

선형 디오판투스 방정식 $ax+by=c$가 해를 가지는 것은 $d=gcd(a,~b)$일 때 $d~|~c$임과 동치이다.

특수해 $x_{0},~y_{0}$에 대하여 일반해는 다음과 같다.

$$x=x_{0}+\left ( \frac{b}{d} \right )t,~y=y_{0}-\left ( \frac{a}{d} \right )t~~(t\in \mathbb{Z})$$

나눗셈 정리 (Division Algorithm)

$ a $가 양의 정수이고, $ b $가 임의의 정수이며, 다음 식을 만족하는 정수 $ q $와 $r$은 유일하게 존재한다.

$$ b=qa+r  ,  ~~~~0\leq r< a $$

나눗셈 정리를 증명하기 전에 알아야할 기본적인 원리가 존재하는데, 정수론에서 자주 이용되는 아르키메데스의 원리이다.

아르키메데스의 원리를 알았으니, 나눗셈 정리를 증명해보자.

pf) $b\geq 0$이면 아르키메데스의 원리에 의하여 $na>b$를 만족하는 양의 정수 $n$이 존재한다. (예를들어, $n=b+1$) 이제, $q+1$을 $na>b$를 만족하는 최소의 양의정수 $n$이라 하면,

$$(q+1)a>b\geq qa$$

가 성립하고, $r=b-qa$로 잡으면, $b\geq qa$에서 $r=b-qa\geq 0$, 또한 $(q+1)a=qa+a>b$에서 $r=b-qa<a$이다. $b<0$인 경우도 같은 방법으로 보일 수 있다. $q$, $r$의 유일성을 증명하기 위하여

$$b=qa+r=q_{1}a+r_{1}, ~~~~0\leq r, r_{1}<a$$

라 가정하면, $r\leq r_{1}$ 또는 $r_{1}\leq r$이므로 편의상 $r_{1}\leq r$이라 하면

$$0\leq r-r_{1}<a$$

이다. $(q_{1}-q)a=r-r_{1}$이므로 $a\mid r-r_{1}$이고 $r-r_{1}>0$이면 $a\leq r-r_{1}$이 되어 $0\leq r-r_{1}<a$ 에 모순이다. 따라서 $ r-r_{1}=0 $, 즉 $r=r_{1}$이 되며, 또 $(q-q_{1})a=0$에서 $q=q_{1}$을 얻는다.