logo

최대공약수와 서로소 📂정수론

최대공약수와 서로소

정의 1

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

설명

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

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

같이보기

대수적인 일반화

유일인수분해정역에서 일반화된다.


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