공약수(Common Divisor)
둘 이상의 수에서 공통의 약수.
즉, 각 수를 모두 나누어 떨어뜨리는 정수를 공약수라고 한다.
최대공약수(Greatest Common Divisor)
공약수 중 가장 큰 수
[예시1] 12와 20의 공약수와 최대공약수
12의 약수 → 1, 2, 3, 4, 6, 12
20의 약수 → 1, 2, 4, 5, 10, 20
둘의 공약수 → 1, 2, 4
둘의 최대공약수 → 4
※ 소인수분해로 공약수 및 최대공약수 구하기
- 소인수분해하여 나온 공통의 소인수 중 지수가 낮은 값들을 곱한다
[예시2] 12와 20의 공약수와 최대공약수
12의 소인수분해 → 2^2 * 3
20의 소인수분해 → 2^2 * 5
→ 공통되는 소인수: 2
→ 지수가 낮은 값: 2^2
→ 최대공약수: 4 (= 2^2)
→ 공약수: 1, 2, 4 (4의 약수)
[예시3] 12와 18의 공약수와 최대공약수
12의 소인수분해 → 2^2 * 3
18의 소인수분해 → 2 * 3^2
→ 공통되는 소인수: 2, 3
→ 지수가 낮은 값: 2^1, 3^1
→ 최대공약수: 6 (= 2 * 3)
→ 공약수: 1, 2, 3, 6 (6의 약수)
※ 나눗셈으로 공약수 및 최대공약수 구하기
[예시4] 12와 20의 공약수와 최대공약수
12, 20
→ 2로 나누면 6, 10
→ 다시 2로 나누면 3, 5
→ 더 이상 나눌 수 없음, 그동안 나눴던 수를 서로 곱하면 2 * 2 = 4
→ 최대공약수: 4 (= 2 * 2)
→ 공약수: 1, 2, 4 (4의 약수)
[예시5] 12와 18의 공약수와 최대공약수
12, 18
→ 2로 나누기: 6, 9
→ 3으로 나누기: 2, 3
→ 더 이상 나눌 수 없음, 그동안 나눴던 수를 서로 곱하면 2 * 3 = 6
→ 최대공약수: 6 (= 2 * 3)
→ 공약수: 1, 2, 3, 6 (6의 약수)
[예시6] 12, 54, 72의 공약수와 최대공약수
12, 54, 72
→ 2로 나누기: 6, 27, 36
→ 3으로 나누기: 2, 9, 12
→ 더 이상 나눌 수 없음, 그동안 나눈 수를 곱하면 2 * 3 =6
→ 최대공약수: 6 (= 2 * 3)
→ 공약수: 1, 2, 3, 6 (6의 약수)
[문제1]
셔츠 112장, 바지 80장, 재킷 32장을 사람들이 나누어 가지려고 한다.
동일한 개수만큼 남김없이 나누어 가지려면 최대 몇 명까지 나눌 수 있는지 구하라.
또한, 한 명당 받을 수 있는 셔츠, 바지, 재킷의 각각의 개수를 구하라.
[풀이1-1]
* 112, 80, 32의 최대공약수 = 최대 인원
→ 2로 나누기: 56, 40, 16
→ 2로 나누기: 28, 20, 8
→ 2로 나누기: 14, 10, 4
→ 2로 나누기: 7, 5, 2
→ 더 이상 나눌 수 없음, 그동안 나눈 수를 곱하면 2^4 = 16
→ 나누고 남은 수 7, 5, 2
→ 나눠 가질 최대 인원: 16명
→ 한 명당 받을 수 있는 각각의 개수: 셔츠 7, 바지 5, 재킷 2
[풀이1-2]
* 112, 80, 32의 최대공약수 = 최대 인원
112의 소인수분해 → 2^4 * 7
80의 소인수분해 → 2^4 * 5
32의 소인수분해 → 2^5 = 2^4 * 2
→ 공통되는 소인수: 2
→ 지수가 낮은 값: 2^4
→ 최대공약수: 16 (= 2^4)
→ 각각의 남은 소인수 7, 5, 2
→ 나눠 가질 최대 인원: 16명
→ 한 명당 받을 수 있는 각각의 개수: 셔츠 7, 바지 5, 재킷 2
댓글