[스낵수학] 공약수, 최대공약수, 서로소 개념

소수와 합성수의 개념은

모두 최대공약수와 최소공약수를

구하기 위한 거였다.

 

공약수는 왜 배울까?

 

우리는 일상에서 숫자 하나만을 사용하지 않고

여러 숫자들을 비교하거나 연산하는 등등

수를 계산하게 된다.

이때 좀 더 효율적으로 계산 시간도 단축하고

우리의 머리도 좀 덜 복잡하게

계산할 수 있는 방법이 바로 공약수를 활용하는 것이다.

 

특히 숫자가 엄청나게 크거나

정말 많은 숫자들을 한 번에

계산해야 한다면, 공약수를 활용하는게 큰 도움이 된다.

 

---

공약수(common divisor)란?

 

둘 이상의 자연수의 공통인 약수

(참조) 약수(divisor)는 '어떤 수를 나누어 떨어지게 하는 수' (나머지가 없음)

 

예를 들면 : 5와 10의 공약수는

5의 약수는 1과 5이다.

10의 약수는 1, 2, 5, 10이다.

5와 10의 공통 약수는 1, 5이다.

 

---

최대공약수(Greatest common divisor)란?

공약수 중 최대인 수

 

예를 들면, 5와 10의 최대공약수

5와 10의 공통 약수는 1과 5이고,

이 중에서 가장 큰 수는 5이다.

따라서 최대공약수는 5이다.

[참조] 중학1 수학 교과서

 

만약에 최대공약수가 1인 경우는?

---

서로소(Relatively prime / coprime)이란?

1 이외에 최대공약수를 갖지 않는 자연수(양의 정수)

 

예를 들면, 3과 7의 공약수는?

3의 약수는 1과 3이다.

7의 약수는 1과 7이다.

이 때, 3과 7의 공통약수이자 최대공약수는 1이다.

그런데, 1은 모든 자연수의 약수이다.

따라서 최대공약수가 1인 두 수에 대해

서로소라고 한다.

---

Q. 공약수가 하나도 없는 자연수가 존재할까?

아니다. 1은 모든 수의 자연수다

 

Q. 1의 서로소는?

1은 모든 자연수와 서로소이다.

 

---

공약수를 빠르게 구하는 방법

두 개 이상의 자연수에 대해 최대 공약수의 약수는

두 개 이상의 자연수의 공약수이다. 

 

최대공약수를 빠르게 구하는 방법

소인수분해로 공통인 소인수를 찾는다.

 

 

 

---

[참조] 중학1 수학 교과서