서로소 뜻, 소인수분해 이용하여 최대공약수 구하는 방법

둘 이상의 자연수의 공통인 약수를 공약수라고 하며, 최대공약수는 공약수 중에서 가장 큰 수입니다.

 

그렇다면 두 수의 공약수가 1뿐인 경우 당연히 두 수의 최대공약수는 1이 되겠죠?

이와 같이 두 수의 공약수가 1뿐일 때(두 수의 최대공약수가 1일 때) 두 자연수를 서로소라고 합니다.

예를 들어 3과 4에 대하여 3의 약수는 1, 3이고 4의 약수는 1, 2, 4이므로 공약수가 1뿐이므로 3과 4는 서로소이며,

8과 9에 대하여 8의 약수는 1, 2, 4, 8이고 9의 약수는 1, 3, 9이므로 공약수가 1뿐이므로 8과 9는 서로소입니다.

6과 14에 대해서는 6의 약수는 1, 2, 3, 6이고 14의 약수는 1, 2, 7, 14이므로 공약수는 1, 2입니다.

즉 1을 제외한 공약수가 존재하기 때문에(최대공약수가 1이 아니기 때문에) 6과 14는 서로소가 아닙니다.

초등학교 때 최대공약수를 구하는 방법에 대해서 배웠습니다.

 

예를 들어 40과 100의 최대공약수를 구할 때,

최대공약수의 개념에 따라 40의 약수( 1, 2, 4, 5, 8, 10, 20, 40 )와 100의 약수( 1, 2, 4, 5, 10, 20, 25, 50, 100 )를 나열한 후,

40과 100의 공약수( 1, 2, 4, 5, 10, 20 )를 찾은 다음 공약수 중에 가장 큰 수인 20을 찾을 수도 있고,

 

두 수의 공약수로 나누는 방법을 이용하여 몫의 공약수가 1뿐일 때까지 반복적인 나눗셈 과정을 통하여 을 구할 수 있습니다.

 

 

 

이제 최대공약수를 구하는 다른 방법을 알아보도록 해요.

 

  소인수분해를 이용하여 최대공약수 구하기

 

소인수분해를 이용하여 최대공약수를 구하는 방법은

두 수를 각각 소인수분해하여 거듭제곱으로 나타낸 후,

공통인 소인수의 거듭제곱에서 지수가 같으면 그대로, 지수가 다르면 지수가 작은 것을 택하여 모두 곱하는 것입니다.

 

예 1) 84와 196의 최대공약수는?

 

① 각각의 수를 소인수분해하기.

소인수분해는 곱셈, 나눗셈, 가지치기(수형도) 방법 중에 자신이 편한 것을 택해서 하면 됩니다.

[이전 글 보기] - 거듭제곱, 소인수분해 방법, 약수와 약수의 개수 구하기

이므로 84를 소인수분해하면 이고,

 

이므로 196을 소인수분해하면입니다.

 

② 소인수분해한 결과는 공통인 소인수는 같은 줄에 맞추고, 공통인 소인수가 없는 경우는 빈 공간으로 놔두기.

 

③ 공통인 소인수의 거듭제곱에서 지수가 같으면 그대로, 지수가 다르면 작은 것을 택하기.

예 2) 40과 100의 최대공약수는?

 

① 각각의 수를 소인수분해하기.

40=4×10

   =2×2×2×5

이므로 40을 소인수분해하면이고,

 

100=10×10

     =2×5×2×5

이므로 100을 소인수분해하면 입니다.

② 소인수분해한 결과는 공통인 소인수는 같은 줄에 맞추고, 공통인 소인수가 없는 경우는 빈 공간으로 놔두기.

③ 공통인 소인수의 거듭제곱에서 지수가 같으면 그대로, 지수가 다르면 작은 것을 택하기.

 

생각해보면, 최대공약수는 공약수 중에 가장 큰 수이므로 두 수를 소인수분해한 결과에서도 이를 적용해야겠죠?

공약수이니까 공통인 소인수는 당연히 포함해야 할 것이고, 공약수 중에 가장 큰 수를 찾으려면 공통인 수를 최대한으로 뽑아내야해요.

위의 40과 100에서 공통인 수는 2가 두 개, 5가 한 개 있으므로 최대공약수는이라고 할 수 있는거죠.

그러므로 지수를 비교해서 지수가 같을 때는 그대로, 지수가 다를 때는 지수가 작은 것을 택해야 합니다.

오개념 체크)

최대공약수의 최대라는 의미때문에 지수가 큰 것을 택해야한다고 착각하는 경우가 있는데,

위의 과 이 공약수가 아닌 것처럼 지수가 큰 것은 공약수가 아닙니다.

마찬가지로 공통이 아닌 소인수의 거듭제곱은 공약수가 아니므로 생각할 필요가 없어요.

즉 위의 예 1)에서 84의 소인수 3은 84와 196의 공약수가 아니므로 택하지 않습니다.