투에 보조정리

틀:위키데이터 속성 추적 수론에서 투에 보조정리(-補助定理, 틀:Llang)는 일차 합동 방정식이 다소 작은 해를 가질 충분 조건을 제시하는 정리이다. 비둘기집 원리의 수론에서의 한 가지 응용이다. 페르마 두 제곱수 정리의 증명에 사용된다.

정의

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

• $0<|x|,|y|\le \sqrt{n}$
• $ax\equiv y(\mathrm{mod}n)$

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

• $0<|x|<x^{*}$
• $0<|y|<y^{*}$
• $ax\equiv y(\mathrm{mod}p)$

증명

다음과 같은 집합을 생각하자.틀:Rp

$\{ax-y:0\le x,y\le \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\le x^{\prime },y^{\prime },x^{″},y^{″}\le \lfloor \sqrt{n}\rfloor$가 존재한다.

$(x^{\prime },y^{\prime })\ne (x^{″},y^{″})$

$a{x}^{\prime }-y^{\prime }\equiv a{x}^{″}-y^{″}(\mathrm{mod}n)$

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

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

$ax\equiv y(\mathrm{mod}n)$

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

역사

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

같이 보기

• 파데 근사

참고 문헌

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