1.2. 최대공약수(greatest common divisor)

aaa

정의. 최대공약수(greatest common divisor)

두 정수 $a,\,b \in \Z$에 대하여, 다음 세 조건을 모두 만족하는 유일한 정수 $d \in \Z$가 존재한다.

  1. $d \mid a$이고 $d \mid b$.
  2. 만약 또 다른 정수 $c \in \Z$가 존재하여 $c \mid a$이고 $c \mid b$이면, $c \mid d$.
  3. $d \geq 0$.

이러한 조건을 만족하는 정수 $d$를 $a$와 $b$의 최대공약수(greatest common divisor)라 부르고 $\gcd(a,\,b)$로 나타낸다.

  예제. 두 정수 $-4$와 $8$의 최대공약수를 구해보자. 조건 (c)에 의해서 $-4$와 $8$의 음이 아닌 약수들만 고려해도 충분하다. $-4$의 음이 아닌 약수들은 $1,\,2,\,4$이고, $8$의 음이 아닌 약수들은 $1,\,2,\,4,\,8$이므로, 조건 (a)를 만족하는 $-4$와 $8$의 공약수(common divisor)들은 $2$와 $4$가 있다. 여기서 $2 \mid 4$이므로 조건 (b)에 의해 $\gcd(-4,\,8) = 4$임을 알 수 있다.

  예제. 임의의 정수 $n \in \Z$에 대하여, $\gcd(0,n) = \abs{n}$이다. 특히, $\gcd(0,\,0) = 0$이 성립한다. '최대'공약수라는 단어의 의미를 공약수 중 가장 큰 정수 오해하여 $\gcd(0,\,0) = \infty$이거나 존재하지 않을 것이라 생각하기 쉽지만 이는 오해이다. 여기서의 '최대'공약수의 의미는 공약수 중 다른 모든 공약수들을 약수로 갖는 수를 말한다.

  다음 설명할 정리는 두 정수 $a$와 $b$의 최대공약수를 언제나 $a$와 $b$의 선형결합으로 나타낼 수 있음을 보여준다.

 

정리.

두 정수 $a,\,b \in \Z$에 대하여, $d = \gcd(a,\,b)$라 하자. 그러면 $ax + by = d$를 만족하는 두 정수 $x,\,y \in \Z$가 언제나 존재한다.

  증명.

 

최대공약수의 성질

두 정수 $a,\,b \in \Z$에 대하여, $\gcd(a,\,b) = 1$인 경우, $a$와 $b$가 서로소(coprime, relatively prime)라 한다. $a,\, b$가 서로소인 경우, 위 정리에 의해 적당한 정수 $x,\,y \in \Z$를 이용하여 $ax + by = 1$로 나타낼 수 있음을 알 수 있다.

 

정리.

세 정수 $a,\,b,\,c \in \Z$에 대하여, 다음이 성립한다.

  1. $\gcd(a,\,b) = \gcd(b,\,a) = \gcd(\abs{a},\, \abs{b})$.
  2. 임의의 정수 $k \in \Z$에 대하여, $\gcd(ka,\,kb) = \abs{k} \gcd(a,\,b)$.
  3. 임의의 정수 $k \in \Z$에 대하여, $\gcd(a,\,b) = \gcd(a,\,b+ka)$.
  4. $\gcd(a,\,c) = \gcd(b,\,c) = 1$이면, $\gcd(ab,\,c) = 1$.
  5. $a \mid c$, $b \mid c$, $\gcd(a,\,b) = 1$이면, $ab \mid c$.
  6. $a \mid bc$, $\gcd(a,\,b) = 1$이면, $a \mid c$.

 

최소공배수(least common multiple)
2.1
위로
2.3