[정보올림피아드대비]10. 약수,배수,최대공약수,최소공배수를 이용한 문제

1. 약수와 배수

a,b,c 는 자연수 이고 b ≠ 0 , a ÷ b = c , 즉 자연수 a 나누기 b 는 c 이고 나머지는 없다면 a를 b의 배수 라고 하고 b는 a의 약수라고 합니다.

예) 15 ÷ 3 = 5 에서 15는 3의 배수이고 3은 15의 약수입니다.

2. 소수와 합성수

한 수가 1과 그 수 자체를 제외하고 다른 약수가 없을때 그 수를 소수라고 합니다.

한 수가 1과 그 수 자체를 제외하고 다른 약수가 있을때 그 수를 합성수라고 합니다.

※ 단, 1은 소수도 합성수도 아닙니다.

3. 소수와 소인수 분해

만약 한 소수가 어떤 수의 약수이면 이 소수를 어떤 수의 소인수라고 합니다.

어떤 합성수를 소인수들의 곱으로 표시했을 때 이것을 소인수분해라고 합니다.

예) 30을 소인수 분해 하면 2 * 3 * 5 이므로 2,3,5 를 30의 소인수라고 합니다.

예) 12 = 2 * 2 * 3 = 2^2 * 3 이므로 2,3을 12의 소인수라고 합니다.

 

=======================================================

3개의 연속된 자연수의 곱이 210 입니다. 이 세수를 구하시오.

문제풀이)

이러한 것은 소인수 분해를 통해서 세수를 찾을 수 있습니다.

210 = 3 * 7 * 2 * 5 이므로 5 * 6 * 7 로 나타내 볼 수 있습니다.

따라서 세수는 5,6,7 입니다.

두 소수의 합이 40입니다. 이 두 소수의 곱의 최댓값을 구하시오

문제풀이)

40을 두 소수의 합으로 표현하면 3 + 37, 11 + 29,  17 + 23 로 표시할 수 있습니다.

3 * 37 = 111

11 * 29 = 319

17 * 23 = 391

정답은 391

자연수 123456789 는 소수입니까 아니면 합성수입니까?

문제풀이)

123456789 는 3의 배수 판정법 에 의해서 3의 배수인것을 확인 할 수 있습니다.

따라서 이 수는 합성수입니다.

연속된 9개의 자연수 중 소수는 가장 많을때 몇개입니까?

문제풀이)

1부터 9 까지의 소수의 갯수는 4개 입니다.

만약 이 외의 연속된 숫자 중에서 이것보다 더 많은 소수를 가지기 위해서는 짝수(2의 배수이므로)를 모두 걸러내야 합니다. 따라서 홀수의 갯수는 5개만 남습니다. 여기서 3의 배수를 걸러내면 9개의 연속된 수에서는 반드시 3의 배수는 2개 이상이 포함됩니다. 또한 5의 배수도 반드시 1개는 포함됩니다.

따라서 연속된 9개의 숫자 중에서 소수의 갯수가 가장 많은 영역은 1~9 까지이고 갯수는 4개입니다.

5,6,7,14,15를 두 개 조로 나누되 각 조의 곱을 갖게 할 수 있습니까?

문제풀이)

이러한 문제도 소인수 분해를 이용하는 문제이다.

5,2*3,7,2*7,3*5 이므로

2가 2개,3이 두개,5가 2개, 7이 2개 이므로 나눌 수 있습니다.

따랏 2*3*5*7 이 되면 되므로 5,6,7 과 14,15로 나눌 수 있습니다.

4. 공약수와 최대공약수

몇 개의 수들이 모두 같은 약수를 가지고 있으면 이 수들을 공약수라고 합니다. 그 중 가장 큰 수를 이 수들의 최대공약수라고 합니다.

예) 12의 약수는 1,2,3,4,6,12 이고 18의 약수는 1,2,3,6,9,18 입니다. 여기서 12와 18의 공약수는 1,2,3,6 이고 여기서 가장 큰 6이 최대공약수입니다.

5. 공배수와 최소공배수

몇 개의 수들이 모두 같은 배수를 가지고 있으면 이 수들을 공배수 라고 합니다. 그 중 가장 작은 수를 이 수들의 최소공배수라고 합니다.

예)12의 배수는 12,24,36,48,60.... 이고 18의 배수는 18,26,54,.... 입니다. 여기서 12와 18의 공배수는 36,72,... 가 되고 가장 작은 수 36은 최소공배수 입니다.

6. 서로소

만약 두 수의 최대공약수가 1이면 이 두 수를 서로소 라고 합니다.

7. 유클리드호제법

유클리드호제법은 2개의 정수에서 최대공약수를 구하는 방법의 하나입니다.

유클리드 호제법의 정의를 보면 a와 b 두개의 정수가 있다고 하면

a와 b의 최대공약수는 b와 a를 b로 나눈 나머지 r의 최대공약수와 같다는 성질입니다.

 

이것을 증명하는 방법은 다음과 같습니다.

a 와 b 의 두 수가 있고 a를 b로 나눈 나머지 r 이 있다고 하면 어떤수를 q라고 가정하면

a = q * b + r 과 같이 표현을 할 수가 있습니다. 

이때 0 <= r < b 입니다.

 

여기서 a,b 의 두수의 최대공약수 k 가 있다고 하면

a = mk, b = nk 로 나타낼수 있는데요 이때 m과 n은 서로 소입니다.

그러면 다음과 같이 표현할 수 있겠네요. 어떤 수를 q라고 하면

mk = q * nk + r

r = mk - qnk = (m-qn) * k 로 표현 할 수 있습니다.

즉 r은 a와 b의 최대 공약수인 k를 가슴에 품고 있다는 것입니다

즉 (m-qn)을 l 이라고 가정하면 r = l * k 가 되는 것입니다.

여기서 b=nk의 n 과 m-qn 이 서로소인것을 증명하면 됩니다.(a 와 b의 최대공약수는 b와 r의 최대공약수가 같음을 증명하기 때문에)

 

만약에 서로소가 아니라고 가정을 하면

n=xG, m-qn = yG 와 같이 공통인 G(G는 1이 아닌수) 가 있다고 하면

m - qn = m - q*xG = yG

m=yG + qxG =(y+qx)*G 와 같이 나타낼수 있습니다.

n=xG 이므로 m과 n은 공약수 G를 갖게 됩니다.

만약 이러한 G를 갖게 된다면 a와 b의 최대공약수는 k가 아니라 k*G 의 값이 될테니 모순이 됩니다.

 

따라서 a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다.

8. 두수의 곱 = 최대공약수 * 최소공배수

a*b = 최대공약수(a,b) * 최소공배수(a,b) 가 됩니다.

이것을 증명하는 방법은 다음과 같습니다.

여기서 G는 A,B의 최대공약수 가 됩니다.

최소 공배수는 G*a*b 입니다.

A = G*a 이고 B = G*b 인것을 알 수 있습니다.

A * B = G*a * G*b 입니다.

최대공약수 * 최소공배수 = G * G*a*b 입니다.

따라서 두수의 곱은 최대공약수 * 최소공배수와 같습니다.

==========================================================================

3개의 나무토막이 있습니다. 길이는 각각 120cm, 180cm,300cm입니다. 지금 이들을 모두 똑같은 토막으로 자르려고 하는데 나머지는 없어야 합니다. 각 토막은 몇cm여야 합니까? (단 토막의 길이를 최대로 하려고 합니다.)

문제풀이)

이 문제는 최대공약수를 구하는 문제입니다.

120,180,300 의 최대공약수는 60 입니다.

따라서 각 토막의 길이는 60cm

 

기계 부속품 가공을 하는데 모두 3번의 공정을 거칩니다. 첫번째 공정에서는 한 명의 직원이 1개의 부속품을 만들기 위해서는 3시간이 걸리고, 두번째 공정에서는 한명의 직원이 1개의 부속품을 만들기 위해서는 10시간이 걸리고, 세번째 공정에서는 한명의 직원이 1개의 부속품을 만들기 위해서는 5시간이 걸립니다.. 생산이 균형을 이루려면 3번의 공정에는 각각 몇명의 직원을 배정해야 합니까? 최소의 인원을 구하시오.

문제풀이)

이 문제는 최소공배수를 구하는 문제입니다.

3,10,5 의 최소공배수를 구하면 30이 됩니다.

따라서 첫번째 공정에 10명, 두번째 공정에 3명, 세번째 공정에 6명을 투입시키면 됩니다.

유클리드 호제법을 이용하여 4811과 1981의 최대공약수를 구하시오.

문제풀이)

4811 = 2 * 1918 + 849

1918 =  2 * 849 + 283

849 = 3 * 283 이므로 최대공약수는 283 입니다.

두 수의 최대공약수는 4이고 최소공배수는 252 일때 그 중 한 수가 28 이면 다른 한수는 얼마입니까?

문제풀이)

최대공약수 * 최소공배수 = a * b 이므로

28 * x = 4 * 252

x = 36

어떤 두자리 수로 251을 나누면 나머지가 41입니다. 두자리 수는 무엇입니까?

문제풀이)

251 - 41 = 210 은 어떤 두자리 수로 나누어 떨어 집니다.

210을 소인수 분해해 보면 7 * 3 * 2 * 5 가 됩니다.

여기서 두자리수는 41보다 커야 합니다. 따라서 7*3*2 = 42 또는 7*2*5= 70 의 값이 됩니다.

 

[역대기출문제]

https://docs.google.com/forms/d/e/1FAIpQLSf7NWuyiL313rsqFm_1zdsuefQteyC6xz2wFlJ8becEta4Tjw/viewform

11-1. 약수,배수,최대공약수,최소공배수를 이용한 문제(초등부)

https://docs.google.com/forms/u/0/d/e/1FAIpQLSf4cx7X4zw8kZ9OyEXyZtRqqO78edGczwAhtmuZNHrHof6Zdw/viewform

11-2. 약수,배수,최대공약수,최소공배수를 이용한 문제(중고등부)