"최대공약수"의 두 판 사이의 차이
Pythagoras0 (토론 | 기여) |
Pythagoras0 (토론 | 기여) |
||
75번째 줄: | 75번째 줄: | ||
==사전형태의 자료== | ==사전형태의 자료== | ||
* http://en.wikipedia.org/wiki/Bézout's_identity | * http://en.wikipedia.org/wiki/Bézout's_identity | ||
+ | |||
+ | |||
+ | ==리뷰, 에세이, 강의노트== | ||
+ | * Backhouse, Roland, and João F. Ferreira. “On Euclid’s Algorithm and Elementary Number Theory.” Science of Computer Programming 76, no. 3 (March 2011): 160–80. doi:10.1016/j.scico.2010.05.006. |
2015년 7월 13일 (월) 06:32 판
유클리드 호제법
- 두 정수 $a,b$의 최대공약수를 구하는 알고리즘
- $a\geq b >0$라고 가정하자
- $r_{-1}=a, r_0=b$라 두고, 다음과 같은 나눗셈을 반복
$$ \begin{aligned} r_{-1}&=r_0q_0+r_1,\, 0<r_1<r_0 \\ r_{0}&=r_1q_1+r_2 ,\, 0<r_2<r_1 \\ \cdots \\ r_{n-1}&=r_{n}q_{n}+r_{n+1},\, 0<r_{n+1}<r_n \\ r_{n}&=r_{n+1}q_{n+1}\\ \end{aligned} $$
- 나눗셈을 반복하여 나머지가 0이 될 때, 얻어지는 $r_{n+1}$이 $a,b$의 최대공약수이다
- 이 때, $k=n+2$회의 나눗셈이 필요하며, $a\geq F_{k+1}=F_{n+3}$이 성립한다. 여기서 $F_k$는 피보나치 수열
$$F_0=0,F_1=1,F_{n+2}=F_{n+1}+F_n$$
- 정리
두 자연수 $a\geq b>0$에 유클리드 호제법을 적용할 때 필요한 나눗셈의 회수 $k$에 대하여 다음이 성립한다 $$ k<2.08\log a+1.45 $$
예1
- 두 자연수 $692,128$에 대하여 호제법을 적용하면, 다음을 얻는다
$$ \begin{array}{c|c|c} k & r_k & r_{k+1} \\ \hline -1 & 692 & 128 \\ 0 & 128 & 52 \\ 1 & 52 & 24 \\ 2 & 24 & 4 \\ 3 & 4 & 0 \\ \end{array} $$
- 따라서 최대공약수는 4가 된다
- $2.08\log 692+1.45=15.03\cdots$
예2
- 두 자연수 $610,377$에 대하여 호제법을 적용하면, 다음을 얻는다
$$ \begin{array}{c|c|c} k & r_k & r_{k+1} \\ \hline -1 & 610 & 377 \\ 0 & 377 & 233 \\ 1 & 233 & 144 \\ 2 & 144 & 89 \\ 3 & 89 & 55 \\ 4 & 55 & 34 \\ 5 & 34 & 21 \\ 6 & 21 & 13 \\ 7 & 13 & 8 \\ 8 & 8 & 5 \\ 9 & 5 & 3 \\ 10 & 3 & 2 \\ 11 & 2 & 1 \\ 12 & 1 & 0 \\ \end{array} $$
- 따라서 최대공약수는 1이고, 14번의 나눗셈을 수행하게 된다
- $2.08\log 610+1.45=14.768\cdots$
- 일반적으로 피보나치수열의 인접한 두 항에 대하여 호제법을 적용하면, 필요한 나눗셈의 회수가 커지게 된다
베주 항등식
- 두 정수 $a,b$의 최대공약수 $\gcd(a,b)$에 대하여, 적당한 $x,y\in \mathbb{Z}$가 존재하여, 다음을 만족한다
$$ax+by=\gcd(a,b)$$
매스매티카 파일 및 계산 리소스
사전형태의 자료
리뷰, 에세이, 강의노트
- Backhouse, Roland, and João F. Ferreira. “On Euclid’s Algorithm and Elementary Number Theory.” Science of Computer Programming 76, no. 3 (March 2011): 160–80. doi:10.1016/j.scico.2010.05.006.