유클리드 호제법 (약수 개수, 최대 공약수, 최소 공배수)

0. 파이썬은 python 3.5부터 gcd를 python 3.9부터 lcm을 math라이브러리에서 제공

 

1. 약수: 나누어 떨어지는 수

 

1-1 N의 약수 구하는 법:

1. 1부터 N이하의 정수로 N을 나누어, 나머지가 0이 되는 수를 찾음( 시간 복잡도: O(N) )
2. 1부터 √n이하의 정수로 N을 나누어, 나머지가 0이 되는 수를 찾고, 그 개수에 2를 곱함. N이 제곱수면, √N이 중복되므로 하나 뺌( 시간 복잡도: O(√N) )

2. 유클리드 호제법:  A = Bq + R이라 할 때, A, B의 최대공약수 G(A, B)와 B, R의 최대공약수 G(B, R)이 같다.

 

두 수 A, B가 있고, 그 두 수의 최대공약수가 G라고 하자. (A > B)

(단 a, b 는 서로소)

A는 아래처럼 나타낼 수도 있다.

(q는 몫, R은 나머지)

이항하면 아래와 같이 되고,

A대신 Ga를,

B대신 Gb를 대입하면 아래와 같이 된다.

공통인수 G로 묶어주면 R은 아래와 같이 된다.

 

결론적으로 이런식으로 나오게 된다.

 

이때, a-bq와 a, a-bq와 b가 서로소이기만 하면 최대공약수가 G가 되면서 성립하게 된다.

 

---

a-bq와 a, a-bq와 b가 서로소임을 증명하는 과정

 

귀류법을 이용

 

증명하려는 명제

b와 a-bq가 서로소이다

 

※ b와 a-bq가 서로소가 아니라면 공약수 m이 존재( k와 k ′는 서로소)

 

 

a와 b는 공약수 m 갖게 된다.

 

i)m ≠ 1이면 2이상의 공약수를 같게되어

a, b 는 서로소라는 전제에 모순.

∴ b와 a-bq가 서로소이다.

 

ii) m =1이면 공약수가 1이므로

b와 a-bq가 서로소가 된다. (모순)

 

 

∴ b와 a-bq가 서로소이다.

 

즉 A와 B(A>B)가 있을 때, A % B % R % ... 했을 때, 나누어 떨어지는 수가 최대 공약수가 됨.(R은 A % B의 값)

 

 

3. GCD(최대 공약수) 코드:

def GCD(a, b):
	while b:
    	a, b = b, a % b
    return a

 

4. LCM(최소 공배수) 코드:

def LCM(a, b):
	gcd = GCD(a, b)
	return (a * b) / gcd