정수론 | 약수와 배수 유형문제

약수와 배수 문제 유형 1

정리: 임의의 정수 a, b에 대하여 다음 식이 성립한다.

• $(a-b)|(a^n-b^n)\quad$ $n\in N$
• $(a+b)|(a^{2n}-b^{2n})\quad$ $n\in N$
• $(a+b)|(a^{2n-1}+b^{2n+1})\quad$ $n\in N$

$a^n-b^n=(a-b)(a^{n-1}+a^{n-2}b+a^{n-3}b^2+\cdots+ab^{n-2}+b^{n-1})$

$a^n-1=(a-1)(a^{n-1}+a^{n-2}+\cdots+a+1)$을 참고하면 된다.

예제

n이 자연수일 때, $323|20^{2n}+16^{2n}-3^{2n}-1$이 성립함을 보여라

$323=17\cdot19$

$20^{2n}+16^{2n}-3^{2n}-1$ = $(20^{2n}-3^{2n})+(16^{2n}-1^{2n})$

$20-3|(20^{2n}-3^{2n})$, $16+1|(16^{2n}-1^{2n})$

따라서 주어진 식은 17의 배수이고 동일한 방법으로 19의 배수임을 증명할 수 있다.

약수와 배수 문제 유형 2

예제

방정식 $xy+yz+zx=xyzm$을 만족시키는 자연수 해를 구하라

주어진 수식을 xyz로 나누면 $\cfrac{1}{z}+\cfrac{1}{x}+\cfrac{1}{y}=m$이다. 그리고 문제에서 미지수 x, y, z에 대해 대칭이므로 임의로 $x \le y \le z$라고 가정해도 일반성을 잃지 않는다. 따라서 가정에 따라 $\cfrac{1}{z}\le\cfrac{1}{y}\le\cfrac{1}{x}$가 성립한다.

가정에 따라 $m\le\cfrac{3}{x}$에 의해 가능한 m의 값은 1,2,3이다. (자연수 해이므로)

• m=3일 때, x=1이고 $\cfrac{1}{y}+\cfrac{1}{z}=2$에서 y=z=1으로 (1,1,1)이 성립한다.

• m=2일 때, x=1이고 $\cfrac{1}{y}+\cfrac{1}{z}=1$에서 y=z=2로 (1,2,2)가 가능하며 x,y,z가 서로 대칭이므로 가능한 가지수는 3개이다.

• m=1일 때 x가 취할 수 있는 값은 1, 2이다.

  • x=2일 때, $\cfrac{1}{y}+\cfrac{1}{z}=\cfrac{1}{2}\le\cfrac{2}{y}$에서 y는 3, 4를 취할 수 있다.
    • y=3일 때, z=6
    • y=4일 때, z=4
  • x=3일 때, $\cfrac{1}{y}+\cfrac{1}{z}=\cfrac{2}{3}\le\cfrac{2}{y}$에서 y는 3을 취할 수 있다.
    • y=3일 때, z=3

  따라서 순서쌍 (2,3,6), (2,4,4), (3,3,3)을 가지고 서로 대칭임을 고려하여 가능한 가지수는 6+3+1로 10개이다.

따라서 가능한 총 순서쌍의 개수는 14개이다.

$\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+\frac{1}{abc}=1$를 만족하는 서로 다른 자연수 a, b, c의 순서쌍 (a,b,c)는 모두 몇 개인가?

a, b, c에 대해 대칭이므로 $a\le b\le c$라 가정하여도 일반성을 잃지 않는다. 그리고 a=1인 경우 성립하지 않으므로 $2\le a\le b\le c$이다.

가정에 따라 역수를 취한 $\cfrac{1}{abc}<\cfrac{1}{c}\le\cfrac{1}{b}\le\cfrac{1}{a}$ 관계가 성립하고 문제의 수식에서 $1=\cfrac{1}{a}+\cfrac{1}{b}+\cfrac{1}{c}+\cfrac{1}{abc}\le\cfrac{3}{a}+\cfrac{1}{abc}<\cfrac{4}{a}$을 만족한다. 정리하면 a<4이고 a가 취할 수 있는 값은 2, 3이다.

• a=2일 때, $\cfrac{1}{b}+\cfrac{1}{c}+\cfrac{1}{2bc}=\cfrac{1}{2}$에서 양변에 2bc를 곱해 정리하면 2(b+c)+1=bc이다. 두 수의 곱으로 표현하면 (b-2)(c-2)=5로 표현할 수 있고 가정한 관계에 따라 b=3, c=7을 만족한다.
• a=3일 때, $\cfrac{1}{b}+\cfrac{1}{c}+\cfrac{1}{3bc}=\cfrac{2}{3}$에서 양변에 3bc를 곱해 정리하면 3b+3c+1=2bc이다. 두 수의 곱으로 표현하기 위해 양변에 2를 곱하여 정리하면 (2b-3)(2c-3)=11이고 가정한 관계에 따라 b=2, c=7인데 $a\le b$이므로 모순이다.

따라서 가능한 순서쌍은 (2,3,7)이고 a,b,c가 가질 수 있는 순서쌍은 (2,3,7)을 배열한 가짓수인 6개이다.

약수와 배수 문제 유형 3

예제

$(a-1)(b-1)(c-1)$이 $(abc-1)$의 약수가 될 a, b, c를 모두 구하여라. (단, 1<a<b<c)

임의의 자연수 $k=\cfrac{abc-1}{(a-1)(b-1)(c-1)}$이라 가정하면 $k<\cfrac{abc}{(a-1)(b-1)(c-1)}$이고 각각에 대해 풀어서 $(1+\cfrac{1}{a-1})(1+\cfrac{1}{b-1})(1+\cfrac{1}{c-1})$이 된다. k가 최대값을 가지는 경우는 a=2, b=3, c=4인 경우이고 대입해서 정리하면 k<4의 결과를 얻을 수 있다. 그리고 $\cfrac{abc-1}{ab(c-1)}=\cfrac{abc-1}{abc-ab}=1+\cfrac{ab-1}{abc-ab}<k$로 1<k가 성립하여 k가 가질 수 있는 값은 2와 3이다. 그런데 $(1+\cfrac{1}{a-1})(1+\cfrac{1}{b-1})(1+\cfrac{1}{c-1})$은 k보다 항상 큰 값이지만 분모의 값이 커지면 되려 1에 근접한 형태임을 알 수 있으므로 k가 적어도 2의 값을 가지기 위한 a값의 범위가 어떻게 되는지 검사해야 한다. 하나씩 대입했을 때 4부터 k<2가 되어 k가 어떠한 값도 가질 수 없음을 확인할 수 있고 이에 따라 $a<4$여야 주어진 조건에 모순되지 않고 해가 존재할 수 있음을 알 수 있다.

따라서 (a,k) 순서쌍은 (2,2), (2,3), (3,2)가 가능하다.

• (a,k)=(2,2)이면 $2bc-1=2(b-1)(c-1)$이 되고 정리하면 2(b+c)=3의 결과를 얻어 자연수 해가 존재하지 않는다.
• (a,k)=(2,3)이면 $3(b-1)(c-1)=2bc-1$이 되고 (b-3)(c-3)=5에서 b=4, c=8의 결과를 얻을 수 있다.
• (a,k)=(3,2)이면 $2(b-1)(c-1)=3bc-1$이 되고 (b-4)(c-4)=11에서 b=5, c=15의 결과를 얻을 수 있다.

약수와 배수 문제 유형 4

예제

정수 m에 대해 $\frac{m^3+m+5}{m^2-m+1}$의 값이 정수가 되도록 하는 모든 m의 값을 구하여라.

주어진 식을 나누어 몫과 나머지로 구분하면 $m+1+\cfrac{m+4}{m^2-m+1}$이므로 주어진 식이 정수가 되려면 최소한 $m^2-m+1\le|m+4|$을 만족해야 한다. 우변에 절대값 기호가 있는데 x=-4를 기준으로 보다 작으면 -x-4가 되므로 대입하여 정리하면 $m^2\le-5$가 되어 모순이다. 따라서 해가 존재하더라도 x=-4보다 크기 때문에 그대로 계산하면 $m^2-2m-3\le0$이 되어 $(m+1)(m-3)\le0$으로 m의 해는 -1, 0, 1, 2, 3이고 추가로 주어진 식에서 m=-4인 경우 분수꼴이 0이 되어 정수가 되기 때문에 모든 m의 값은 -4, -1, 0, 1, 2 ,3이다.

작성에 도움이 된 자료

• KMO 수학경시 정수론, 장환수학, 임장환 저