정수론 | 약수와 배수

약수와 배수

$a,d \in Z$이고, $d \neq 0$이라고 가정했을 때, $a=cd$를 만족하는 어떤 정수 $c$가 존재한다면 $d$는 $a$의 약수라 부른다. 그리고 $a$는 $d$의 배수이다. 이 경우 $a$와 $d$의 관계는 $d \mid a$로 표기한다.

참고사항

다음 관계식은 문제 해결에 자주 사용되므로 숙지할 필요가 있다.

1. $2 \mid a(a+1)$

   $a$가 $2k \;(k \in Z)$이면 $a(a+1))=2k(2k+1)$로 성립, $a$가 $2k+1$이면 $(2k+1)(2k+2)$로 성립

2. $3 \mid a(a+1)(a+2)$

   $a$가 $3k,3k+1,3k+2 \; (k \in Z)$이면 $a(a+1)(a+2)=3k(3k+1)(3k+2), (3k+1)(3k+2)(3k+3), (3k+2)(3k+3)(3k+4)$로 성립

3. $6 \mid a(a+1)(a+2)$

   $2 \mid a(a+1),\; 3\mid a(a+1)(a+2)$이므로 $a(a+1)(a+2)$는 $2$와 $3$의 공배수가 되어 $6 \mid a(a+1)(a+2)$가 성립

약수의 성질 - 연산

직관적으로 알 수 있는 내용이지만 막상 문제를 해결할 땐 잘 떠오르지 않아 숙지해야 하는 몇가지 약수의 성질들을 나열하였다. $a,b,c,d \in Z$의 경우 다음을 만족한다.

• $d \mid a, d\mid b \implies d \mid ax \pm by \quad (x,y \in Z)$

  $a=md, b=nd \quad (m,n \in Z)$에 따라 $ax \pm by = mdx \pm ndy = d(mx \pm ny)$

• $d \mid a, d \mid ax \pm b \quad (x \in Z) \implies d \mid b$

  $a=md, (ax \pm b)=nd \quad (m,n \in Z)$에 따라 $\pm b = nd-ax=d(n-mx)$

• $a \mid b, b \mid c \implies a \mid c$

  $b=am, c=bn \quad (m,n \in Z)$에 따라 $c=amn$

• $d \mid 1 \implies d=\pm1$

  $d \mid 1 \implies 1=dn \quad (n \in Z)$에 따라 $\lvert 1 \rvert = \lvert dn \rvert \leq \lvert d \rvert$

위 내용들은 합동관계에 대해 설명할 때 등장하며 알고리즘 문제에서도 합동식에 관련된 문제가 꾸준히 출제되고 있어 알아두면 좋을 것 같다.

최대공약수(gcd, greatest common divisior)

$a,b \in Z$에 대해 정수 $d \ (d>0)$가 $d \mid a, d \mid b$를 만족하고 $c \mid a, c\mid b$인 정수 $c$에 대해 $c \mid d$를 만족하면 $d$를 $a,b$의 최대공약수라 부르고 $d=gcd(a,b)$로 표기한다. 만약 $d=1$이라면 $a,b$는 서로소라 부른다.

예제

$n \in Z$에 대해 $gcd(n!+1, (n+1)!+1)=1$임을 증명하라

$d=gcd(n!+1,(n+1)!+1)$라 하자. $d \mid (n+1)(n!+1)=(n+1)!+n+1$ 또한 약수의 성질에 따라 성립한다. 그리고 $d \mid (n+1)!+n+1-n!-1$이므로 $d \mid n$를 만족하여 $d \mid n!$이다.

$d \mid n!$과 $d \mid n!+1$이므로 $d \mid n!+1-n!=1$이므로 $d=1$가 되어 $gcd(n!+1,(n+1)!+1)=1$이다.

정수 $a,b,c$을 자연수 $k$로 나누었을 때, 나머지가 같을 필요충분조건은 $k \mid a-b, k \mid c-b$임을 증명하여라

$a,b,c$를 각각 $m_1d+r, \; m_2d+r, \; m_3d+r$이라고 하면 $a-b=d(m1-m2), \; c-b=d(m3-m2)$가 되어 $d \mid a-b, \; d\mid c-b$가 성립한다.

하지만, 만약 $a=m_1d+r_1,\;b=m_2d+r_2$가 되어 $a-b = d(m_1-m_2)+(r_1-r_2)$라 한다면 $d \mid a-b$이라는 전제에 따라 $d \mid (a-b)-d(m_1-m_2)=r_1-r_2$이다. $-d<r_1-r_2<d$이므로 $d$가 $r_1-r_2$의 약수임이 확인되었는데 피제수인 $r_1-r_2$가 $d$보다 작다는 건 모순되므로 $r_1-r_2=0$가 되어 $a,b$를 $d$로 나누었을 때 나머지는 같다.

같은 방법으로 $c,b$에 대해서도 똑같이 증명이 가능하므로 $b,c$를 $d$로 나누었을 때의 나머지도 같음을 알 수 있다. 그리고 $d \mid a-b, d \mid c-b$를 활용하여 $d \mid (a-b)-(c-b) = a-c$이므로 위의 방법에 의해 $a,c$ 또한 $d$로 나누었을 떄의 나머지도 같다.

∴ $k \mid a-b, \; k \mid c-b$를 만족해야 $a,b,c$를 $k$로 나누었을 때 나머지 $r$이 같고 그 역 또한 성립한다.

유클리드의 보조정리(Euclid's Lemma)

$p$, $q$는 서로 다른 소수이고 $a$, $b$는 정수라 하자. 이 경우 $p \mid ab$이면 $p \mid a$ 또는 $p \mid b$이다.

• $p \mid a^k$이면 $p \mid a$이다.
• $p \mid a$, $q \mid a$이면 $pq \mid a$이다.

예제

$a,b \in N$이고 $gcd(a,b) = 1$이라 하자. 만약 $d \neq 1$이고 $d \mid ab$이면 다음 조건을 만족하는 소수 $p$가 존재한다.

1. $p \mid ab$
2. [$p \nmid a$ 이고 $p \mid b$] 또는 [$p \mid a$이고 $p \nmid b$]이다.

$d > 1$이라 했으므로 집합 S를 1보다 큰 $d$의 약수집합이라 하자. $d \in S$이므로 S는 공집합이 아니며 자연수의 순서정리에 따라 집합 S는 최소원소 $p$를 갖는다. 이 때 $p$는 소수이고 $d$의 약수이므로 $p \mid ab$를 만족하는 소수 $p$가 존재한다.

$p$가 소수이고 $gcd(a,b)=1$이며 $p \mid ab$가 성립하므로 [$p \nmid a$ 이고 $p \mid b$] 또는 [$p \mid a$이고 $p \nmid b$]가 성립한다.

$a,b \in N$이고 $gcd(a,b)=1$라 하자. 그러면 $gcd(a+b,ab)=1$임을 증명하여라.

소수 $p$가 $p \mid ab$이고 $p \mid a+b$라 하자. 만약 $p \mid a$라 하면, $p \mid b$이므로 $gcd(a, b)=1$에 모순된다. 반대의 경우에도 동일하기 떄문에 $p \mid ab$이고 $p \mid a+b$를 동시에 만족하는 소수 $p$는 존재하지 않는다.

(∵ 1이 아닌 소수 $p$가 $p \mid a+b$이고 $p \mid ab$이려면 $p \mid a, \; p \mid b$를 모두 만족해야 하기 때문이다.)

• 참고. 합동관계 관련 내용에도 속한다. (이후에 다룰 예정)

양의 정수 $d$에 대하여, $d$가 $4a^2+9b^2$과 $ab$의 최대공약수가 되도록 하는 서로소인 양의 정수 $a,b$가 존재한다고 한다. 이러한 $d$의 개수를 구하여라.

문제의 조건에 따라 $gcd(a,b)=1$이고 $d \mid ab$이므로 $d=AB$라 할 수 있다. ($A$는 $a$만의 약수, $B$는 $b$만의 약수)

$A \mid a, \; A \nmid b$에서 $A \mid 4a^2+9b^2$로부터 $A \mid 9b^2$여야 하므로 $A \mid 9$

$B \mid b, \; B \nmid b$에서 $B \mid 4a^2+9b^2$로부터 $B \mid 4a^2$여야 하므로 $B \mid 4$

즉, $d$가 AB=36의 약수여야 $d=gcd(4a^2+9b^2, ab)$를 만족하기 떄문에 $d$의 개수는 9개이다.

양의 정수 $a,m,n \; (101 \leq a \leq 199)$이 [$m+n$은 $a$의 배수], [$mn=a(a+1)$] 두 조건을 만족할 때 $m+n$의 값을 구하여라.

$m+n=d(m'+n')=ak, \; mn=d^2m'n'=a(a+1)$이 되는데 $gcd(a,a+1)=1, \; gcd(m',n')=1, \; gcd(m'+n',m'n')=1$이므로 $a$는 완전제곱수이다.

∵

$a|m+n,\ mn=a(a+1)$에서 a의 인수 중 $p|m\ or\ p|n$을 만족하는 p가 존재한다. 한쪽의 경우로 예를 들어 만약 $p|m$일 때, $p|a$이고 $a|m+n$이므로 $p|n$이 된다. 그리고 $gcd(a,a+1)=1$이므로 mn의 인수 중 앞에서 작성하였듯이 p를 제외한 a에 속하는 모든 인수 q도 m과 n에 공통으로 속하므로 a는 완전제곱수가 된다.

주어진 범위를 만족하는 완전제곱수는 $11^2,12^2,13^2,14^2$가 있다.

• $a$가 121일 때

  $m=11m_1,\ n=11n_1$이라고 하면, $m_1n_1=(11^2+1),\ 11|m_1+n_1$

  $11^2+1=122=2 \cdot 61$이므로 $(m_1,n_1)=(1,122), \; (2,61)$에 따라 $m_1+n_1 = 123 \; or \; 63$ 중 11의 배수는 없다.

• $a$가 144일 때

  $m=12m_1,\; n=12n_1$이라고 하면, $m_1n_1=(12^2+1), \; 12|m_1+n_1$

  $12^2+1=145=5 \cdot 29$이므로 $(m_1,n_1)=(1,145), \; (5,29)$에 따라 $m_1+n_1 = 146 \; or \; 34$ 중 12의 배수는 없다

• $a$가 169일 때

  $m=13m_1,\; n=13n_1$이라고 하면, $m_1n_1=(13^2+1), \; 13|m_1+n_1$

  $13^2+1=170=10 \cdot 17$이므로 $(m_1,n_1)=(1,170), \; (2,85), \; (5,34), \; (10,17)$에 따라 $m_1+n_1 = 171, \; 87, \; 39, \; 27$ 중 39가 13의 배수이므로 $m+n=13(39)=507$

• $a$가 196일 때

  $m=14m_1,\; n=14n_1$이라고 하면, $m_1n_1=(14^2+1), \; 14|m_1+n_1$

  $14^2+1=197=1 \cdot 197$이므로 $(m_1,n_1)=(1,197)$에 따라 $m_1+n_1 = 198$은 14의 배수가 아니다.

따라서, $m+n$은 507이다.

양의 정수 $m$과 홀수 $n$이 방정식 $m+\frac{1}{m}=6(\frac{n}{8}+\frac{8}{n})$을 만족할 때, $mn$의 값을 구하시오.

$m,n$이 0이 아니므로 양변에 $4mn$을 곱하여 주어진 수식을 보기좋게 변형하면 $4n(m^2+1)=3m(n^2+8^2)$이 된다.

$4 \mid 3m(n^2+8^2)$이고 $n$이 홀수이므로 $n^2+8^2$도 홀수가 되어 $4 \mid m$이다.

$3 \mid 4n(m^2+1)$이고 $3 \nmid m^2+1$이므로 $3 \mid n$이다.

∵

• m=3k일 때 $3 \nmid (3k)^2+1$
• m=3k+1일 때 $3 \nmid (3k)^2 +2 \cdot 3k + 1$
• m=3k+2일 때 $3 \nmid (3k)^2+2 \cdot 6k + 4$

$m=4m', n=3n'$ ($n'$은 홀수) 하여 변형된 수식에 적용 후 정리하면 $n'(16m'^2+1)=m'(9n'^2+8^2)$이다. 양변 모두 홀수이므로 $m',n'$모두 홀수에 따라 $m'=2a+1, \; n'=2b+1$로 표현할 수 있다. 그러나 두 값을 위 공식에 대입하면 정리되지 않으므로 $m',n'$가 모두 홀수라는 사실만 가져간다.

다른 방법으로 $gcd(m',n')=d$라 할 때, $m'=da, \; n'=db \quad gcd(a,b)=1$로 표현할 수 있으며 $n'(16m'^2+1)=m'(9n'^2+8^2)$에 대입하여 정리하면 $b(16d^2a^2+1)=a(9d^2b^2+8^2)$이고 $a,b$는 서로소이므로 $a \mid 16d^2b^2+1, \; b \mid 9d^2b^2+64$를 만족한다.

위 결과에 따라 $a \mid 16d^2b^2+1$이므로 1이 $a$의 배수가 되어야 한다.

$b \mid 9d^2b^2+64$이므로 64 $b$의 배수여야 하는데 $n'$이 홀수임에 따라 $b$도 홀수가 되어 $b=1$

$b(16d^2a^2+1)=a(9d^2b^2+8^2)$에 $a,b$를 대입하여 정리하면 $7d^2=63$으로 $d=3$

$m'=3, n'=3$이므로 $m=4m', n=3n'$에 대입하여 $m=12,n=9$임을 알 수 있다.

$mn=12 \cdot 9 = 108$

작성에 도움이 된 자료

• KMO 수학경시 정수론, 장환수학, 임장환 저
• 진산수학서당, 네이버 블로그