공배수와 공약수 구하기

공배수: 최소공배수의 배수

공약수: 최대공약수의 약수

 

 

1. 공약수 구하기

 

a와 b의 공약수 개수 = 최대공약수의 약수의 개수

 

예1)

36 48 - 2

18 24 - 2

9 12 - 3

3 4

 

최대 공약수는 2*2*3=12 

36과 48의 공약수는 12, 6, 4, 3, 2, 1

12의 약수는 12, 6, 4, 3, 2, 1

 

예2)

30 45 - 3

10 15 - 5

2 3

 

최대공약수는 3*5=15

30과 45의 공약수는 15, 5, 3, 1

15의 약수는 15, 5, 3, 1

 

두 수의 공약수 구할거라고 힘들게 나열하지 말고 두 수의 최대공약수만 하나 구하면 약수들이 간단하게 나온다.

 

두 수의 공약수를 구하는 다른 방법으로는 위의 예시에서 나온 공약수들을 하나씩 곱해서 도출하는 것이다.

 

예1)에서 최대공약수를 구하기 위해 작성한 식에서 약수가 2, 2, 3이 나왔다. 이 2, 2, 3을 경우의 수 조합 구하듯이 하나씩 구해주는 거다.

 

예를들면, 2, 2, 3으로 나올 수 있는 조합은 (2), (3), (2*2=4), (2*3=6), (2*2*3=12)인데 이 조합이 공약수가 된다.

 

 

 

 

2. 공배수 구하기

 

두 수의 공배수는 최소 공약수의 배수이다.

 

예를 들어, 8과 16의 공배수를 구해보자.

 

위에서 약수 구하듯이 공약수로 나눈다.

 

8 16 - 8

1 2

 

이때 8, 1, 2를 곱하면 최소 공배수가 나온다. 최소공배수는 16이다. 

 

이 16의 배수인 16, 32, 48, 64가 8과 16의 공배수이다.

 

 

 

그리고 두 수가 서로소라면 두 수의 곱이 최소공배수이다.

 

서로소란 두 수의 공약수가 1밖에 없는 수를 말한다.

 

위의 공배수 구하기 식의 1, 2, 8 중 1, 2가 서로소에 해당한다. 공약수 구하기 예시에서는 예1)의 3, 4 예2)의 2, 3이 서로소이다.

 

식을 써보면 이해가 더 쉽다. 서로소의 공배수를 구해보자.

 

3 4 - 1

3 4

공배수: 1*3*4=12

 

11 5 - 1

11 5

공배수: 1*11*5=55

 

두 수와 곱할 공약수가 1밖에 존재하지 않아 서로소의 곱이 공배수가 된다.