최대공약수와 서로소

최대공약수와 서로소

정의 1

  1. 두 정수 $n$ 과 $m \ne 0$ 에 대해 다음을 만족하는 정수 $k$ 가 존재하면 $n$ 을 $m$ 이 나눈다고 한다. $$ n = mk $$ 이 때 $n$ 을 $m$ 의 배수Multiple, $m$ 을 $n$ 의 약수Divisor라 하며 다음과 같이 표기한다. $$ m \mid n $$ $m$ 이 $n$ 을 나눌 수 없으면 삭선을 그어 $m \nmid n$ 로 나타낸다.
  2. $0$ 이 아닌 두 정수 $a$, $b$ 가 주어져 있다고 하자. 둘 모두를 나누는 약수 중 가장 큰 수를 $a$ 와 $b$ 의 최대공약수Greatest Common Divisor라 하며, $\gcd (a,b)$ 와 같이 표기한다.
  3. 만약 $\gcd (a,b) = 1$ 이면 $a$ 와 $b$ 가 서로 소Relatively Prime라고 한다.

설명

최대공약수와 서로소라는 개념은 대부분 초등학생 시절부터 보아왔을 개념이다.

서로 소의 영문 표현인 Relatively Prime을 보면 알수있듯, 사실 많은 사람들의 언어습관과 달리(심지어 이 포스트의 제목에서도 띄어쓰기 없이 서로소라 쓰고 있다) 서로소는 서로RelativelyPrime하다는 말이다. 영어에서 ‘서로’를 표현하는 더 적합한 단어는 상호적인(Mutually)겠지만, 수학 전반에서 Mutually는 나름의 중요한 의미가 있어 상대적인(Relatively)이 쓰인다. 이때 상대적이라는 것은 두 수 $a$, $b$ 는 $1$ 이외의 약수를 공유하지 않으므로 서로에게 있어서 사실상 소수나 마찬가지라는 뜻이다. 절대적으로는 소수가 아닐 수 있지만, 서로에게 있어서만은 소수처럼 취급할 수 있다는 정도로 받아들이면 된다.


  1. Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition): p30. ↩︎

댓글