AWS 서비스를 활용한 Serverless API

읽기 전

• 이번에 앱 개발을 하면서 데이터 송수신에 사용할 serverless api를 구현하자는 의견이 있어 정리합니다.
• node.js와 웹 위주로 정리된 글은 많지만 필자가 이번에 구현하려는 python과 안드로이드 관련 내용은 부족한 감이 있어 작성하고자 합니다.

구조 설명

구현하고자 하는 API는 GET, POST, DELETE 메소드를 지원한다. 안드로이드에서 요청을 보내면 AWS API Gateway에서 매핑하여 AWS Lambda로 넘겨 처리한 뒤 DynamoDB의 데이터를 조회, 삽입, 삭제한다. 구현하고자 하는 기능은 실시간 연동이 아니라 기능 호출 시 작동하므로 cold start를 저렴하게 이용할 수 있는 방법을 생각하다가 serverless를 채택하게 되었다. 그리고 서버관리가 필요없이 on-demand 방식으로 자연스럽게 확장할 수 있다는 점도 serverless를 채택하게 된 계기가 되었다.

구성 서비스 소개

AWS API Gateway

WebSocket API, REST API, HTTP API 등을 지원한다. API를 사용한 외부 클라이언트와 AWS 서비스 간 통신을 구현함에 있어 가장 첫 번째 단계로 볼 수 있다. 클라이언트가 요청한 메소드에 대해 input data를 매핑하여 다음 단계로 전달하거나 요청에 대한 response를 반환할 때 원하는 형태로 매핑을 할 수 있다.

AWS Lambda

원하는 기능을 함수 단위로 작성하여 관리할 수 있게끔 한다. 다양한 런타임을 제공하며 트리거를 설정하여 작동할 수 있다. 이번에는 외부 클라이언트에서의 API 호출에 따라 작동하므로 API Gateway가 트리거가 되어줄 것이다. EC2처럼 실시간으로 요금이 책정되는 서비스와는 달리 사용량에 따라 요금이 책정되기 때문에 이벤트 기반으로 원하는 기능을 구현하고자 한다면 나쁘지 않은 선택이 될 것이다. 다만, 실행 횟수가 많아지면 단가의 차이가 발생하여 서버 구축이 오히려 저렴할 수 있으므로 가급적 가볍거나 실험적으로 제작하는 토이 프로젝트를 구현할 때 적합하다.

AWS DynamoDB

SQL 엔진을 지원하는 RDS 서비스와는 달리 AWS에서 자체적으로 지원하는 NoSQL 데이터베이스 서비스이다. 그렇기 때문에 사용자가 생성한 테이블의 데이터 등을 웹 콘솔에서 확인할 수 있어 좀 더 직관적이라는 장점이 있다. RDS를 사용할까도 생각했지만 VPC 설정하고 이것저것 작업을 요구하기에 이후 데이터 컬럼 확장을 생각하여 NoSQL로 채택하였다. 단점은 Amazon에서 자체적으로 제작하여 지원하는 데이터베이스다 보니 공식 API 기능 명세 도큐먼트와 데이터 저장 형식이 Amazon이 지정한 방식에 의존해야 한다는 단점이 있다. 만약 굳이 AWS 서비스만을 사용해서 serverless 환경을 구축하는 것이 아니라면 RDS를 사용하는 방법이 더 효율적일 수 있다.

격자평면(Lattice Plane)이란

평면 위에 가로 세로의 간격이 각각 1씩인 점들로 구성된 평면을 격자평면(lattice plane)이라고 부른다.

Visible point, Invisible point

원점 O에서 바로 볼 수 있는 점을 Visible point라 부르고 다른 격자점에 막혀서 보이지 않는 점을 Invisible point라고 부른다.

아래 그림의 경우 점 P가 Visible point이고 점 Q가 Invisible point가 된다.

정리: 격자평면에서 점 P(m,n)이 Visible point일 필요충분조건은 $gcd(m,n)=1$이고 Invisible point일 필요충분조건은 $gcd(m,n)\ne1$이다.

[증명] 어떠한 점이라도 점 P(m,n)을 원점 O에 대해 막지 않으려면 m, n보다 작은 정수 중 동일 기울기를 갖는 값이 존재해서는 안된다. 그러므로 $gcd(m,n)=1$이어야 점 P가 Visible point가 된다.

Invisible point에 대해서 다른 가로막는 격자점을 $Q(m',n')$이라고 하면 같은 기울기를 갖고 있기 때문에 임의의 정수 $k$에 대해 $k(m',n')=(m,n)$을 만족하는 정수 $k$가 존재한다. 따라서 $km'=m,\ kn'=n$이므로 $gcd(m,n)=k\ne1$이 된다.

정리: 직선 $y=ax$에서 기울기 $a$가 무리수이면 직선 $y=ax$는 원점 이외의 어떤 격자점도 지나가지 않는다.

[증명] $a$가 무리수일 때, 직선 $y=ax$에 어떤 격자점이 존재한다고 가정하자. 양의 정수 $m,n$에 대해 $n=am$이라 하면 $a=\cfrac{n}{m}$이므로 $a$는 유리수가 되어 모순이 된다.

∴ $a$가 무리수이면 그래프 $y=ax$는 원점을 제외한 어떤 격자점도 지나지 않는다.

정리: 양의 정수 $a,\ b$가 $gcd(a,b)=1$일 때, $[\frac{a}{b}]+[\frac{2a}{b}]+\cdots+[\frac{(b-1)a}{b}]$의 값은 $\frac{(b-1)(a-1)}{2}$이다.

[증명] $(0,0),\ (b,0),\ (0,a),\ (b,a)$를 연결하는 직사각형 안의 격자점에 대해 $gcd(a,b)=1$이므로 두개의 점$(0,0),\ (b,a)$를 연결하는 직선 $y=\cfrac{ax}{b},\ (0<x<b)$ 위에는 지나가는 격자점이 존재하지 않는다. 따라서, 네 개의 점을 연결하는 직사각형 내부 격자점 개수의 절반이고 그 값은 $\cfrac{(b-1)(a-1)}{2}$이다.

예제: $[1\cdot\cfrac{301}{201}]+[2\cdot\cfrac{301}{201}]+\cdots+[401\cdot\cfrac{301}{201}]$의 값을 구하여라.

$gcd(201,301)=1$이고 네 점 $(0,0),\ (402,0),\ (0,602),\ (402,602)$로 만들어진 직사각형 내부의 격자점을 생각했을 때 직선 $y=\cfrac{301}{201}x$가 지나가는 격자점은 $(201,301)$가 존재한다. 그러므로 직선이 직사각형을 절반으로 나누었지만 $(201,301)$은 어느 영역에도 속하지 않으므로 내부 격자점을 계산할 때는 제외해야 한다. 따라서 해당 점을 제외한 절반의 격자점의 개수는 $\cfrac{(402-1)(602-1)-1}{2}$이다. 그리고 직선 위에 존재하는 $(201,301)$도 포함해야 하므로 1을 더하여 주어진 식의 값은 $\cfrac{(402-1)(602-1)-1}{2}+1=120501$이다.

예제: 세 직선 $y=\frac{2}{3}x+\frac{1}{2}\ (0\le x\le12),\ y=0,\ x=12$로 이루어진 삼각형에서 삼각형 안과 변 위에 있는 정수 좌표의 개수를 구하여라.

주어진 영역은 엄연히 따지만 삼각형은 아니지만, 적당히 내부 영역과 변 위에 존재하는 격자점의 개수를 구하는 것으로 이해하기로 하자.

직선 $y=\cfrac{2}{3}x+\cfrac{1}{2}\ (0\le x\le12)$은 주어진 격자평면 내에 교차하는 격자점이 존재하지 않으므로 격자평면을 정확히 절반으로 양분함을 알 수 있다. 문제에서 제시된 조건에 따라 변 위에 있는 정수 좌표의 개수를 포함하면 가로와 세로 변의 길이를 1씩 빼지 않아도 되기 때문에 가로 길이가 13, 세로 길이가 10인 격자점 수의 절반에 해당한다. 따라서 구하고자 하는 값은 $\cfrac{13\cdot10}{2}=65$이다.

작성에 도움이 된 자료

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

가우스 함수, [] 함수, 최대 정수 함수(Greatest integer function)의 정의

가우스 함수에 대한 명칭은 단순히 최대 정수 함수에 국한되지 않고 여러 곳에서 사용된다. 따라서, 혼동을 줄이기 위해 일반적으로 사용되는 명칭을 병기하였다.

실수 $x\in R$에 대하여 $x$를 넘지 않는 최대정수를 $[x]$라고 표기하고 함수 $[\ ]\ :\ R \rightarrow Z\ :\ x \rightarrow [x]$를 최대 정수 함수(Greatest integer function)이라 한다. []함수(Bracket function) 혹은 초등 교과과정에서는 가우스 함수라고도 부른다.

정리하자면 [ ]은 임의의 실수 $x\in R$에 대해 $x=[x]+\alpha,\ 0\le\alpha<1$로 표현할 수 있다.

예제 : 양의 정수 $n$이 $[\frac{n}{10}]+[\frac{n}{100}]+[\frac{n}{1000}]+[\frac{n}{10000}]=2016$을 만족하고 $n$의 각 자릿수의 합이 20일 때, $n$을 1000으로 나눈 나머지를 구하여라.

주어진 조건을 만족하려면 n이 5자리 정수여야 한다. 그러므로 표현하면 $n=\overline{a_4a_3a_2a_1a_0}$으로 나타낼 수 있고 각 자리수의 합이 20이므로 $a_0+a_1+a_2+a_3+a_4=20$이다. 전개식은 $a_4\cdot10^4+a_3\cdot10^3+a_2\cdot10^2+a_1\cdot10+a_0$이다. 주어진 식의 각 부분을 전개식을 기반으로 나타내면 아래와 같다.

$[\cfrac{n}{10}]=a_4\cdot10^3+a_3\cdot10^2+a_2\cdot10+a_1$

$[\cfrac{n}{100}]=a_4\cdot10^2+a_3\cdot10+a_2$

$[\cfrac{n}{1000}]=a_4\cdot10+a_3$

$[\cfrac{n}{10000}]=a_4$

따라서 주어진 방정식은 $a_4(1+10+10^2+10^3)+a_3(1+10+10^2)+a_2(1+10)+a_1$이고 괄호 안의 내용은 등비급수에 따라 바꾸면 $\cfrac{a_4(10^4-1)+a_3(10^3-1)+a_2(10^2-1)+a_1(10-1)}{10-1}$이 된다. 즉, $a_0$만 적절히 조정하면 양의 정수 $n$과 가 자릿수 합 20으로 나타낼 수 있다. 정리하면 $\cfrac{n-20}{10-1}=2016$이 되므로 $n=18164$가 되어 $n$을 1000으로 나눈 나머지는 164가 된다.

$n!$에 들어있는 소수 개수 구하는 방법

$a,\ b,\ q,\ r\in Z,\ b>0$에 대하여 $a=bq+r,\ 0\le r<b$라고 하자. 양변을 b로 나누면 $\cfrac{a}{b}=q+\cfrac{r}{b},\ 0\le \cfrac{r}{b}<1$이다. 즉 $[\cfrac{a}{b}]=q$가 됨을 알 수 있다. 따라서, $[\cfrac{a}{b}]$는 부등식 $b\cdot t\le a$를 만족하는 최대정수 $t$로도 표현할 수 있다.

정리: 자연수 $n\in N$과 소수 $p$에 대하여 $n!$ 안에 들어있는 소수 $p$의 개수는 $\sum_{k=1}^{\infty}[\frac{n}{p^k}]=[\frac{n}{p}]+[\frac{n}{p^2}]\cdots$이다.

[증명] 1부터 $n$까지의 자연수 중 $p$로 나누어지는 수는 $p,\ 2p,\ 3p,\ \cdots,\ tp$이고 정수 $t$는 $p\cdot t\le n$을 만족하는 최대 정수이다. 즉, $[\cfrac{n}{p}]=t$이다. 따라서, 1부터 $n$까지의 자연수 중 $[\cfrac{n}{p}]$개의 $p$인수가 존재한다. 그 다음 1부터 $n$까지의 자연수 중 $p^2$로 나누어지는 수는 $[\cfrac{n}{p^2}]$개 존재한다. 이를 계속 반복하면 1부터 n까지의 수에 대해 존재하는 모든 $p$인수의 개수를 구할 수 있다.

왜냐하면 지수 관점에서 곱셈이 이루어질 경우 덧셈으로 표현되고 첫 번째 과정은 말 그대로 적어도 $p^1$을 인수로 갖는 수의 개수이다. 두 번째 과정은 1부터 $n$까지 수에 대해 $p^2$로 나누어지는 수의 개수이므로 이전에 구했던 $p^1$을 가지고 있던 수 외에 $p^2$ 이상을 인수로 갖는 수만 포함하기 떄문에 이 과정을 반복하여 $[\cfrac{n}{p^2}]=0$이 되는 지점까지 반복하면 1부터 $n$까지의 수에 존재하는 모든 $p$인수를 구할 수 있다. 따라서 주어진 식은 마지막 항이 0이 되는 순간이 존재하므로 무한급수가 아니며 인수의 개수는 $\sum_{k=1}^{\infty}[\cfrac{n}{p^k}]$이다.

예제: $3042!$를 8진법으로 표현하였을 때, 마지막으로 연속되는 0의 개수는 몇 개인가?

8진법이므로 $2^3$으로 어디까지 묶이는 지 확인해야 한다. 주어진 값이 갖는 2의 개수를 구하면 $[\cfrac{3042}{2}]+[\cfrac{3042}{4}]+[\cfrac{3042}{8}]+\cdots+[\cfrac{3042}{2048}]$를 계산하면 되고 그 결과는 $1521+760+380+190+95+47+23+11+5+2+1$이 되어 3035가 된다. $[\cfrac{3035}{3}]=1011$이 되어 $3042!=k\cdot8^{1011},\ (k\nmid8)$으로 표현하면 8진법에서의 주어진 값이 갖는 연속되는 0의 개수는 1011이다.

• 위 과정에서 눈치챌 수 있겠지만 $[\cfrac{n}{p}]=t$라고 할 때 $[\cfrac{n}{p^2}]=[\cfrac{t}{p}]$가 성립하므로 계산의 복잡함을 줄일 수 있다.

예제: $n\in N$일 때, $2^n\ |\ (n+1)(n+2)\cdots(2n-1)2n$임을 증명하여라.

$(n+1)(n+2)\cdots(2n-1)2n=\cfrac{2n!}{n!}$으로 표현할 수 있다. 그리고 $n!$에 포함된 2의 개수는 $[\cfrac{n}{2}]+[\cfrac{n}{2^2}]+[\cfrac{n}{2^3}]+\cdots$이고 $2n!$에 포함된 2의 개수는 $[\cfrac{2n}{2}]+[\cfrac{2n}{2^2}]+[\cfrac{2n}{2^3}]+\cdots$이다. 각각을 정수 $r,\ s$라고 가정하면 $s=n+r$로 표현할 수 있고 $n=s-r$이 성립하는데 주어진 식에 따라 $2^{s-r}$은 $\cfrac{2n!}{n!}$의 인수임을 알 수 있다.

$\therefore\ 2^n\ |\ (n+1)(n+2)\cdots(2n-1)2n$이다.

정리: 임의의 실수 $x,\ y\in R$에 대하여, $[x+y]\ge[x]+[y]$이다.

[증명] $x\ge[x],\ y\ge[y]$이므로 $x+y\ge[x]+[y]$가 성립한다. 그리고 $[x+y]\ge[[x]+[y]]$또한 성립하지만 $[[x]+[y]]\in Z$이므로 $[x+y]\ge[x]+[y]$이다.

예제: n개의 연속된 자연수의 곱은 $n!$로 나누어 떨어짐을 증명하여라.

$n$개의 연속된 자연수 중 가장 큰 수를 $k$라 하자. 그러면 $n$개의 연속된 자연수의 곱은 $k(k-1)(k-2)\cdots(k-n+1)$이다.

달리 표현하면 $\cfrac{k(k-1)\cdots(k-n+1)(k-n)\cdots2\cdot1}{(k-n)(k-n-1)\cdots2\cdot1}=\cfrac{k!}{(k-n)!}$이다.

따라서 주어진 조건에 따르면 $\cfrac{k!}{n!(k-n)!}$이 정수임을 증명하면 된다.

주어진 식이 정수임을 증명하기 위해 $n!(k-n)!$이 갖는 임의의 소수 $p$에 대해 $k!$가 소수 $p$를 적어도 같거나 많이 가지면 된다.

• $k!$이 갖는 소수 $p$의 개수

  $[\cfrac{k}{p}]+[\cfrac{k}{p^2}]+[\cfrac{k}{p^3}]+\cdots$

• $n!$이 갖는 소수 $p$의 개수

  $[\cfrac{n}{p}]+[\cfrac{n}{p^2}]+[\cfrac{n}{p^3}]+\cdots$

• $(k-n)!$이 갖는 소수 $p$의 개수

  $[\cfrac{k-n}{p}]+[\cfrac{k-n}{p^2}]+[\cfrac{k-n}{p^3}]+\cdots$

$n!$과 $(k-n)!$이 갖는 소수 $p$의 개수를 합하면 $([\cfrac{n}{p}]+[\cfrac{k-n}{p}])+([\cfrac{n}{p^2}]+[\cfrac{k-n}{p^2}])+\cdots$이 되는데 보조정리를 이용하면 $[\cfrac{k}{p}]\ge[\cfrac{n}{p}]+[\cfrac{k-n}{p}]$이므로 적어도 $n!$과 $(k-n)!$이 갖는 임의의 소수 $p$에 대해 $k!$가 적어도 같거나 더 많이 가짐을 확인할 수 있기 때문에 $\cfrac{k!}{n!(k-n)!}$은 정수이다.

작성에 도움이 된 자료

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

• 이전 포스팅에서 선형 디오판토스 방정식에 대한 증명과 다양한 성질을 다루었기에 이번 포스팅에서는 관련 문제 유형에 따른 풀이 방법을 정리하고자 한다.
• 선형 디오판토스 방정식에 대한 특수해와 일반해를 구하는 방법은 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 수학경시 정수론, 장환수학, 임장환 저

• 이전 포스팅에서 선형 디오판토스 방정식에 대한 증명과 다양한 성질을 다루었기에 이번 포스팅에서는 관련 문제 유형에 따른 풀이 방법을 정리하고자 한다.
• 선형 디오판토스 방정식에 대한 특수해와 일반해를 구하는 방법은 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 수학경시 정수론, 장환수학, 임장환 저