투에 보조정리

수론에서 투에 보조정리(-補助定理, 영어: Thue's lemma)는 일차 합동 방정식이 다소 작은 해를 가질 충분 조건을 제시하는 정리이다. 비둘기집 원리의 수론에서의 한 가지 응용이다. 페르마 두 제곱수 정리의 증명에 사용된다.

정의

양의 정수 $n$이 정수 $a$와 서로소라고 하자. 투에 보조정리에 따르면, 다음을 만족시키는 정수 $x,y$가 존재한다.^:264-265

• $0<|x|,|y|\leq {\sqrt {n}}$
• $ax\equiv y{\pmod {n}}$

혹자^:43는 다음과 같은 명제를 투에 보조정리로 삼는다. 정수 $n,a,x^{*},y^{*}$가 $0<y^{*}\leq n<x^{*}y^{*}$라고 하자. 그렇다면, 다음을 만족시키는 정수 $x,y$가 존재한다.

• $0<|x|<x^{*}$
• $0<|y|<y^{*}$
• $ax\equiv y{\pmod {p}}$

증명

다음과 같은 집합을 생각하자.^:264-265

$\{ax-y\colon 0\leq x,y\leq \lfloor {\sqrt {n}}\rfloor ,\;x,y\in \mathbb {Z} \}$

0과 $\lfloor {\sqrt {n}}\rfloor$ 사이의 두 정수의 쌍은 $(\lfloor {\sqrt {n}}\rfloor +1)^{2}$개이며, $(\lfloor {\sqrt {n}}\rfloor +1)^{2}>n$이므로, 다음과 같은 정수 $0\leq x',y',x'',y''\leq \lfloor {\sqrt {n}}\rfloor$가 존재한다.

$(x',y')\neq (x'',y'')$

$ax'-y'\equiv ax''-y''{\pmod {n}}$

즉, $x=x'-x''$, $y=y'-y''$라고 하면, 다음이 성립한다.

$0\leq |x|,|y|\leq {\sqrt {n}}$

$ax\equiv y{\pmod {n}}$

만약 $x=0$이거나 $y=0$이라면, 위와 같은 합동과 $a,n$의 서로소에 따라 $x=y=0$이다. 이는 $(x',y')\neq (x'',y'')$에 모순이다. 따라서, $|x|,|y|>0$이다.

역사

노르웨이의 수학자 악셀 투에가 처음 증명하였다.

같이 보기

• 파데 근사

참고 문헌

• 오정환, 이준복, 《정수론》, 2003