요약

(1)

정수론, 제5장

가약성과 최대공약수

^{이상준 교수}(덕성여대 수학과) 2015년 2학기

교재 : 친절한 수론 길라잡이 (4판)

조셉 실버만 지음, 김병찬,김지영,이종규,박부성 옮김

강의 슬라이드: 이상준, 오연주(15학번)

(2)

요약

❖ 약수와 배수

❖ 최대공약수

❖ 최대공약수를 구하는 방법: 유클리드 호제법 (Euclidean algorithm)

❖ 알고리즘 증명과 계산량

(3)

약수와 배수

❖ 정의: 정수 n과 0이 아닌 정수 m이 있다고 가정하자.

• 만일 적당한 정수 k가 존재하여 n=mk 를 만족하면 다음과 같이 표현한다. 

① m이 n을 나눈다. 

② m은 n의 약수 (divisor)이다. 

③ n은 m의 배수 (multiple)이다. 

라고 하고, m

∣

^{n 이라고 쓴다.}

• 만일 m이 n을 나누지 않을 때, m

∤

^{n 이라고 쓴다.}

❖ 예: 6 = 3·2, 132 = 12·11 이므로 3

∣

^{6, 12}

∣

^{132 이다.}

❖ 주의: 0

∤

^{a, 7}

∣

0 0은 약수가 될 수 없다. (배수는 될 수 있다.)

(4)

공약수

❖ 정의: 정수 a, b, c (c≠0)가 있다고 가정하자. 

만일 c가 a와 b를 나눈다면, c를 a와 b의 공약수 (common divisor)라 한다.

❖ 예: 4는 12와 20의 공약수이다.

❖ 최대공약수 (greatest common divisor):  

두 정수 a와 b의 최대공약수는 a와 b의 공약수 중에서 가장 큰 수이다. 

기호로는 gcd(a,b) 로 표기한다.

❖ 만일 gcd(a,b)=1 이면 ‘a와 b는 서로소이다.’ 라고 한다.

❖ 예: gcd(12,20) = 4, gcd(18,30) = 6, gcd(225,120) = 15

❖ 주의: 만일 a≠0 이면, gcd(a,0)=a.

(5)

❖ 질문: gcd(1160718174,316258250) 를 어떻게 구할까?

❖ 답: “유클리드 호제법”을 사용할 수 있다.

1160718174 = 3 × 316258250 + 211943424 316258250 = 1 × 211943424 + 104314826

211943424 = 2 × 104314826 + 3313772

104314826 = 31 × 3313772 + 1587894

3313772 = 2 × 1587894 + 137984

1587894 = 11 × 137984 + 70070

137984 = 1 × 70070 + 67914

70070 = 1 × 67914 + 2156

67914 = 31 × 2156 + 1078

2156 = 2 × 1078 + 0

⟵ gcd

(6)

❖ 쓰는 법: ^1160718174

211943424

3313772

137984

70070 67914

1078

316258250

211943424 104314826

1587894

70070

67914 21562156 0 3

2

1

31

1

31

11

1 2

(7)

❖ 예제: gcd(143,227)=?

(8)

❖ 예제: gcd(12378,3054)=?

(9)

유클리드 호제법 (Euclidean algorithm)

❖ gcd(a,b) 를 얻기 위해 다음을 계산 한다.

(10)

❖ 정리 (유클리드 호제법, Euclidean algorithm):

1. 두 개의 수 a와 b (a>b)의 최대공약수를 계산하려면, r^-1 = a, r0 = b 라 놓고, 2. 다음의 몫과 나머지 구하는 과정 ri-1 = qi+1 × ri + ri+1 ( i = 0,1,2,...)을 계속하여, 

나머지 rn+1 이 0이 될 때까지 반복한다.

3. 이 때, 0이 아닌 마지막 나머지 rn 이 a와 b의 최대공약수이다.

❖ 질문: 유클리드 호제법은 항상 끝날까?

❖ 답: a > b > r₁ > r₂ > … 이고 ri ≥ 0 이므로  유한번의 단계 안에 끝난다.

(11)

궁금한 점

❖ 유클리드 호제법 증명

❖ 질문: 유클리드 호제법이 끝나려면  

몫과 나머지를 구하는 과정이 몇번 필요할까?

(12)

유클리드 호제법의 증명

❖ 보조정리: 만일 a = qb + r 이면, gcd(a,b) = gcd(b,r) 이다.

❖ 보조정리로부터 유클리드 호제법의 증명: 

a > b > r₁ > r₂ > … > rn > 0 

gcd(a,b) = gcd(b,r1) = gcd(r1,r2) = … = gcd(rn,0) = rn

❖ 보조정리의 증명: g = gcd(a,b), g* = gcd(b,r) 라 하자.

1. g ≤ g* 를 보이자: g

∣

^{a, g}

∣

b ⟹ a=kg, b=lg  r = a-qb = kg-qlg = g(k-ql) ⟹ g

∣

r 

g 가 b,r의 공약수이고, g*가 최대공약수 이므로 g ≤ g*.

2. g* ≤ g 를 보이자: 비슷한 방법!

(13)

❖ 연습: g* ≤ g 를 보이자.

(14)

유클리드 호제법이 끝나려면 몇 단계가 필요할까?

(15)

필요한 단계 수 계산: