728x90

(중국인의 나머지 정리)

$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)$을 갖는다.

728x90
728x90

728x90
728x90

728x90
728x90

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$

728x90
728x90

양의 정수 $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}$

728x90
728x90

큰 숫자를 소수인지 아닌지 판단해보고 싶은적이 한번씩은 있을 것이다.

 

처음부터 일일히 세어 나갈 수도 없는 노릇이고 일일히 하나씩 나누어 보기에도 너무 힘들다.

 

그렇다면 큰 숫자가 소수인지 아닌지 어떻게 판단할 수 있을까?

 


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 $로 소인수분해 된다.

728x90
728x90

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})$$

728x90
728x90

Def.

$n\times n$ 행렬 $A$에 대하여

$$A\textbf{x}=\lambda \textbf{x}$$

를 만족하는 $\textbf{x}(\neq \textbf{0})\in \mathbb{R}^{n}$와 스칼라 $\lambda $가 존재하면, $\lambda $를 $A$의 고윳값(eigenvalue)이라 하고 $\textbf{x}$를 $\lambda $에 대응하는 $A$의 고유벡터(eigenvector)라 한다.

** $p(\lambda )=det(\lambda I-A)$를 $A$의 특성 다항식(고유 다항식, characteristic polynomial)이라 한다.

 

ex1.

행렬 $A=\begin{pmatrix}
-1 & 2 & 0 \\
7 & 4 & 0 \\
0 & 0 & 3 \\
\end{pmatrix}$에 대한 보기의 진위를 판정하고 이유를 설명하시오. [2010학년도 기출]

<보기>

(1) $A$의 고유다항식(characteristic polynomial)은 $x^{3}-6x^{2}-9x+54$이다.
(2) $A^{2}$의 모든 고윳값(eigenvalue, characteristic value)들의 합은 $36$이다.

 

sol1.

더보기

 

 

 

Def.

$\lambda $가 $A$의 고윳값일 때, $\lambda I-A$의 해공간을 $\lambda $에 대응하는 $A$의 고유공간(eigenspace)이라 한다.

** $k$가 양의 정수이고 $\lambda $가 행렬 $A$의 고윳값이며 $\textbf{x}$가 대응고유벡터이면, $\lambda^{k} $는 $A^{k}$의 고윳값이고 $\textbf{x}$는 \lambda ^{k}에 대응하는 $A^{k}$의 고유벡터이다.

 

ex2.

다음 행렬의 고유치(eigen value)와 고유공간(eigen space)을 구하시오. [2004학년도 기출]

$$\begin{bmatrix}
1 & 1 & -1 \\
0 & 2 & 0 \\
0 & 0 & 2 \\
\end{bmatrix}$$

 

sol2.

더보기

 

 

 

ex3.

$3\times 3$행렬 $A=\begin{bmatrix}
1 & 0 & 1 \\
0 & 2 & 0 \\
0 & 0 & 3 \\
\end{bmatrix}$에 대하여, $A^{10}$의 고윳값(eigen values)과 고유벡터(eigenvector)를 모두 구하시오. [2000학년도 기출]

 

sol3.

더보기

 

 

 

Def.

정사각행렬 $A$에 대하여 $P^{-1}AP$가 대각행렬도 되는 가역행렬 $P$가 존재하면 $A$를 대각화 가능하다(diagonalizable)고 한다. 그리고 행렬 $P$는 $A$를 대각화한다(diagonalize)고 한다.

** $\lambda_{0} $를 $n\times n$ 행렬 $A$의 고윳값이라 하자.

(1) 기하학적 중복도(geometric multiplicity) : $\lambda_{0} $에 대응하는 고유공간의 차원

(2) 대수적 중복도(algebraic multiplicity) : $A$의 특성다항식에서 $\lambda-\lambda _{0}$의 차수

** $A$가 대각화가능하기 위한 필요충분조건은 모든 고윳값에 대해서 기하학적 중복도가 대수적 중복도와 같은 것이다.

 

 

**$n$개의 일차독립인 고유벡터를 갖는 $n\times n$ 행렬 $A$를 대각화하는 방법

1. $A$의 고윳값 $\lambda_{1},~\lambda _{2},~\cdots ,~\lambda _{n} $과 $n$개의 일차독립인 고유벡터 $\textbf{x}_{1},~\textbf{x}_{2},~\cdots ,~\textbf{x}_{n}$을 구한다.

2. 행렬 $P=\left [ \textbf{x}_{1}~\textbf{x}_{2}~\cdots ~\textbf{x}_{n} \right ]$을 구성한다.

3. $P^{-1}AP$는 대각성분이 차례대로 $\lambda_{1},~\lambda _{2},~\cdots ,~\lambda _{n}$인 대각행렬이다.

 

ex4.

3차 정사각행렬 $A=\left ( a_{ij} \right )$가

$$A\begin{bmatrix}
1 \\
1 \\
2\end{bmatrix}=\begin{bmatrix}
4 \\
4 \\
8\end{bmatrix},~A\begin{bmatrix}
-1 \\
 0\\
1\end{bmatrix}=\begin{bmatrix}
2 \\
0 \\
-2\end{bmatrix},~A\begin{bmatrix}
1 \\
1 \\
0\end{bmatrix}=\begin{bmatrix}
-2 \\
-2 \\
0\end{bmatrix}$$

을 만족할 때, $A$의 고윳값(eigenvalue)을 모두 쓰시오. 또한, $a_{11}+a_{12}+a_{13}$의 값을 풀이 과정과 함께 쓰시오. [2022학년도 기출]

 

sol4.

더보기

 

 

 

ex5.

행렬 $A=\begin{bmatrix}
3 & 2 & 2 \\
0 & 3 & 1 \\
0 & -2 & 0 \\
\end{bmatrix}$에 대하여 $A=PDP^{-1}$을 만족하는 행렬 $D=\begin{bmatrix}
d_{1} & 0 & 0 \\
0 & d_{2} & 0 \\
0 & 0 & d_{3} \\
\end{bmatrix}$와 가역행렬 $P$를 풀이 과정과 함께 쓰시오. 또한 행렬 $A^{n}$의 2행 3열의 성분을 구하시오. (단, $d_{1}\leq d_{2}\leq d_{3}$이고 $n$은 자연수이다.) [2021학년도 기출]

 

sol.

더보기

 

 

 

Thm.

$n\times n$ 행렬 $A$의 고유 다항식에 대한 복소 해가 $\lambda _{1},~\lambda _{2},~\cdots ,~\lambda _{n}$라 하면 다음이 성립한다.

(1) $det(A)=\lambda _{1}\lambda _{2}\cdots \lambda _{n}$

(2) $tr(A)=\lambda _{1}+\lambda _{2}+~\cdots ~+\lambda _{n}$

728x90

'[전공수학] 이론 > 선형대수' 카테고리의 다른 글

동형사상(isomorphism)  (0) 2022.12.23
동치명제  (0) 2022.12.23
선형변환의 행렬 표현  (0) 2022.12.23
선형변환(선형사상, linear transformation)  (0) 2022.12.22
정사영(orthogonal projection)  (0) 2022.12.22

+ Recent posts