나누어떨어짐

Divisibility

정의

정수론에서, 어떤 정수가 다른 정수로 나누어졌을 때, 나머지가 없는 것을 말한다. 옛날에는 정제(整除)라 했다. 즉, [math]\displaystyle{ a,b\in\mathbb{Z} }[/math]에 대해, [math]\displaystyle{ b=ac }[/math]인 정수 [math]\displaystyle{ c }[/math]가 존재하면, [math]\displaystyle{ b }[/math]는 [math]\displaystyle{ a }[/math]로 나누어떨어진다고 한다. 초등학교에서는 [math]\displaystyle{ a }[/math]가 [math]\displaystyle{ b }[/math]를 나눈다고 배웠을 것이다. 이를 기호로는 [math]\displaystyle{ a\mid b }[/math]로 표시하며, [math]\displaystyle{ a }[/math]를 약수(Divisor) 혹은 인수(Factor), [math]\displaystyle{ b }[/math]를 [math]\displaystyle{ a }[/math]의 배수(Multiple)라 한다. 만약 [math]\displaystyle{ b }[/math]가 [math]\displaystyle{ a }[/math]로 나누어떨어지지 않을 경우, 기호로는 [math]\displaystyle{ a\not\mid b }[/math]로 표기한다.

초등학교에선 어째서인지 [math]\displaystyle{ \mid }[/math]기호를 가르치지 않고, 대학교에서 정수론을 배운다면 그 때 보게 될 것이다. 초등학교 때 배우는 수학 개념인 만큼 어려운 내용은 없지만, 이 부분은 합동식의 토대가 되므로 소홀히 해선 안 된다. 또한, 자연수가 아닌 정수임에 유의하자. [math]\displaystyle{ -4\mid24 }[/math]같은 명제는 거짓이 아니라 참이다.

성질

정수 [math]\displaystyle{ x,y,z }[/math]에 대해 다음이 성립한다.

1. [math]\displaystyle{ x\neq0 }[/math]일 때, [math]\displaystyle{ x\mid0 }[/math]
2. [math]\displaystyle{ 1\mid x,\,-1\mid x }[/math]
3. [math]\displaystyle{ x\neq0 }[/math]일 때, [math]\displaystyle{ x\mid x }[/math] (반사율)
4. [math]\displaystyle{ x\mid y,\,y\mid z }[/math]이면, [math]\displaystyle{ x\mid z }[/math] (추이율)
5. [math]\displaystyle{ y\neq0 }[/math]이고, [math]\displaystyle{ x\mid y }[/math]이면, [math]\displaystyle{ \left|x\right|\leq\left|y\right| }[/math]
6. [math]\displaystyle{ x\mid y,\,x\mid z }[/math]이면, 임의의 정수 [math]\displaystyle{ s,t }[/math]에 대해, [math]\displaystyle{ x\mid\left(sy+tz\right) }[/math]
7. [math]\displaystyle{ x\mid y,\,x\mid\left(y\pm z\right) }[/math]이면, [math]\displaystyle{ x\mid z }[/math]
8. [math]\displaystyle{ x\mid y,\,y\mid x }[/math]이면, [math]\displaystyle{ \left|x\right|=\left|y\right| }[/math]
9. [math]\displaystyle{ y\neq0 }[/math]이고, [math]\displaystyle{ x\mid y }[/math]이면, [math]\displaystyle{ \frac{y}{x}\mid y }[/math]
10. [math]\displaystyle{ z\neq0 }[/math]이면, [math]\displaystyle{ x\mid y\Leftrightarrow xz\mid yz }[/math]

기호로 써져 있지만, 잘 보면 우리가 은연중에 막 사용한 정수의 성질들이 많이 보일 것이다.

증명

1. [math]\displaystyle{ x\cdot0=0 }[/math]이므로, [math]\displaystyle{ x\mid0 }[/math]
2. [math]\displaystyle{ x=x\cdot1=\left(-x\right)\cdot\left(-1\right) }[/math]이므로, [math]\displaystyle{ 1\mid x,\,-1\mid x }[/math]
3. [math]\displaystyle{ x=x\cdot1 }[/math]이므로, [math]\displaystyle{ x\mid x }[/math]
4. [math]\displaystyle{ x\mid y,\,y\mid z }[/math]이므로, [math]\displaystyle{ y=xs,z=yt }[/math]를 만족하는 정수 [math]\displaystyle{ s,t }[/math]가 존재한다. 따라서, [math]\displaystyle{ z=yt=xst }[/math]이므로, [math]\displaystyle{ x\mid z }[/math]
5. [math]\displaystyle{ x\mid y }[/math]이므로, [math]\displaystyle{ y=xt }[/math]를 만족하는 정수 [math]\displaystyle{ t }[/math]가 존재한다. 또한, [math]\displaystyle{ y\neq0 }[/math]이므로, [math]\displaystyle{ \left|t\right|\geq1 }[/math]이다. 따라서 [math]\displaystyle{ \left|y\right|=\left|xt\right|=\left|x\right|\left|t\right|\geq\left|x\right| }[/math]
6. [math]\displaystyle{ x\mid y,\,x\mid z }[/math]이므로, [math]\displaystyle{ y=xa,z=xb }[/math]를 만족하는 정수 [math]\displaystyle{ a,b }[/math]가 존재한다. 따라서, 임의의 정수 [math]\displaystyle{ s,t }[/math]에 대해 [math]\displaystyle{ sy=xas,tz=xbt }[/math]이고, [math]\displaystyle{ sy+tz=x\left(as+bt\right) }[/math]이다. 그러므로, [math]\displaystyle{ x\mid\left(sy+tz\right) }[/math]
7. [math]\displaystyle{ x\mid y,\,x\mid\left(y\pm z\right) }[/math]이므로, [math]\displaystyle{ y=xa,y\pm z=xb }[/math]를 만족하는 정수 [math]\displaystyle{ a,b }[/math]가 존재한다. 그러면, [math]\displaystyle{ \pm z=xb-y=xb-xa=x\left(b-a\right) }[/math]이므로, [math]\displaystyle{ z=\pm x\left(b-a\right) }[/math]이다. 따라서, [math]\displaystyle{ x\mid z }[/math]
8. [math]\displaystyle{ x\mid y,\,y\mid x }[/math]이므로, [math]\displaystyle{ y=xs,x=yt }[/math]를 만족하는 정수 [math]\displaystyle{ s,t }[/math]가 존재한다. 그런데 [math]\displaystyle{ x=yt=xst }[/math]이므로 [math]\displaystyle{ ts=1 }[/math]이다. 이는 [math]\displaystyle{ t,s }[/math]가 둘 다 1이거나 -1일 때만 성립한다. 따라서 [math]\displaystyle{ x=y }[/math]이거나 [math]\displaystyle{ x=-y }[/math]이고, 곧 [math]\displaystyle{ \left|x\right|=\left|y\right| }[/math]
9. [math]\displaystyle{ x\mid y }[/math]이므로, [math]\displaystyle{ y=xt }[/math]인 정수 [math]\displaystyle{ t }[/math]가 존재한다. 또한, [math]\displaystyle{ y\neq0 }[/math]이므로 [math]\displaystyle{ t\neq0 }[/math]이다. 즉, [math]\displaystyle{ t\mid y }[/math]가 성립한다. 한편, [math]\displaystyle{ t=\frac{y}{x} }[/math]이므로, [math]\displaystyle{ \frac{y}{x}\mid y }[/math]
10. [math]\displaystyle{ x\mid y }[/math]이면, 적당한 정수 [math]\displaystyle{ s }[/math]에 대해 [math]\displaystyle{ y=xs }[/math]이다. 양변에 [math]\displaystyle{ z }[/math]를 곱하면 [math]\displaystyle{ yz=xzs }[/math]이므로, [math]\displaystyle{ xz\mid yz }[/math]이다. 역으로 [math]\displaystyle{ xz\mid yz }[/math]이면, 적당한 정수 [math]\displaystyle{ t }[/math]에 대해 [math]\displaystyle{ yz=xzt }[/math]이고, [math]\displaystyle{ z\neq0 }[/math]이므로, [math]\displaystyle{ y=xt }[/math]이다. 즉, [math]\displaystyle{ x\mid y }[/math]

약수와 배수

나누어떨어짐에 더 알기 위해서는 약수와 배수에 대해서도 알아야한다. 먼저, 어떤 정수의 약수가 1과 자기 자신 단 두 개 밖에 없다면 그 수는 소수가 된다. 약수가 세 개 이상이라면 합성수가 된다. 1은 약수가 한 개 라서 소수도, 합성수도 아니다. 회색분자 책에 따라서는 중성수라 부르기도 한다. 그럼 약수는 어떻게 찾을까? 제일 간단하고 무식한 방법은 소수로 하나씩 나누어 보는 것이다. 합성수는 자기 자신의 제곱근보다 작거나 같은 약수를 가지므로 수가 크지 않다면 노가다도 좋은 방법이다. 여기서 조금 더 발전하면 초등학교 때 부터 지겹도록 배워온 배수판정법을 쓸 수 있다. 그 방법은 아래와 같다.

정수 [math]\displaystyle{ N }[/math]을 10의 거듭제곱으로 표현하면 [math]\displaystyle{ N=\sum_{i=0}^{n}a_i\cdot10^i,\,a_i\in\left\{0,1,2,\cdots,9\right\},\,i=0,1,2,\cdots,n }[/math]이다. 그러면,

1. [math]\displaystyle{ 2\mid a_0\Rightarrow2\mid N }[/math]
2. [math]\displaystyle{ 3\mid\sum_{i=0}^{n}a_i\Rightarrow3\mid N }[/math]
3. [math]\displaystyle{ 4\mid\left(10a_1+a_0\right)\Rightarrow4\mid N }[/math]
4. [math]\displaystyle{ 5\mid a_0\Rightarrow5\mid N }[/math]
5. [math]\displaystyle{ 2\mid N,\,3\mid N\Rightarrow6\mid N }[/math]
6. [math]\displaystyle{ 8\mid\left(100a_2+10a_1+a_0\right)\Rightarrow8\mid N }[/math]
7. [math]\displaystyle{ 9\mid\sum_{i=0}^{n}a_i\Rightarrow9\mid N }[/math]
8. [math]\displaystyle{ a_0=0\Rightarrow10\mid N }[/math]

이다. 7, 11, 13의 배수는 조금 특이한데, 일의 자리부터 세 자리씩 끊은 뒤, 각 부분을 교대로 빼고 더한 값이 7, 11, 13의 배수이면 된다. 이는 1001=7·11·13임을 활용한 것이다.

아래 두 정리도 약수, 배수를 판별하는데 도움이 된다.

1. [math]\displaystyle{ m\mid pq,\,\gcd\left(m,p\right)=1 }[/math]이면 [math]\displaystyle{ m\mid q }[/math]
2. [math]\displaystyle{ p\mid a_1a_2\cdots a_n }[/math]이면 [math]\displaystyle{ p\mid a_i }[/math]를 만족하는 [math]\displaystyle{ a_i }[/math]가 존재한다.

증명은 다음과 같다.

1. 적당한 정수 [math]\displaystyle{ a,b }[/math]에 대해, [math]\displaystyle{ am+bp=1 }[/math]이다. 양변에 [math]\displaystyle{ q }[/math]를 곱하면, [math]\displaystyle{ q=amq+bpq }[/math]이다. 그런데 [math]\displaystyle{ m\mid amq,\,m\mid pq }[/math]이므로, [math]\displaystyle{ m\mid\left(amq+bpq\right)=q }[/math]
2. [math]\displaystyle{ n=1 }[/math]이면 자명하다.
   [math]\displaystyle{ n=k }[/math]일 때 성립한다 가정하자. 그럼, [math]\displaystyle{ p\mid a_1a_2\cdots a_k }[/math]이고, [math]\displaystyle{ p\mid a_i }[/math]인 [math]\displaystyle{ a_i }[/math]가 존재한다. 그런데 나누어떨어짐의 성질에 의해, [math]\displaystyle{ p\mid a_1a_2\cdots a_ka_{k+1} }[/math]이고, [math]\displaystyle{ p\mid a_i }[/math]이므로, [math]\displaystyle{ n=k+1 }[/math]일 때도 성립한다.
   따라서 수학적 귀납법에 의해 명제는 참이다.

마지막으로, 산술의 기본 정리에 의해 1보다 큰 모든 정수는 소인수분해가 가능하다. 즉, 1보다 큰 임의의 정수 [math]\displaystyle{ n }[/math]에 대해 [math]\displaystyle{ n={p_1}^{e_1}{p_2}^{e_2}\cdots{p_n}^{e_n} }[/math]이 성립한다는 소리. 여기서 [math]\displaystyle{ p_i }[/math]는 소수이자, [math]\displaystyle{ n }[/math]의 약수이다. 참고로 양의 약수의 개수는 [math]\displaystyle{ \left(e_1+1\right)\left(e_2+1\right)\cdots\left(e_n+1\right) }[/math]이고, 양의 약수의 총 합은 [math]\displaystyle{ \frac{{p_1}^{e_1+1}-1}{p_1-1}\cdot\frac{{p_2}^{e_2+1}-1}{p_2-1}\cdots\frac{{p_n}^{e_n+1}-1}{p_n-1} }[/math]이다. 이 역시 초등학교에서 배웠을 내용. 증명은 경우의 수와 곱의 법칙을 사용하여 간단히 증명할 수 있다.

관련 항목

• 최대공약수
• 최소공배수
• 소인수분해
• 유클리드 호제법
• 나눗셈 정리
• 모듈러산술