오늘도 이해되지 않는 내용을 스스로 정리하고자 포스팅을 한다 ㅎㅎ..

유클리드 호제법

• 두 개의 자연수의 최대공약수를 구하는 알고리즘
• a를 b로 나눈 나머지를 r이라 할 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
  a % b = r, gcd(a, b) = gcd(b, r)

gcd(36, 24) = 12
gcd(24, 12) = 0
-> 0이 나올 때 b의 값이 최대공약수. (딱 나눠떨어지므로)
즉 36과 24의 최대공약수는 12

코드로는 다음과 같이 표현할 수 있겠다.

    // gcd(a, b) == gcd(b, a%b)를 이용, a % b == 0 일 때 반복 멈추기
    static int gcd(int a, int b) {
        while (b!=0) { // 딱 나눠 떨어졀 때까지 반복
            int r = a % b; // a를 b로 나눈 나머지
            a = b;
            b = r; // b에 나머지 대입
        }
        return a;
    }
}

코드 상으로 b=0이라 a가 최대공약수가 되었지만 반복문 직전에 b를 a에 대입한 걸 볼 수 있다!

또한 유클리드 호제법에 따르면 a, b, c의 최대공약수는 (a, b)의 공약수와 c의 최대공약수와 같다.
이를 이용해서 다음과 같이 재귀적으로 사용할 수도 있다.

gcd(gcd(a, b), c) // 이전 코드와는 무관

여기까진 나름 쉽다!
그런데 어질어질한 '확장' 유클리드 호제법이 날 기다리고 있었다,,,
확장 유클리드 호제법에 들어가기 전에 알아두면 좋은 정수론을 조금 훑고 가자

정수론

부정 방정식

• 해가 무수히 많은 방정식

디오판토스 방정식

• 해가 정수인 경우의 부정 방정식 (ex: 3x+2y = 5)

베주 항등식

정수 x, y의 최대공약수 gcd(x, y)가 있을 때
확장 유클리드 호제법을 이용하여 ax + by = gcd(x, y)의 해가 되는 정수 a, b 짝을 찾아낼 수 있다.
(이 때 a, b 중 한개는 보통 음수가 됨)
이 식을 베주의 항등식이라고 한다.

=> ax+by=gcd(x, y)이면 방정식의 해를 찾을 수 있다.
==> ⭐️ 방정식의 해가 반드시 존재한다 ⭐️

확장 유클리드 호제법

ax + by = c 에서
as + bt = r 이라는 식을 만들었다. (원래 식에서 a, b만 가져온 형태)

ex) 9x + 5y = 2 -> 9s + 5t = r

이 식을 만족하는 숫자 3개를 만들어 보고자 한다.
9s + 5t = r을 만족하는 가장 작은 r을 찾아보자.

1. s = 1, t = 0일 경우 r = a
2. s = 0, t = 1일 경우 r = b

두가지 식은 언제나 성립한다.
이 특징을 이용해서 s = 1, t = 0을 대입하면 r = a = 9가 된다.
s = 0, t = 1을 대입하면 r = b = 5가 된다.

s	t	r
1	0	9
0	1	5

현재 두 가지 조합을 찾았다!
다음 조합도 찾아보자.

9를 5로 나누면 4가 남는다.
-> 5를 4로 나누면 1이 남는다.
-> 4를 1로 나누면 0이 남는다.

s	t	r
1	0	9
0	1	5
		4
		1

익숙한 과정이지 않는가?
바로 전 단계에서 배운 유클리드 호제법이다.
이 과정에서 gcd(최대공약수)는 1이다.

이 과정을 자세히 보면

9를 5로 나누는 과정 = 5(나눈 수)에 1(몫)을 곱하고 9에서 빼준다. (9-5=4)

임을 알 수 있다.
여기서 1은 별뜻 없는 게 아니고 9를 5로 나눈 몫이다!!!!
즉 원래 수 - 나눈수*몫 이라는 뜻!
값에 1을 곱하고 원래 값에서 빼 주는 같은 방식으로 표의 빈 공간을 채워보자.
(헷갈리지 않게 몫을 뜻하는 q의 값을 표에 추가하였다)

1에 1을 곱하고 0에서 빼준다. => 0 - 1 = -1
0에 1을 곱하고 1에서 빼준다. => 1 - 0 = 1

s	t	r	q
1	0	9
0	1	5
1	-1	4	1
		1

새로운 행이 완성되었다!
이 표의 값을 원래 식에 대입하면 성립할까?

9*1 + 5*(-1) = 4
=> 9 - 5 = 4

성립한다!!
식을 만족하는 s, t, r을 또 하나 찾은 셈이다. (해를 찾은 건 아니다)

한 번 더 표의 빈 부분을 채워보자.
이번에는 한 줄 내려와 a = 5, b = 4, r = 1이 된다.
따라서 q는 5 / 4 = 1 이다.

-1에 1을 곱하고 1에서 빼준다. => 1 + 1 = 2
1에 1을 곱하고 0에서 빼준다. => 0 - 1 = -1

s	t	r	q
1	0	9
0	1	5
1	-1	4	1
-1	2	1	1

이렇게 찾아낸 값을 또 원래 식에 대입해 보자.

9*(-1) + 5*2 = 1
=> -9 + 10 = 1

역시 성립한다.
새로운 s, t, r을 찾았다.

한 번 더 해보자!
q는 4 / 1 = 4이며, r(나머지)는 0이다.
0이 됐다는 건, 딱 나눠떨어진다는 뜻이고 이를 나눈 값인 1이 gcd라는 뜻이 된다.
베주 항등식에서, ax + by = gcd(a, b)일 경우 해가 반드시 존재한다고 했었다.
여기서 다시 한 번 표를 보자. (거의 반복학습 ㅋㅋㅋ)

s	t	r	q
1	0	9
0	1	5
1	-1	4	1
-1	2	1	1

우리는 식을 as + bt = r로 만든 후 구했고 현재 식을 만족하는 gcd는 1이다. (r = 1)
r = 1을 만족할 수 있게 만드는 x, y는 s, t에 해당하는 -1, 2이다.
또 9*(-1) + 5*2 = 1 이 성립함도 확인했다.

아직 해는 구하지 못했다!
우리가 해를 구하려던 방정식은 9x + 5y = 2 이었다.
s, t, r을 대입하여 나온 9*(-1) + 5*2 = 1 식을 위와 같이 만들기 위해서는 전체*2를 해 줘야 한다.

[9*(-1) + 5*2 = 1] * 2
= 9x + 5y = 2와 같다.

따라서 x = -2, y = 4임을 알 수 있다!
길고 길었지만 마침내 해를 구했다 👏

최대공약수

유클리드 호제법을 이용하여 구한다.

최소공배수

두 수의 곱 / 최대공약수

정리

s, t, r의 조합을 찾는다는 생각으로 계속하여 유클리드 호제법을 이용해서 계산하고,
r이 gcd가 되는 순간 원래 방정식과 비교하여 해를 구할 수 있다.
포스팅을 하다보니 또 머리에서 정리가 된 것 같다!
이걸 코드로 구현할 수 있을지는... (먼산)
아무튼 오늘 포스팅은 끝 ㅎㅎㅎ