"최대공약수"의 두 판 사이의 차이

수학노트
둘러보기로 가기 검색하러 가기
(새 문서: ==베주 항등식== * 두 정수 $a,b$의 최대공약수 $\gcd(a,b)$에 대하여, 적당한 $x,y\in \mathbb{Z}$가 존재하여, 다음을 만족한다 $$ax+by=\gcd(a,b)$$ ==사...)
 
 
(같은 사용자의 중간 판 5개는 보이지 않습니다)
1번째 줄: 1번째 줄:
 +
==유클리드 호제법==
 +
* 두 정수 <math>a,b</math>의 최대공약수를 구하는 알고리즘
 +
* <math>a\geq b >0</math>라고 가정하자
 +
* <math>r_{-1}=a, r_0=b</math>라 두고, 다음과 같은 나눗셈을 반복
 +
:<math>
 +
\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}
 +
</math>
 +
* 나눗셈을 반복하여 나머지가 0이 될 때, 얻어지는 <math>r_{n+1}</math>이 <math>a,b</math>의 최대공약수이다
 +
* 이 때, <math>k=n+2</math>회의 나눗셈이 필요하며, <math>a\geq F_{k+1}=F_{n+3}</math>이 성립한다. 여기서 <math>F_k</math>는 [[피보나치 수열]]
 +
:<math>F_0=0,F_1=1,F_{n+2}=F_{n+1}+F_n</math>
 +
;정리
 +
두 자연수 <math>a\geq b>0</math>에 유클리드 호제법을 적용할 때 필요한 나눗셈의 회수 <math>k</math>에 대하여 다음이 성립한다
 +
:<math>
 +
k<2.08\log a+1.45
 +
</math>
 +
===예1===
 +
* 두 자연수 <math>692,128</math>에 대하여 호제법을 적용하면, 다음을 얻는다
 +
:<math>
 +
\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}
 +
</math>
 +
* 따라서 최대공약수는 4가 된다
 +
* <math>2.08\log 692+1.45=15.03\cdots</math>
 +
===예2===
 +
* 두 자연수 <math>610,377</math>에 대하여 호제법을 적용하면, 다음을 얻는다
 +
:<math>
 +
\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}
 +
</math>
 +
* 따라서 최대공약수는 1이고, 14번의 나눗셈을 수행하게 된다
 +
* <math>2.08\log 610+1.45=14.768\cdots</math>
 +
* 일반적으로 피보나치수열의 인접한 두 항에 대하여 호제법을 적용하면, 필요한 나눗셈의 회수가 커지게 된다
 +
 +
 +
 
==베주 항등식==
 
==베주 항등식==
−
* 두 정수 $a,b$의 최대공약수 $\gcd(a,b)$에 대하여, 적당한 $x,y\in \mathbb{Z}$가 존재하여, 다음을 만족한다
+
* 두 정수 <math>a,b</math>의 최대공약수 <math>\gcd(a,b)</math>에 대하여, 적당한 <math>x,y\in \mathbb{Z}</math>가 존재하여, 다음을 만족한다
−
$$ax+by=\gcd(a,b)$$
+
:<math>ax+by=\gcd(a,b)</math>
 +
 
 +
 
  
 +
==매스매티카 파일 및 계산 리소스==
 +
*
  
  
 
==사전형태의 자료==
 
==사전형태의 자료==
 
* 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.
 +
 +
==메타데이터==
 +
===위키데이터===
 +
* ID :  [https://www.wikidata.org/wiki/Q289471 Q289471]
 +
===Spacy 패턴 목록===
 +
* [{'LOWER': 'étienne'}, {'LEMMA': 'Bézout'}]
 +
* [{'LOWER': 'etienne'}, {'LEMMA': 'Bezout'}]
 +
* [{'LOWER': 'etienne'}, {'LEMMA': 'Bézout'}]
 +
* [{'LEMMA': 'bezout'}]
 +
* [{'LOWER': 'e.'}, {'LEMMA': 'Bézout'}]
 +
* [{'LOWER': 'étienne'}, {'LEMMA': 'bézout'}]
 +
* [{'LEMMA': 'bézout'}]
 +
* [{'LOWER': 'etienne'}, {'LEMMA': 'bezout'}]
 +
* [{'LOWER': 'e.'}, {'LEMMA': 'Bezout'}]

2021년 2월 17일 (수) 02:25 기준 최신판

유클리드 호제법

  • 두 정수 \(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.

메타데이터

위키데이터

Spacy 패턴 목록

  • [{'LOWER': 'étienne'}, {'LEMMA': 'Bézout'}]
  • [{'LOWER': 'etienne'}, {'LEMMA': 'Bezout'}]
  • [{'LOWER': 'etienne'}, {'LEMMA': 'Bézout'}]
  • [{'LEMMA': 'bezout'}]
  • [{'LOWER': 'e.'}, {'LEMMA': 'Bézout'}]
  • [{'LOWER': 'étienne'}, {'LEMMA': 'bézout'}]
  • [{'LEMMA': 'bézout'}]
  • [{'LOWER': 'etienne'}, {'LEMMA': 'bezout'}]
  • [{'LOWER': 'e.'}, {'LEMMA': 'Bezout'}]
원본 주소 "https://wiki.mathnt.net/index.php?title=최대공약수&oldid=52025"