최대공약수로 최소공배수 구하기

최소공배수를 구해보자

우선 최대공약수를 구해야 한다.

A, B에 대한 최대공약수는 A, B를 공약수로 나누면 얻을 수 있다.

 

A를 4, B를 12라고 가정하고 최대공약수를 구해보자.

 

2 ) 4 12

2 ) 2  6

 ------------

     1   3

 

이렇게 공통의 약수로 나눠서 더 이상 나눠지지 않을 때까지 나눠주면 된다.

이때 나눈 공약수를 모두 곱하면 이게 바로 최대공약수이다.

 

2 * 2 = 4

최대공약수는 4

 

그리고 더 이상 나눠지지 않는 나머지 수들까지 모두 곱하면 최소공배수를 구할 수 있다.

4 * 1 * 3 = 12

최소공배수는 12

 

최대 공약수는 G로 표시하고 최소 공배수는 보통 L로 표현한다.

• 최대공약수(Greatest Common Diviosr)
• 최소공배수(Least Common Multiple)

더 이상 나눠지지 않은 나머지 수들은 소문자 a, b로 표현해 보자.

 

원래 수 : A, B

최대공약수로 나눈 수 : a, b

최대공약수 : G

최소공배수 : L

 

L은 G * a * b로 나타낼 수 있다.

L = G * a * b

 

원래 수 A, B로 최소공배수를 구하고 싶으면 양변에 G를 곱해보자.

 

G * L = G * a * b * G

G * L = G * a * G * b (교환 법칙으로 위치 바꾸자. a는 A를 G로 나눈 값이기 때문에 G * a = A와 같다.)

G * L = A * B

L = A * B / G

 

이제 A, B, G로 최소공배수를 구할 수 있다.

정리하자면

• G * L = A * B
• L = A * B / G
• A = G * a, B = G * b

 

12와 18의 최소공배수를 구해보자.

 

2 ) 12 18

3 )  6   9

 ------------

     2   3

 

G = 6

L = 12 * 18 / 6 = 36

 

최소공배수는 36이다.

 

함께 읽으면 좋은 글

최대공약수와 유클리드 호제법

약수와 배수