정수론 | 부정방정식 유형 풀이 - 1

• 이전 포스팅에서 선형 디오판토스 방정식에 대한 증명과 다양한 성질을 다루었기에 이번 포스팅에서는 관련 문제 유형에 따른 풀이 방법을 정리하고자 한다.
• 선형 디오판토스 방정식에 대한 특수해와 일반해를 구하는 방법은 1번링크, 2번링크에 정리해두었다.

선형 부정방정식 $ax+by=n$이 주어진 경우

선형 부정방정식 $710x+68y=6$의 정수해를 구하여라.

양변을 2로 나누면 $305x+34y=3$이 되고 $gcd(305,34)=1$이므로 주어진 식의 우변은 좌변 두 계수의 최대공약수의 배수임을 알 수 있다. 유클리드 호제법을 사용하여 각 계수가 어떻게 변하는지 확인 후 확장 유클리드 알고리즘을 활용하여 특수해를 구하면 다음과 같다.

$710-68\cdot10=30$

$68-30\cdot2=8$

$30-8\cdot3=6$

$8-6=2$

위 유클리드 호제법의 결과를 역으로 올라가는 과정을 정리하면 다음과 같다.

$2=8-6$

$2=4\cdot8-30 \quad \because 6=30-8\cdot3$

$2=4\cdot68-9\cdot30 \quad \because8=68-30\cdot2$

$2=(-9)\cdot710+94\cdot68 \quad \because30=710-68\cdot10$

따라서, 주어진 식의 특수해는 양변의 3을 곱한 값인 (-27,282)임을 확인하였다. 주어진 식과 대입한 식은 서로 값이 동일하므로 각 미지수에 대해 정리하면 다음과 같다.

$710x+68y=710\cdot(-27)+68\cdot282$

$355(x+27)=34(282-y)$

$gcd(355,34)=1$이므로 임의의 정수에 대해 x+27은 34t이고 282-y는 355t가 성립함을 알 수 있다. 그러므로 주어진 문제의 정수해는 $(34t-27,355t+y)$이다.

$18x+19y=2005$를 만족시키는 양의 정수쌍 (x,y)의 개수를 구하여라.

$gcd(18,19)=1$이므로 주어징 방정식은 정수해를 가지며 간단히 (-1,1)임을 구할 수 있다. $18\cdot(-1)+19\cdot1=1$의 양변에 2005를 곱하면 주어진 식의 특수해가 $(-2005,2005)$임을 확인할 수 있다. 이를 통해 도출된 $18x+19y=18\cdot(-2005)+19\cdot(2005)$를 정리하면 임의의 정수 t에 대해 일반해 $(-2005+19t,2005-18t)$를 구할 수 있다. 다만, 위 조건에 따라 x, y는 각각 양의 정수이므로 $105.5\cdots<t<111.3\cdots$의 범위를 만족하는 정수 t는 6개이다. 따라서 위 식을 만족시키는 양의 정수쌍은 6개이다.

부정방정식의 인수분해를 통한 풀이방법

$2x^2y^2+y^2-26x^2=1201$을 만족하는 양의 정수 쌍 $(x,y)$의 개수를 구하여라.

주어진 식을 인수분해를 위해 정리하면 $2x^2(y^2-13)+y^2=1201$이 되고 y에 대해서도 동일하게 값을 맞춰주면 $(2x^2+1)(y^2-13)=1188=2^23^311$로 정리가 된다. $2x^2+1$은 반드시 홀수이므로 좌변 인수의 조합에 따라 $3,\ 3^2,\ 11,\ 3^3,\ 3\cdot11,\ 3^2\cdot11,\ 3^3\cdot11$이 가능하다. 정리하면 $x^2$에 해당하는 값은 1, 4, 5,13, 16, 49, 148로 제곱수만 가능함에 따라 x가 가질 수 있는 값은 1, 2, 4, 7이다.

가능한 x값을 대입하여 $y^2$이 가질 수 있는 값을 정리하면 409, 145, 49, 25로 제곱수만 가능함에 따라 y가 가질 수 있는 값은 5, 7뿐이다. 따라서 위 식을 만족하는 양의 정수쌍은 2개이다.

이차방정식 $x^2+(m+1)x+2m-1=0$의 두 개의 근이 정수가 되도록 하는 정수 m의 값을 구하여라.

두 개의 정수 근을 $\alpha,\ \beta$라 하면 $\alpha+\beta=-m-1,\ \alpha\beta=2m-1$을 만족한다. 두 식을 m에 대해 정리하면 $\alpha\beta+2(\alpha+\beta)=-3$이고 다항식의 곱 형태로 정리하면 $(\alpha+2)(\beta+2)=1$이다. 만족하는 값은 (-1,-1), (-3,-3)이다. 따라서 해당 값을 대입하면 m은 1, 5이다.

$n^a+2n^b=n^c$, $a+b+c\le500$을 모두 만족하는 양의 정수 a, b, c, n으로 이루어진 순서쌍 (a, b, c, n)의 개수를 구하여라.

$n^a+2n^b=n^c$에 따라 a<c, b<c를 만족한다. 그렇다면 a, b의 관계에 따라 식을 정리하여 만족하는 범위를 정리해야 한다.

• a=b인 경우

  $3n^a=n^c$이므로 양변을 $n^a$로 나누면 $3=n^{c-a}$가 된다. 조건을 만족하려면 n은 3, c-a=1이 되어야 하므로 c=a+1이다. 두 번째 식에 대입하면 $3a\le499$이므로 만족하는 a의 값의 개수를 166개로 순서쌍의 개수는 166쌍이다.

• a<b인 경우

  양변을 $n^a$로 나누면 $1+2n^{b-a}=n^{c-a}$이고 양변을 다시 $n^{b-a}$로 나누어 정리하면 $2=n^{c-b}-\cfrac{1}{n^{b-a}}$이다. 해당 조건을 만족하려면 $n^{b-a}|1$이 성림해야 하므로 $n|1$이거나 $a=b$이어야 하기 때문에 모순이다.

• b<a인 경우

  양변을 $n^b$로 나누면 $n^{a-b}+2=n^{c-b}$이고 정리하면 $2=n^{a-b}(n^{c-a}-1)$이다. 해당 조건을 만족,하려면 $n^{a-b}=1,\ n^{c-a}-1=2$이거나 $n^{a-b}=2,\ n^{c-a}-1=1$이어야 한다. 이 경우 가능한 값은 n=2, a-b=1, c-a=1이면 조건을 만족함을 알 수 있고 두 번째 식에 대입하여 정리하면 $3b\le497$이다. 이를 만족하는 b는 165개로 순서쌍의 개수는 165개다.

따라서, (a,b,c,n)을 만족하는 순서쌍의 개수는 331개이다.

문제에서 주어진 조건 해석을 통한 풀이

두 수 $n^2+3m$과 $m^2+3n$이 모두 완전제곱수가 되게 하는 양의 정수 m, n에 대해 mn의 최댓값을 구하여라.

주어진 두 식이 서로 대칭이므로 임의로 $m\le n$이라 두어도 일반석을 잃지 않는다. 그렇다면 첫 번째 식에 대해 제곱수에 대한 범위를 정리하면 $n^2<n^2+3m\le n^2+3n<(n+2)^2$이다. 따라서, $n^2+3m=(n+1)^2$이고 정리하면 $n=\cfrac{3}{2}m-\cfrac{1}{2}$이다. 이 값을 두 번째 식에 대입하여 제곱수에 대한 범위를 정리하면 $m^2<m^2+3n=m^2+\cfrac{9}{2}m-\cfrac{3}{2}<(m+3)^2$이다. 정리된 값이 가질 수 있는 제곱수는 $(m+1)^2$과 $(m+2)^2$이므로 정리하여 도출된 m,n의 값은 (1,1), (11,16)이다. 따라서, mn의 최댓값은 176이다.

자연수 m, n이 식 $2m^2+2n^2=137(m-n)$을 만족시킬 때, m+n의 값은 얼마인가?

좌변이 짝수이므로 임의의 정수 k에 대해 $m-n=2k$가 성립한다. $m=n+2k$라 하고 식에 대입하여 정리하면 $2n^2+4nk+4k^2=137k$이다. 좌변이 짝수이므로 k도 임의의 정수에 대해 $k=2h$라 할 수 있다. 대입하여 정리하면 $n^2+4nh+8h^2=137h$가 된다. 좌변을 제곱수 형태로 정리하면 $(n+2h)^2=h(137-4h)$이 된다. 좌변이 제곱수임에 따라 $137-4h>0$을 만족하는 h의 범위는 $h\le34$임을 알 수 있다. 그리고 우변도 제곱수여야 하므로 h와 137-4h 모두 각각 제곱수여야 한다.($\because\ h\ne137-4h$) 앞에서 구한 조건을 만족하는 h는 1, 4, 9 ,16, 25이고 각각에 대해 137-4h에 대입하면 h=4일 때 121이 되어 조건을 성립한다. 값을 대입하면 $(n+8)^2=2^2\cdot11^2$ 따라서 $n=14,\ h=4$임에 따라 $k=8$이고 $m=n+16$이 되어 $m+n=44$이다.

작성에 도움이 된 자료

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