정수의 약수·배수와 최대공약수·최소공배수

개요

• 내용 유형: 강의
• 정수에서 약수와 배수의 정의를 살펴보고, 최대공약수와 최소공배수를 구하는 방법 및 배수 판정법을 다룬다.
• 특히 유클리드 호제법과 이를 이용한 일차 부정방정식 풀이가 핵심이다.

핵심 개념

약수와 배수

• 정수 $A\neq 0$, 정수 $B$에 대해 $B=AQ$를 만족하는 정수 $Q$가 있으면:
  • $A$는 $B$의 약수 또는 인수이다.
  • $B$는 $A$의 배수이다.
• 정수의 범위에서는 음수도 배수가 될 수 있다.
• $0$은 모든 정수의 배수이며, $1$과 $-1$은 모든 정수의 약수이다. 약수 자리에 $0$을 두지 않는 것은 0으로 나누는 상황을 피하기 위해서다.
• $B$가 $A$의 배수일 필요충분조건은 $B$의 배수 전체가 $A$의 배수 전체에 포함되는 것이다.
• 배수 관계의 기본 성질:
  1. $A$는 $A$의 배수이다.
  2. $B$가 $A$의 배수이고 $C$가 $B$의 배수이면, $C$는 $A$의 배수이다.
  3. $B$와 $C$가 모두 $A$의 배수이면, 정수 $m,n$에 대해 $mB+nC$도 $A$의 배수이다. 이를 두 수의 일차결합이라고 한다.

최대공약수

• $A$와 $B$의 최대공약수는 $\gcd(A,B)$로 나타낸다.
• 최대공약수는 입력된 두 정수의 부호를 바꾸어도 변하지 않는다.
• 두 수의 최대공약수가 $1$이면 두 수는 서로소이다.
• $d=\gcd(A,B)$이면 $A/d$와 $B/d$는 서로소이다. 따라서 분자와 분모를 최대공약수로 나누면 기약분수가 된다.

상세 노트

유클리드 호제법

나눗셈 관계가 $A=BQ+R$일 때,

$$\gcd(A,B)=\gcd(B,R)$$

이다. 이 성질을 반복 적용해 나머지가 $0$이 될 때까지 나누면, 마지막 0이 아닌 나머지가 최대공약수다.

예를 들어 $348$과 $243$은 다음과 같이 계산한다.

$$\begin{aligned} 348&=243\cdot1+105\ 243&=105\cdot2+33\ 105&=33\cdot3+6\ 33&=6\cdot5+3\ 6&=3\cdot2+0 \end{aligned}$$

따라서 $\gcd(348,243)=3$이다.

일차 부정방정식

• 유클리드 호제법을 거꾸로 대입하면 $\gcd(A,B)$를 $Ax+By$의 형태로 나타낼 수 있다.
• 예를 들어 $\gcd(20,12)=4$이며,

$$4=20(-1)+12(2)$$

이므로 $20x+12y=4$의 한 정수해는 $x=-1,\ y=2$이다.

최소공배수

• $A,B$의 공배수 가운데 가장 작은 양의 정수를 최소공배수라 하며, $\operatorname{lcm}(A,B)$로 나타낸다.
• 양의 정수 $A,B$에 대해 다음 관계가 성립한다.

$$\gcd(A,B)\operatorname{lcm}(A,B)=AB$$

배수 판정법

• 2의 배수: 일의 자리 숫자가 짝수
• 5의 배수: 일의 자리 숫자가 0 또는 5
• 10의 배수: 일의 자리 숫자가 0
• 4의 배수: 끝의 두 자리 수가 4의 배수
• 8의 배수: 끝의 세 자리 수가 8의 배수
• 3의 배수: 각 자리 숫자의 합이 3의 배수
• 9의 배수: 각 자리 숫자의 합이 9의 배수
• 11의 배수: 홀수 번째 자리 숫자들의 합과 짝수 번째 자리 숫자들의 합의 차가 11의 배수
• 7의 배수: 일의 자리 숫자를 두 배한 뒤 나머지 수에서 빼는 방법 등을 사용할 수 있다. 예를 들어 $469$는 $46-2\cdot9=28$이고, 28이 7의 배수이므로 469도 7의 배수다.
• $P,Q$가 서로소이고 어떤 수 $N$이 $P$와 $Q$ 모두의 배수라면, $N$은 $PQ$의 배수다.