목차

1. 최대공약수, Greatest Common Divisor : GCD

2. 최대공약수 구하는 법 - 소인수 분해로 구하기

3. 최대공약수 구하는 법 - 유클리드 호제법

4. 유클리드 호제법 증명

1. 최대공약수, Greatest Common Divisor : GCD

최대공약수는 두 개의 수 A, B의 약수들 중 공통된 숫자 중 최대 수를 가르키는 것입니다.

숫자가 많아져도 역시 최대공약수는 존재합니다.

현대사회에 들어서면서 컴퓨터를 통해 언어로 표현조차 안되는 양의 숫자들의 연산이 가능해지면서,

각 숫자들의 관계를 파악해주는 공약수가 매우 중요한 팩터가 되었습니다.

2. 최대공약수 구하는 법 - 소인수 분해로 구하기

소인수 분해를 한 후에 공통적인 숫자만 골라내면 됩니다.

(예시 - 24, 60, 84의 최대공약수 구하기)

24 = 2 × 2 × 2 × 3

60 = 2 × 2 × 3 × 5

84 = 2 × 2 × 3 × 7

이 숫자들은 모두 2를 두 개, 3을 하나 포함하고 있습니다.

최대공약수는 12 = 2 × 2 × 3이 됩니다.

작은 수들의 연속일 때는 이 것도 좋은 방법이죠.

하지만 큰 수 일 때는 더 좋은 방법이 있습니다.

3. 최대공약수 구하는 법 - 유클리드 호제법

고대 그리스의 수착자인 유클리드는 기학학 원론(유클리드 원론)으로 유명합니다.

총 13개권으로 정리된 이 책은 100% 유클리드에 머리속에서 나온 것은 아니고, 정리본에 가깝습니다.

하지만 기하학과 정수론의 시초로 알려진 책으로 공리를 제안하고 있다는 데서 수학의 시초라 불립니다.

이 원론에 내용 중의 호제법은 인류 최초의 알고리즘으로 최대 공약수를 구하는 법이 기록되어 있습니다.
두 정수 A, B의 최대공약수를 GCD(A, B)라고 하자.
정수 A, B, q r (b ≠ 0)에 대하여 A = Bq + r이면 GCD(A, B) = GCD(B, r)가 성립한다.
- 네이버 지식백과 -

그러니까 A, B의 관계를 A = Bq + r로 나타내면 A, B와 B, r의 최대공약수는 같다는 말입니다.

예시를 보시면 알 수 있습니다.

예를 들어 2,056,512와 123,456의 최대공약수를 구해 보겠습니다.

이 정도 수의 약수를 구하라고 하면 손으로 계산하는 경우는 포기하기 딱 좋은 큰 수입니다.

호제법은 여러번 반복해야 합니다.

마지막은 나머지가 없습니다. 바로 이 때 192가 바로 최대공약수입니다.

처음에는 접근이 어렵다고 생각한 큰 수도 7번 반복하면 구해지네요.

손으로 하려면 번거롭기는 합니만 구할 수 있는 방법이 있는 것 자체가 좋은 일일 겁니다.

그래도 역시 프로그램으로 알고리즘을 짜두는게 편리하겠죠.

큰 수도 몇번만 연산하면 계산할 수 있으니 컴퓨터의 연산속도로는 상상도 못 하는 단위도 처리할 수 있습니다.

4. 유클리드 호제법 증명

호제법의 증명을 잠시 소개합니다.

이렇게 정리를 했으면 아래 식부터 시작해서 증명하겠습니다.

따라서 G역시 r의 약수입니다.

또한 G'은 최대공약수임으로 G는 G'의 약수입니다.

여기까지 G는 B와 r, G'의 약수가 됩니다.

여기서 m은 b의 약수을 알 수 있습니다.
지금까지 알아낸 바로,

이로서 m은 a와 b의 공약수임을 알았습니다.

a, b는 서로소임으로 공약수는 1뿐입니다. 

m=1이고, G'=mG=G 고로 G=G'입니다.

최소 공배수 부분에서 설명드리겠지만, 최대공약수가 있으면 최소 공배수도 구할 수 있습니다.

이 공약수 공배수는 알고리즘이 완성되어 대부분의 수학툴에서 사용할 수 있습니다.

자연수란 말 그대로 수를 세는데 사용합니다.

가감의 개념이 들어가면 정수에 개념이 됩니다.

1. 약수

어떤 수 A를 나누었을 때 나머지 없이 나누어 떨어지는 수 B들이 있을때 B는 A의 약수라고 합니다.

예를 들어 72의 약수는 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72가 됩니다.

나눈다는 개념과 좀 다른것 같지만 1로는 모든 수가 나누어지고 자기자신 역시 나누어집니다.

1과 자신 말고는 약수를 가지지 않는 수를 소수라고 합니다.

2. 배수

배수는 어떤 수 A에 자연수를 곱하면 생기는 수입니다.

7의 배수는 14, 21, 28, 35 ...로 약수와는 달리 그 수가 무한대입니다.

A의 배수 A2, A3, A4 ... 가 있다면, A는 모든 배수 A2, 3, 4들의 약수입니다.

3. 공약수와 공배수

공약수는 어떤 수 A, B가 있을때 두 수의 약수중 같은 것 들을 말합니다.

72와 48의 경우 2, 3, 4, 6, 8, 12, 24가 공약수가 됩니다.

1을 제외하고 공약수가 전혀 없는 관계를 서로소라고 부릅니다.

공배수는 두수를 곱해서 나오는 겹치는 수를 말합니다.

예를 들어 4와 6의 공배수는 12, 24, 36 ...이 됩니다.

4. 공약수와 공배수가 사용되는 경우

공약수와 공배수는 수학개념적으로 원론적인 축에 들어가는 개념입니다.

정수론에서는 툭하면 배수와 약수를 통한 해석을 펼칩니다.

특히 약수 → 약수가 없는 수, 소수하면 암호화 / 코드화의 핵심이라는게 유명합니다.

그러다 보니 약수/배수 이야기가 먼 세상 같지만 이 개념들은 사실 일상에서 가까운 이야기입니다.

정확하게는 가까운것을 이용해서 학문을 펼친다고 봐야 합니다.

• 공약수는 자원의 활용에서 사용됩니다.
  - 급식을 학교 3개에 720명, 800명, 1000명에게 공급할 때 약수는 2, 4, 5, 8, 10, 20, 40, 80이 있습니다.
  만일 생산지에서 80(최대공약수)개 들이 포장을 하면 효율적으로 공급할 수 있지요.
  - 고객사 A회사는 레일이 24 m 단위 B회사는 32 m 단위로 그때 그때 필요한만큼 사간다고 칩시다.
  그렇다면 6m 단위로 짤라두면 어느 회사에서 요구하든 편리하게 대응할 수 있을 껍니다.
  
  
• 공배수는 생산의 단위로 이용됩니다.
  - 한 틀에서 고무 타이어는 48개, 휠은 120개 생산 될 때 타이어는 240개 단위로 생산하는게 비용이 가장 절약 됩니다.
  (사실은 더 복잡하죠.)
• 물류에서 계란은 12개 빵은 30쌍으로 묶어서 팝니다. 토스트는 60개 단위로 최대 이윤이 남겠습니다.
  61개를 만들면 오히려 손해볼 수도 있다는 것이죠.

실재 이런 개념을 매우자주 자연스럽게 이용합니다.

특히 공배수는 장사를 한다면 자연스럽게 사용하는 개념이니 기억해 두어야 합니다.