수론 에서, 정수 들의 공약수 (公約數, 영어 : common factor )는 동시에 그들 모두의 약수 인 정수다. 적어도 하나가 0이 아닌 정수들의 최대공약수 (最大公約數, 문화어 :영어 : greatest common factor , 약자 GCF)는 공약수 가운데 가장 큰 하나다. 다항식 이나 환 의 원소에 대해서도 정의할 수 있다.
두 정수
n
,
m
∈
Z
{\displaystyle n,m\in \mathbb {Z} }
공약수 는
n
{\displaystyle n}
m
{\displaystyle m}
n
,
m
∈
Z
{\displaystyle n,m\in \mathbb {Z} }
최대공약수 는 다음과 같은 여러 정의가 있으며, 이들은 서로 동치 이다.
n
{\displaystyle n}
m
{\displaystyle m}
n
{\displaystyle n}
m
{\displaystyle m}
n
{\displaystyle n}
m
{\displaystyle m}
배수 인 양의 정수
n
{\displaystyle n}
m
{\displaystyle m}
모두 0이지는 않은 두 정수의 최대공약수는 항상 존재하며, 항상 유일하다. 기호는
gcd
{
n
,
m
}
{\displaystyle \gcd\{n,m\}}
(
n
,
m
)
{\displaystyle (n,m)}
비슷하게, 여러 정수
n
1
,
n
2
,
…
,
n
k
∈
Z
{\displaystyle n_{1},n_{2},\dots ,n_{k}\in \mathbb {Z} }
공약수 는 공통 약수이며, 모두 0이지는 않은 여러 정수
n
1
,
n
2
,
…
,
n
k
∈
Z
{\displaystyle n_{1},n_{2},\dots ,n_{k}\in \mathbb {Z} }
최대공약수
gcd
{
n
1
,
n
2
,
…
,
n
k
}
{\displaystyle \gcd\{n_{1},n_{2},\dots ,n_{k}\}}
동치 인 정의가 있다. 이는 항상 유일하게 존재한다.
가장 큰 공약수
공약수이자, 모든 공약수의 배수인 양의 정수
정수 계수 선형 결합인 최소 양의 정수
(재귀적 정의)
gcd
{
gcd
{
gcd
{
⋯
gcd
{
gcd
{
n
1
,
n
2
}
,
n
3
}
⋯
}
,
n
k
−
1
}
n
k
}
{\displaystyle \gcd\{\gcd\{\gcd\{\cdots \gcd\{\gcd\{n_{1},n_{2}\},n_{3}\}\cdots \},n_{k-1}\}n_{k}\}}
최대공약수가 1인 정수들을 서로소
최대공약수는 다음과 같은 성질들을 가진다. (여기서 최대공약수를 취하는 정수들은 적어도 하나가 0이 아니라고 가정한다.)
약수 관계는 최대공약수를 통해 다음과 같이 나타낼 수 있다.
n
∣
m
⟺
gcd
{
n
,
m
}
=
n
{\displaystyle n\mid m\iff \gcd\{n,m\}=n}
공약수는 최대공약수의 약수 와 동치 이다.
k
∣
n
,
m
⟺
k
∣
gcd
{
n
,
m
}
{\displaystyle k\mid n,m\iff k\mid \gcd\{n,m\}}
k
∣
n
1
,
n
2
,
…
,
n
t
⟺
k
∣
gcd
{
n
1
,
n
2
,
…
,
n
t
}
{\displaystyle k\mid n_{1},n_{2},\dots ,n_{t}\iff k\mid \gcd\{n_{1},n_{2},\dots ,n_{t}\}}
최대공약수는 정수 계수 선형 결합으로 나타낼 수 있는 최소 양의 정수이다.
gcd
{
n
,
m
}
=
min
{
a
n
+
b
m
>
0
:
a
,
b
∈
Z
}
{\displaystyle \gcd\{n,m\}=\min\{an+bm>0\colon a,b\in \mathbb {Z} \}}
gcd
{
n
1
,
n
2
,
…
,
n
t
}
=
min
{
a
1
n
1
+
a
2
n
2
+
⋯
+
a
t
n
t
>
0
:
a
1
,
a
2
,
…
,
a
t
∈
Z
}
{\displaystyle \gcd\{n_{1},n_{2},\dots ,n_{t}\}=\min\{a_{1}n_{1}+a_{2}n_{2}+\cdots +a_{t}n_{t}>0\colon a_{1},a_{2},\dots ,a_{t}\in \mathbb {Z} \}}
최대공약수는 음이 아닌 정수
k
{\displaystyle k}
gcd
{
n
k
,
m
k
}
=
gcd
{
n
,
m
}
k
{\displaystyle \gcd\{nk,mk\}=\gcd\{n,m\}k}
gcd
{
n
1
k
,
n
2
k
,
…
,
n
t
k
}
=
gcd
{
n
1
,
n
2
,
…
,
n
k
}
k
{\displaystyle \gcd\{n_{1}k,n_{2}k,\dots ,n_{t}k\}=\gcd\{n_{1},n_{2},\dots ,n_{k}\}k}
gcd
{
n
k
,
m
k
}
=
gcd
{
n
,
m
}
k
(
k
∣
n
,
m
)
{\displaystyle \gcd \left\{{\frac {n}{k}},{\frac {m}{k}}\right\}={\frac {\gcd\{n,m\}}{k}}\qquad (k\mid n,m)}
gcd
{
n
1
k
,
n
2
k
,
…
,
n
t
k
}
=
gcd
{
n
1
,
n
2
,
…
,
n
t
}
k
(
k
∣
n
1
,
n
2
,
…
,
n
t
)
{\displaystyle \gcd \left\{{\frac {n_{1}}{k}},{\frac {n_{2}}{k}},\dots ,{\frac {n_{t}}{k}}\right\}={\frac {\gcd\{n_{1},n_{2},\dots ,n_{t}\}}{k}}\qquad (k\mid n_{1},n_{2},\dots ,n_{t})}
특히, 정수들을 최대공약수로 나눈 몫들은 서로소 다.
gcd
{
n
gcd
{
n
,
m
}
,
m
gcd
{
n
,
m
}
}
=
1
{\displaystyle \gcd \left\{{\frac {n}{\gcd\{n,m\}}},{\frac {m}{\gcd\{n,m\}}}\right\}=1}
gcd
{
n
1
gcd
{
n
1
,
n
2
,
…
,
n
t
}
,
n
2
gcd
{
n
1
,
n
2
,
…
,
n
t
}
,
…
,
n
t
gcd
{
n
1
,
n
2
,
…
,
n
t
}
}
=
1
{\displaystyle \gcd \left\{{\frac {n_{1}}{\gcd\{n_{1},n_{2},\dots ,n_{t}\}}},{\frac {n_{2}}{\gcd\{n_{1},n_{2},\dots ,n_{t}\}}},\dots ,{\frac {n_{t}}{\gcd\{n_{1},n_{2},\dots ,n_{t}\}}}\right\}=1}
정수들 가운데 하나에서 다른 하나와 서로소인 약수를 지워도 최대공약수가 변하지 않는다.
gcd
{
m
,
k
}
=
1
⟹
gcd
{
n
m
,
k
}
=
gcd
{
n
,
k
}
{\displaystyle \gcd\{m,k\}=1\implies \gcd\{nm,k\}=\gcd\{n,k\}}
gcd
{
m
,
k
}
=
1
⟹
gcd
{
n
1
,
…
,
n
j
m
,
…
,
n
t
,
k
}
=
gcd
{
n
1
,
…
,
n
t
,
k
}
{\displaystyle \gcd\{m,k\}=1\implies \gcd\{n_{1},\dots ,n_{j}m,\dots ,n_{t},k\}=\gcd\{n_{1},\dots ,n_{t},k\}}
소인수분해 가 주어진 정수들의 최대공약수는 공통된 소인수의 최소 지수 거듭제곱의 곱이다. 두 정수의 경우 소인수분해가 다음과 같다고 하자.
n
=
p
1
e
1
p
2
e
2
⋯
p
t
e
t
{\displaystyle n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{t}^{e_{t}}}
m
=
p
1
f
1
p
2
f
2
⋯
p
t
f
t
{\displaystyle m=p_{1}^{f_{1}}p_{2}^{f_{2}}\cdots p_{t}^{f_{t}}}
e
1
,
e
2
,
…
,
e
t
,
f
1
,
f
2
,
…
,
f
t
∈
Z
≥
0
{\displaystyle e_{1},e_{2},\dots ,e_{t},f_{1},f_{2},\dots ,f_{t}\in \mathbb {Z} _{\geq 0}}
그렇다면, 최대공약수는 다음과 같다.
gcd
{
n
,
m
}
=
p
1
min
{
e
1
,
f
1
}
p
2
min
{
e
2
,
f
2
}
⋯
p
t
min
{
e
t
,
f
t
}
{\displaystyle \gcd\{n,m\}=p_{1}^{\min\{e_{1},f_{1}\}}p_{2}^{\min\{e_{2},f_{2}\}}\cdots p_{t}^{\min\{e_{t},f_{t}\}}}
두 정수의 최대공약수와 최소공배수 의 관계는 다음과 같다.
gcd
{
n
,
m
}
lcm
{
n
,
m
}
=
n
m
{\displaystyle \gcd\{n,m\}\operatorname {lcm} \{n,m\}=nm}
최대공약수는 각 정수의 약수를 구하고, 공통되는 약수를 구하고, 가장 큰 하나를 구하면 얻을 수 있다. 예를 들어 12와 18의 경우, 12의 모든 약수는 (±) 1, 2, 3, 4, 6, 12이며, 18의 모든 약수는 (±) 1, 2, 3, 6, 9, 18이므로, 공약수는 (±) 1, 2, 3, 6이다. 가장 큰 6이 바로 최대공약수이다. 최대공약수를 구하는 방법은 그 밖에 소인수분해 를 통한 방법과 유클리드 호제법 을 통한 방법이 있다.
두 수 192와 72의 최대공약수를 소인수 분해를 이용하여 구하여 보자. 일단 두 수를 소인수 분해한다.
192
=
2
6
×
3
=
2
×
2
×
2
×
2
×
2
×
2
×
3
{\displaystyle 192=2^{6}\times 3=2\times 2\times 2\times 2\times 2\times 2\times 3}
72
=
2
3
×
3
2
=
2
×
2
×
2
×
3
×
3
{\displaystyle 72=2^{3}\times 3^{2}=2\times 2\times 2\times 3\times 3}
구하고 나면, 두 소인수 분해 결과의 중복되는 부분을 찾아 서로 곱한다. 두 결과에서 2가 세 번 중복되어 나오고 3이 한번 중복되어 나왔다. 즉
2
×
2
×
2
×
3
=
24
{\displaystyle 2\times 2\times 2\times 3=24}
그러나 일반적으로 소인수 분해를 효율적으로 빠른 시간 내에 하는 방법은 알려져 있지 않다. 더 빠른 시간 안에 구하는 방법에는 호제법이 있다.
똑같이 두 수 192와 72의 최대공약수를 이번에는 호제법으로 구하여 보자. 일단 192을 72로 나누어 나머지를 구한다.
192
=
72
×
2
+
48
{\displaystyle 192=72\times 2+48}
이는 192을 72로 나누어 나온 나머지가 48라는 것을 의미한다. 이번에는 72을 나머지인 48로 나눈다.
72
=
48
×
1
+
24
{\displaystyle 72=48\times 1+24}
이와 같은 연산을 나머지가 0이 될 때까지 반복한다.
48
=
24
×
2
+
0
{\displaystyle 48=24\times 2+0}
나머지가 0이 되었으므로 연산을 중지한다. 이때, 나머지가 0이 되기 바로 직전의 연산에서의 나머지가 원래 두 수의 최대공약수가 된다.
이를 수식화 한 것은 호제법 문서를 참조하라.
이 부분의 본문은 소인수분해입니다.
