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

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

점화식 형태의 함수가 주어진 경우

함수 $f\ :\ N\times N \rightarrow N$가 다음 조건을 만족할 때, $f(p,q)=2001$을 만족하는 자연수의 순서쌍 (p,q)를 모두 구하여라.

1. $f(1,1)=2$
2. $f(m+1,n)=f(m,n)+m, \quad f(m,n+1)=f(m,n)-n$

2-1번 조건에 따라 $f(p,q)$는 $f(p-1,q)+p-1$로 나타낼 수 있고 이를 연쇄적으로 계속하면 $f(1,q)+(p-1)+(p-2)+\dots+1$을 얻을 수 있다. 식을 정리하면 $f(p,q)=f(1,q)+\cfrac{(p-1)p}{2}$이 된다.

2-2번 조건에 따라 $f(1,q)$는 $f(1,q-1)-(q-1)$로 나타낼 수 있고 이를 연쇄적으로 반복하면 $f(1,1)-\cfrac{(q-1)q}{2}$를 얻는다. $f(1,1)=2$이므로 $f(p,q)=2+\cfrac{(p-1)p}{2}-\cfrac{(q-1)q}{2}=2001$이 된다. 양변에 2를 곱하여 정리하면 $(p-q)(p+q-1)$이고 $p-q<p+q-1$이므로 $(p-q,p+q-1)=(1,2\cdot1999),(2,1999)$가 되어 자연수 순서쌍 (p,q)는 (2000,1999), (1001,999)이다.

연속하는 자연수 합

10000을 연속하는 두 개 이상의 자연수 합으로 나타낼 수 있는 경우의 수는 얼마인가? (단, 더하는 순서는 무시한다.)

자연수 $a+1$부터 시작하여 연속하는 $n$개의 자연수를 더하면 10000이 된다고 가정하자. 이를 나타내는 식은 $(a+1)+(a+2)+\cdots+(a+n)$이고 식을 정리하면 $an+\cfrac{n(n+1)}{2}=10000=2^4\cdot5^4$이다. 양변에 2를 곱하여 다시 정리하면 $n(2a+n+1)=2^5\cdot5^4$가 된다. 소인수분해 결과 홀수와 짝수 인수가 존재하는데 $n,\ 2a+n+1$은 서로 홀짝이 다르므로 적어도 좌변에 존재하는 한개의 인수는 $2^5$를 인수로 갖는다.

• 만약 n이 짝수라면

  $n=2^5\cdot5^k,\ 2a+n+1=5^{4-k}\ (k\le4)$라 둘 수 있다. $n<2a+n+1$이므로 $2^5<5^{4-2k}$가 되어 k가 가질 수 있는 값은 0밖에 없다. 그러므로 $n=2^5$

• 만약 n이 홀수라면

  $n=5^k,\ 2a+n+1=2^5\cdot5^{4-k}\ (k\le4)$라 둘 수 있다. $n<2a+n+1$이므로 $5^{2k-4}<2^5$가 되어 k가 가질 수 있는 값은 3, 2, 1, 0이다. 그러나 k가 0의 값을 가지면 n은 1이므로 문제에서 제시된 조건에 모순되므로 k가 가질 수 있는 값은 1, 2, 3이 된다.

그러므로 10000을 연속하는 두 개 이상의 자연수 합으로 나타낼 수 있는 경우의 수는 4가지이다.

판별식과 방정식의 해

방정식$(a^2+b)(a+b^2)=(a-b)^3$을 만족하는 모두 0이 아닌 정수해 쌍 $(a,b)$를 모두 구하여라.

주어진 식을 전개하면 $a^3+ab+a^2b^2+b^3=a^3-3a^2b+3ab^2-b^3$이고 정리하면 $b(2b^2+(a^2-3a)b+3a^2+a)=0$을 얻는다. $b\ne0$이므로 $2b^2+(a^2-3a)b+3a^2+a=0$을 만족해야 한다. 이 방정식에 정수근이 존재하려면 판별식이 0이거나 제곱수여야 한다. 근의 공식에 따라 b는 $b=\cfrac{-(a^2-3a)\pm\sqrt{D}}{4}$이다.

판별식 $D=(a^2-3a)^2-4\cdot2(3a^2+a)$

$=a^4-6a^3-15a-8a$

$=a(a^3-6a^2-15a-8)$

$=a(a-8)(a+1)^2$이 된다.

$a\ne0$이므로 $a=-1$이거나 임의의 정수 $n$에 대하여 $a(a-8)=n^2$를 만족해야 한다.

• $a=-1$

  $D=0$이 되어 $b=-1$이 된다.

• $a(a-8)=n^2$

  조건을 정리하면 $(a-4)^2-n^2=4^2$가 되고 인수분해하면 $(a-4-n)(a-4+n)=16$을 얻는다. 정수조건이므로 $(a-4-n,a-4+n)$은 $(1,16),(2,8),(4,4),(-16,-1),(-8,-2),(-4,-4)$의 값을 가질 수 있다.

  그러나 두 항을 더했을 때 $2a-8$이 되어 가질 수 있는 값에 대해 정리하면 짝수이므로 $(1,16),(-16,-1),(-4,-4)$는 홀수와 $a$가 0이 되어 조건에 모순된다. 나머지 $a$가 가질 수 있는 값은 9, 8, -1을 갖는데 -1은 이전에 정리하였으므로 9와 8에 대해서 b가 가질 수 있는 값을 구하면 된다.

  $a=9$이면 판별식 D는 30의 제곱수가 되어 b의 값은 -6, -21을 갖는다. $a=8$이면 D는 0이 되어 b의 값은 -10을 갖는다.

따라서, 주어진 방정식을 만족하는 정수해 쌍 $(a,b)$는 $(-1,-1),(8,-10),(9,-6),(9,-21)$이다.

표현방법 해석

조건 $n^2=m^4+2m^3+2m^2+2m+2$를 만족시키는 정수의 순서쌍 $(m,n)$의 집합을 $A={(m_i,n_i)|i=1,2,\cdots,k}$라고 하자. $\sum_{i=1}^k (m_i^2+n_i^2)$의 값을 구하여라.

주어진 식의 좌변이 제곱수이므로 우변도 제곱수여야 한다. 우변에 주어진 식을 정리하면 $(m^2+m)^2+(m+1)^2+1$을 얻을 수 있다. 이 식을 P라고 하면 $(m^2+m)^2<P\le(m^2+m+1)^2$의 관계를 얻을 수 있다. P는 $(m^2+m)^2$보다 반드시 크므로 제곱수가 되려면 $P=(m^2+m+1)^2$의 관계를 만족해야 한다. 식을 전개하여 정리하면 $m^2-1=0$이 되어 m이 가질 수 있는 값은 1, -1임을 확인할 수 있고 P에 대입하면 1, 9가 되어 n이 가질 수 있는 값은 1, -1, 3, -3이다.

따라서, A집합은 $(1,3),(1,-3),(-1,1),(-1,-1)$이 되어 구하고자 하는 값은 24이다.

작성에 도움이 된 자료

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