====== 최대 공약수 (GCD; Greatest Common Divisor) ======
  * 최대 공약수가 뭔지는 생략해도 충분할듯.

===== 최대 공약수 알고리즘 =====
  * 가장 유명한 것은 유클리드 알고리즘이고, 시간복잡도도 O(logn)으로 최적이지만, 실질적으로는 좀더 빠르게 돌아가는 Binary GCD 알고리즘이나 Lehmer's algorithm 등도 있다.
  * 파이썬에서는 math.gcd 함수에 구현되어 있기 때문에, 굳이 직접 구현할 필요는 없다.
    * 내부 구현은 Lehmer's algorithm 이라고 한다.

==== 유클리드 알고리즘 ====
  * [[wp>Euclidean algorithm]] (Euclid's algorithm 으로도 불린다)
  * 유클리드 호제법이라고도 불린다. 
  * 두 양의 정수의 최대 공약수를 구하기 위해 사용되는 알고리즘. 중학교 수학 교과에도 포함되어 있고, 코딩 과목을 듣다보면 코드로 짜는 연습도 한번쯤은 해보게 된다.
  * 기원전 300년경에 기록되어서, 인류 최초의 알고리즘으로도 알려져있다.
    * 원래 알고리즘은 스텝마다 나눗셈을 하는게 아니라, 스텝마다 뺄셈을 하는 방식이었다고 한다.. 이건 좀 느린데;;
  * 로직도 심플하고 코드도 간단하게 작성 가능하다 (재귀함수로 구현하면 한줄에도 가능).
  * 유클리드 알고리즘으로 GCD(n,m)을 구할때 필요한 나눗셈의 횟수는 O(log(max(n,m)))이다. 
    * PS에서는 나눗셈을 O(1)로 취급하니까 그냥 시간복잡도가 O(log(max(n,m)))이라고 생각하면 간단하다. 
    * 이것을 제대로 처음 증명한것이 [[wp>Lamé's Theorem]]인데, 계산복잡도 이론의 시초라고 한다  

==== Binary GCD algorithm ====
  * [[wp>Binary GCD algorithm]]
  * Stein's algorithm 이라고도 불리긴 하지만, 실제로는 스타인이 1967년에 발표하기 훨씬전인 기원전 2세기에 중국에서 이미 알려져 있었다고 한다.
  * 나눗셈을 쓰지 않고, 비트쉬프트연산과 뺄셈만으로 GCD를 구하도록 개선된 알고리즘
  * 시간복잡도는 유클리드 알고리즘과 동일하게 O(log(max(n,m))이지만, 실질적으로는 더 빠르게 돌아간다고 한다. 

==== Lehmer's GCD algorithm ====
  * [[wp>Lehmer's GCD algorithm]]
  * 큰수들 간의 GCD를 구할때 효율적이다
  * cpython의 math.gcd는 이 알고리즘으로 구현되어 있다
    * Pypy에서는 그냥 유클리드 알고리즘으로 구현되어있기 때문에, 큰수의 GCD를 구할 때에는 pypy가 훨씬 느리다는 이야기가 있다. ([[https://foss.heptapod.net/pypy/pypy/-/issues/3031]])

===== 베주 항등식 =====
  * [[wp>Bézout's identity]]
  * 이름은 항등식인데, 내용은 정리에 가깝다. (Bézout's lemma 라고도 불린다고 한다) 
  * 내용은
    * 두 정수 n, m 이 있을때, nx+my=gcd(n,m) 을 만족시키는 정수 x와 y가 반드시 존재한다
    * 정수 x와 y에 대해서 nx+my=d 를 만족시키는 정수 d는 항상 gcd(n,m)의 배수이다.
  * 여기서 바로 알수 있는 것들은
    * nx+my=c 라는 부정방정식이 있을때, c가 gcd(n,m)의 배수가 아니라면 x,y의 정수해가 존재하지 않는다
    * (x0, y0)가 nx+my=d 의 하나의 해일때, 일반해는 (x0 + k*m/gcd(n,m), y0 - k*n/gcd(n,m)) 이 된다

===== 확장 유클리드 알고리즘 (Extended Euclid Algorithm) =====
  * m과 n이 주어졌을때, nx+my=gcd(n,m) 을 만족시키는 정수 x0와 y0, 그리고 gcd(n,m)을 함께 구하는 알고리즘
    * 이런 x,y가 존재한다는 것은 베주 항등식에서 알수 있다.
  * 코드는 유클리드 알고리즘을 조금만 수정하면 된다. 시간복잡도도 동일하게 O(log(max(n,m)))
  * 이제 nx+my=c 의 해를 다음 과정으로 구할 수 있다.
    * 확장 유클리드 알고리즘을 통해서 gcd(n,m)과 nx+my=gcd(n,m)를 만족시키는 x0, y0 를 구한다
    * c % gcd(n,m) != 0이면 해가 없다. 그렇지 않으면 x0*c/gcd(n,m), y0*c/gcd(n,m) 이 nx+my=c 의 해가 된다
    * 일반해는 (x0*c+k*m)/gcd(n,m), (y0*c-k*n)/gcd(n,m) 이 된다
  * 확장 유클리드 알고리즘이 사용되는 가장 흔한 경우는 모듈러 역원을 계산하는 것이다.
    * a의 m에 대한 모듈러 역원 x는 a*x % m = 1 을 만족하는 x이다
    * 이걸 다시 쓰면 ax-my = 1 이 된다. 즉, gcd(a,m)이 1보다 크면 역원이 없고, 서로소라면 a,m에 대해서 확장 유클리드 알고리즘을 돌리면 x값을 찾을수 있다.
  * 파이썬에는 pow함수가 모듈러 역원을 계산해주기 때문에 모듈러 역원 계산을 위해서 확장 유클리드 알고리즘을 새로 코딩할 필요는 없다. 오히려 역으로 pow함수를 이용해서 확장 유클리드 알고리즘을 구현하는 것도 가능하다.
    * nx+my=gcd(n,m)를 만족하는 정수 x0,y0을 찾는다고 하자.
    * 먼저 math.gcd를 이용해서 gcd(n,m) = g 를 계산하자
    * 양변을 g로 나눠서 (n/g)x + (m/g)y = 1 로 만들고 이항하면, (n/g)*x ≡ 1 mod (m/g) 가 되므로 x=pow(n/g, -1, m/g)로 계산할수 있다. y도 마찬가지로 y=pow(m/g, -1, n/g) 으로 계산하면 된다.
    * gcd를 먼저 구하고 역원을 다시 구해야 하므로 속도상으로는 좀 비효율적일수 있지만, 계산 자체가 가벼워서 별로 차이는 안난다. 확장 유클리드 알고리즘을 반복해서 적용해야 하는 문제를 본적도 없어서 별 신경 안써도 될것 같다
    * 그것보다는, 그냥 확장 유클리드 알고리즘 코드를 구현해도 워낙 심플하기 때문에 굳이 이렇게 회피해야 하는가 하는 생각은 든다.