[암호학] GCD, LCM

도입

GCD, Great Common Divisor는 최대공약수로 두 수가 가지는 공통 약수; 공약수 중에 가장 큰 수를 의미한다고 흔히 알려져 있으며 현재까지 그렇게 배워왔을 것이다.
→ 과연 실제 정의도 이와 동일할까?

 

1. GCD : Great Common Divisor

 

1.1. Definition of GCD

$$\gcd(a,b) = d$$

Definition 1. for integers $a$ and $b$ unique integer $d$ s.t.,

• $d|a$, and $d|b$
• for all possible $c$, $c|a$ and $c|b$ implies $c|d$.

즉, $\gcd(a,b)=d$는 $a$와 $b$의 공약수이며, $a,b$의 공약수인 모든 $c$에 대해 $c$는 $d$의 약수이다.

우리가 최대공약수를 배워오면서 느꼈던 공약중에서 “최대"라는 의미와는 다르게 실제 GCD의 Definition에서는 최대에 대한 언급이 없는 것을 알 수 있다.

두번째 조건을 만족하는 $d$는 공약수 $G(a,b)$[^1]중에서 최대인 값을 만족하지만(→), 이러한 정의는 두 수의 공약수 중에서 최대인 수 $\max G(a,b)$를 나타내는 정의와는 분명히 다르다.

즉, $c|d$가 되면 $c\le d$가 되지만, $c\le d$라고 해서 $c|d$가 되는건 아니다. (!←)
e.g.,) $2|4$이면 $2\le4$이지만, $3\le5$라고 해서 $3|5$가 성립하지는 않는다.

 

⇒ 그렇다면 이러한 정의는 왜 사용하는 것일까?
GCD의 정의에 따르면 $G(a,b)$는 반드시 $\gcd(a,b) = d$ 그리고 최대공약수의 약수들의 집합으로만 이루어져야하기 때문이다.
$$ G(a,b) = {{d'\text{s divisor}}, d} $$
즉, 정의에서 이미 공약수 집합은 ${1,2,3,5}$와 같은 형태로 정의될 수 없음을 명시하기 위한 역할을 하고 있는 것이다.

proof about Equivalence of GCD Definitions

공약수의 정의를 사용면 두 정의가 동일하다는 것을 보일 수 있다.

[!tip] 즉, $D(a, b)$ 가 $D(d)$와 동일함을 증명한다.

두 집합이 동일하다는 것을 보이기 위해서는 양방향의 포함관계를 모두 보이면 된다.

• $ $D(a,b) \subseteq D(d)​$

어떤 $c \in D(a,b)$를 가정하자. $c$가 $a$와 $b$를 모두 나누기 때문에 다음이 성립한다.

• $a = cs$
• $b = ct$

$d$는 최대공약수이기 때문에 $d=ax+by$로 표현할 수 있다. 유틀리드 선형조합식에 위에서 $a$와 $b$를 선형조합으로 표현한 수식을 대입할 수 있다. 식을 정리하면 $c$가 $d$의 약수임을 알 수 있다.
$$ \begin{align} d &= csx + cty \ d &= c(sx+ty)\end{align}$$
따라서 $c \in D(d)$이므로 위의 포함관계가 성립한다.

• $ $D(d) \subseteq D(a,b)​$

어떤 $c \in D(d)$를 가정하면 다음이 성립하고, $d$가 최대공약수임을 이용해보자.

• $d = cs$
• $d=ax+by$

아래서 증명할 [[GCD and LCM#Theorem 3]]을 적용하면 $a=a_0d, b=b_0d$, and $\gcd(a_0, b_0) = 1$가 존재한다는 것을 알 수 있다. 따라서 식에 a, b를 다시 대입하면 다음과 같이 표현할 수 있다. $$ d = a_0dx+b_0dy $$ 여기에 $d=cs$를 대입할 수 있고, 식을 정리하면 $c$가 $a$, $b$의 약수임을 알 수 있다. $$ \begin{align} d &= a_0csx + b_0csy \ d &= c(a_0sx+b_0sy)\end{align}$$
따라서 $c \in D(a, b)$이므로 위의 포함관계가 성립한다. 양방향 모두 성립하므로 두 집합은 동일하다.$\Box$

 

1.2. GCD & Relatively Prime

만약 두 수 $a, b$가 서로소; Relatively Prime이라면 $\gcd(a,b)=1​$이다.

 

1.3. Extension GCD

2개의 정수가 아니라 그보다 더 많은 수에 대해서도 적용할 수 있다. $$ \gcd(a,b,c) = d $$

Definition 2 : Extension GCD

• $d|a, d|b, d|c$
  • for all possible $e$, $e|a$, $e|b$, $e|c$ implies $e|d$.
• $d \geq 0$

 

1.4. GCD를 어떻게 구하는가?

일반적으로 소인수 분해를 해서 최대공약수를 구할 수 있다. → 하지만 이 방법은 너무 느리다!
따라서 GCD를 구할 때는 [[Euclidean algorithm]]을 사용하게 된다. 자세한 내용은 유클리드 호제법 포스팅을 참고하자.

 

2. Property about GCD

2.1. Theorem 1

Theorem 1 $\gcd(a,b)=1$ iff for some $x$ and $y$, $ax+by=1​$

Proof about Theorem 1

iff이므로 양방향에 대한 증명을 모두 해야한다.

• $ If $\gcd(a,b)=1$ then $ax+by=1$
  • [[Euclidean algorithm#Extended Euclidean algorithm ⭐️|확장된 유클리드 호제법]]에서 사용했던 [[Euclidean algorithm#Property 1|property 1]]를 그대로 적용하면 증명할 수 있다.
• $ if $ax+by=1$ then $\gcd(a,b)$
  • $d|(ax+by)$는 $d|1$이므로 $d=1$이 된다.
  • $d|(ax+by)$가 되게하는 $d$는 [[Euclidean algorithm#Property 2|property 2]]에 의해 $\gcd(a,b)$인데, 위에서 $d=1$임을 확인했으므로 $\gcd(a,b)=1$.

두가지 케이스 모두에서 만족하므로 위 정리는 성립한다.$\Box$

 

2.2. Theorem 2

Theorem 2 $a|bc$ and $\gcd(a,b)=1$ then $a|c$

Proof about Theorem 2

먼저 증명을 위해 각각을 수식적으로 표현해보자.[^2]

• $a|bc$ → $bc=ka$ (1)
• $\gcd(a,b) =1$ → $ax+by=1$ (2)
• $a|c$ → $c=k'a$

따라서 가정이 만족될 때, $c=k'a$가 되게하는 $k'$가 존재함을 보이면 된다.
Eq 2의 양변에 $c$를 곱하고 Eq 1에서 $bc$를 표현한 식을 대입하여 정리하면 다음을 얻을 수 있다.
$$ \begin{align}acx+bcy&=c\ acx+kay &= c \ a(cx+by) &= c \end{align} $$
즉, $k'=cx+by$인 $k'$가 존재하므로 위 정리는 맞다.$\Box$

 

2.3. Theorem 3

Theorem 3 if $\gcd(a,b)=d$ then $a=a_0d, b=b_0d$, and $\gcd(a_0, b_0) = 1$

Proof about Theorem 3

최대”공약수”가 $d$이기 때문에 $a=a_0d, b=b_0d$임은 자명하다. $\gcd(a_0,b_0)=1$라는 것만 증명하자.

먼저 증명을 위해 수식적으로 표현해보자.

• $\gcd(a,b) =d$ → $ax+by=d$
• $\gcd(a_0,b_0) =1$ → $a_0q+b_0p=1$

첫번째 식에 $a=a_0d, b=b_0d$를 대입한 식은 아래와 같다. $$ a_0dx + b_0dy = d $$
식의 양변을 $d$로 나누면 $a_0x + b_0y=d$가 되고 이는 [[Euclidean algorithm#Property 1|property 1]]에 의해 $\gcd(a_0, b_0)=d$라는 의미와 동일하기 때문에 증명할 수 있다. $\Box$

 

2.4. Theorem 4

Theorem 4.1 if $\gcd(a,b)=1$ and $\gcd(a, c) = 1$ then $\gcd(a, bc)=1$

Proof about Theorem 4

먼저 증명을 위해 수식적으로 표현해보자.

• $\gcd(a,b)=1$ → $ax+by = 1$
• $\gcd(a,c)=1$ → $as+ct = 1$

위에서 표현한 수식은 모두 그 결과가 1이기 때문에, 수식의 좌변을 곱한 결과도 1이 되어야한다. $$ (ax+by)(as+ct) = 1$$ 식을 전개해서 나타내면, $a$와 $bc$에 대한 선형조합으로 나타낼 수 있다. $$ \begin{align}(axas + axct + byas + byct) &= 1 \ a(axs + xct + bys) + bc(yt) & = 1 \end{align}$$
따라서 $\gcd(a, bc)=1$ then $aq+bcp=1$을 만족하므로 증명할 수 있다.$\Box$

 

2.5. Theorem 4+

Theorem 4.2 if $\gcd(a, bc)=1$ then $\gcd(a,b)=1$ and $\gcd(a, c) = 1$

Proof about Theorem 4+

이 증명은 정말 간단하다. 가정을 수식으로 표현하면 $ax+bcy=1$이 된다.
위의 수식에서 어떤 항을 기준으로 생각하는지에 따라 모두 만족한다.

• $ax+b(cy) = 1$ → $ax+by'=1$
• $ax+c(by) = 1$ → $ax+cy'' = 1$

따라서 증명할 수 있다.$\Box$

 

 

3. LCM : Least Common Multipler

3.1. Definition of LCM

LCM은 최소공베수로 두 수가 가지는 공통 베수; 공배수 중에 가장 작은 수를 의미한다.
앞에서 GCD의 정의가 우리가 일반적으로 알고있는 것과는 달랐던 것 처럼 LCM의 정의도 약간 다르다.
$$ \text{lcm}(a,b) = l $$

Definition 3. for integers $a$ and $b$ unique integer $d$ s.t.,

• $a|l$ and $b|l$[^3]
• for all possible $c$, $a|c$ and $b|c$ implies $l|c$
• $l \geq 0$

즉, $\text{lcm}(a,b)=l$은 $a$와 $b$의 공베수이며, $a,b$의 공베수인 모든 $c$에 대해 $c$는 $l$의 배수이다.

 

4. GCD and LCM

4.1. with Relatively Prime

GCD와 LCM을 사용하면 "서로소"를 다양한 방식으로 정의내릴 수 있다. 다음 표현은 모두 동일하다.

• $a$와 $b$는 서로소 이다.
• = $\gcd(a,b)=1$
• = $\text{lcm}(a,b) = ab$
• = 어떤 $x,y$에 대해 $ax + by = 1$

 

Proof about LCM with Relatively Prime

$\text{lcm}(a,b) = ab$임을 증명하자.
아이디어 : $a$와 $b$의 공배수가 모두 $ab$로 나누어 떨어짐을 보이자.

$a$와 $b$의 공배수를 $c$라고 하자. $c$는 배수이기 때문에 다음의 식을 얻을 수 있다.

• $c = as$
• $c = bt$

서로소를 나타내는 다른 표현으로부터 $ax+by = 1$를 얻을 수 있다. 이 선형조합식의 양변에 $c$를 곱하고, c자리에 각 표현을 대입하면 $c$가 $ab$의 배수임을 보일 수 있다. $$ \begin{align}acx+bcy&=c\ abtx + bast &= c\ ab(tx+st) &= c \end{align} $$
따라서 서로소의 최소공배수는 두 수의 곱이다.$\Box$

 

4.2. GCD and LCM Relation

GCD와 LCM은 몇개의 관게를 갖는다. 다음을 한 번 증명해보자.

For $a$ and $b$, if $\gcd(a,b) = d$,

• $a = a_0d, \ \ b=b_0d$
• $\text{lcm}(a,b) = a_0b_0d​$
• $ab = \text{lcm}(a,b) \gcd(a,b)​$

proof about relation 1

GCD Theorem 3에 의하여 가정과, relation 1의 조건을 만족하면 $\gcd(a_0, b_0) = 1$도 만족한다. $\gcd$가 1이므로 선형조합으로 표현한 식도 1이 된다. $a_0 x + b_0 y=1$
위 식의 양변에 d를 곱하면 쉽게 보일 수 있다. $\Box$

proof about relation 2

어떤 수 $c$가 $a,b$의 공배수라고 하자. $c$는 배수이기 때문에 다음의 식을 얻을 수 있다.

• $c = as$
• $c = bt$

GCD Theorem 3에 의하여 $as = a_0ds, \ bt = b_0 dt$로 표현할 수 있고, $a_0 x + b_0 y=1$를 만족한다.
위 선형조합식의 양변에 $c$를 곱한뒤 위의 표현을 대입하면 $c$가 $a_0b_d$의 배수임을 보일 수 있다.$\Box$
$$ \begin{align}a_0cx+b_0cy&=c\a_0btx+b_0asy&=c\ a_0b_0dtx + b_0a_0dsy &= c \ a_0b_0d(tx+sy) &= c\end{align} $$

proof about relation 3

relation1, relation2가 모두 성립하므로 단순 대입만으로 증명할 수 있다.$\Box$
$$ a_0b_0d \times d = a_0d \times b_0d = ab$$

 

[^1]: 어떤 수 $a$의 약수 집합은 $G(a)$로 나타내며, $a$, $b$의 공약수 집합은 $G(a,b)$로 나타낸다.
[^2]: 이렇듯 수식을 사용하여 표현할 때는 화살표 왼쪽에 있는 내용의 "Definition"으로부터 오른쪽을 도출해낸다.
[^3]: 공약수에 대한 정의였던 GCD는 divide 표현에서 "나누는 수"인 왼쪽에 위치했지만, LCM은 공배수에 대한 정의이기 때문에 "나눠지는 수"안 오른쪽에 위치한다.