유클리드 호제법
예를 들어 A와 B의 최대 공약수 흔히 GCD라고 부르는 최대공약수를 구하는데, 이럴 때 만약 A>B라면 A와 B의 최대공약수는
A를 B로 나눈 나머지를 R이라고 할 경우 A와 B사이의 최대 공약수는 B와 R사이의 최대 공약수와 똑같다.
최대 공약수 문제가 나왔을 때 흔히 A = aG, B = bG (G = 최대공약수)
최대 공약수라는 이름을 유지하기 위해서는 더이상의 공약수가 없어야 하기 때문에 여기서 a와 b는 서로소다.
이들의 최대 공약수가 G니까 정말로 A를 B로나눈 나머지가 r이였을 때, b와 r과의 최대공약수도 G가 되는지만 확인하면 된다.
A를 예를들어 B로 나누었으면 몫이 있다. 그 몫을 우리는 q라고 해본다.
이럴 경우 A = q*B+r이 된다.
A = a * G다 라고 표현을 했으므로 똑같이 표현해주면 aG = q * bG + r이 되어서 결과적으로 r = (a-qb)G가 된다.
r = (a-qb)G, B = bG니까 이 둘 사이의 최대 공약수가 r과 B사이의 최대 공약수가 G다.
결과적으로 (a-gb)와, b가 서로소임을 보이면 되는것. 이 둘 사이의 더이상 공통되는 약수가 없으면 결국 r과 b와의 최대공약수도 G가 되는것.
a-qb = mp, b = np라고 가정 할 경우
a - q*np = mp
a는 p로 묶었을때,
a = (nq + m)p
b = np 가 된다.
a와 b는 서로소라는 걸 알고 있지만 p라는 공약수가 있게되는것, 공통 인수가 있게되는것.
이렇게되면 a와 b는 서로소가 아니다 라는게 되는 것. 그럼 a와 b가 서로소라는 사실에 위배되는거기 때문에 결과를 부정해서 놓은것.
이랬을 때 모순이 발생했으므로 ea - qb와 b는 서로소구나 라는걸 알 수 있는 것.
*서로소: 두 자연수 a, b에 대하여 a와 b의 최대공약수가 1이라면 두 자연수를 서로소라고 한다.
15와 16은 서로소다.
15를 소인수분해하면 3x5
16을 소인수분해하면 2x2x2x2
15의 소인수는 3, 5
16의 소인수는 2이다.
겹치는 소인수가 없으므로 15와 16은 소인수다.
유클리드 호제법을 이해하기 위해선 MOD연산(%)이 필요하다
MOD연산은 두 값을 나는 나머지를 구하는 연산이다.
먼저 큰 수를 작은수로 나눈 나머지를 구한다.
1112 % 695 = 417
다음 나눴던 수와 나머지로 또 MOD연산을 한다.
695 % 417 = 278
417 % 278 = 139
278 % 139 = 0
나머지가 0이 되었을 때, 마지막 계산에서 나누는 수로 사용된 139가 1112와 695의 최대공약수가 된다.
func GCD(_ a: Int, _ b: Int) -> Int{
return b ? GCD(b, a % b) : a
}
참고
https://velog.io/@yerin4847/W1-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95