투에 보조정리

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

정의

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

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

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

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

증명

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

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

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

${\displaystyle (x',y')\neq (x'',y'')}$

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

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

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

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

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

역사

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

같이 보기

• 파데 근사