トゥエの補題

モジュラー算術において、チューの補題は、おおよそ、すべてのモジュラー整数は、分子と分母の絶対値が法の平方根を超えないような「モジュラー分数」で表すことができる、と述べている。

より正確には、 m > 1の任意の整数 のペア( a , m )に対して、 X ≤ m < XYを満たす2 つの正の整数XとYが与えられたとき、次の2 つの整数xとyが存在する。

${\displaystyle ay\equiv x{\pmod {m}}}$

そして

${\displaystyle |x|<X,\quad 0<y<Y.}$

通常、XとYはmの平方根より大きい最小の整数に等しいとされますが、一般形が便利な場合もあり、一意性定理（下記）を述べやすくなります。^{[ 1 ]}

最初の証明は、鳩の巣原理を用いたアクセル・トゥー^{[ 2 ]によるものとされている[ 3 ]}。

チューの補題は、 m を4 を法として 1 と合同な素数pとし、a をa ² + 1 ≡ 0 mod pを満たすものとすることで、 2 平方数の和に関するフェルマーの定理を証明するために使用できる。このようなaの存在は、ウィルソンの定理から導かれる。^{[ 4 ]}

一般に、チューの補題によって存在が主張される解は一意ではありません。例えば、a = 1 の場合、 XとYが小さすぎない限り、 ( x , y ) = (1, 1), (2, 2), (3, 3), ...のように複数の解が存在します。したがって、 yとmが互いに素である場合に限り、a が法mで合同となる有理数⁠ x / y ⁠の一意性が期待できます。しかしながら、この有理数は必ずしも一意である必要はありません。例えば、m = 5、a = 2、X = Y = 3の場合、2 つの解が存在します。

${\displaystyle 2a+1\equiv -a+2\equiv 0{\pmod {5}}}$。

しかし、XとYが十分に小さい場合、解が存在するならば、それは一意である。より正確には、上記の表記法では、

${\displaystyle 2XY<m,}$

そして

${\displaystyle ay_{1}-x_{1}\equiv ay_{2}-x_{2}\equiv 0{\pmod {m}}}$、

と

${\displaystyle \left|x_{1}\right|<X,\quad \left|y_{1}\right|<Y,}$

そして

${\displaystyle \left|x_{2}\right|<X,\quad \left|y_{2}\right|<Y,}$

それから

${\displaystyle {\frac {x_{1}}{y_{1}}}={\frac {x_{2}}{y_{2}}}.}$

この結果は、分子と分母の境界がわかっている有理数を計算するためにモジュラー算術を使用することを可能にする有理数再構成の基礎となる。 ^{[ 5 ]}

証明は比較的簡単だ。各合同式を他のy _iで掛けて引き算すると、

${\displaystyle y_{2}x_{1}-y_{1}x_{2}\equiv 0{\pmod {m}}.}$

これらの仮説は、各項の絶対値がXY < m / 2より小さいことを示唆しており、したがってそれらの差の絶対値はmより小さい。これは、${\displaystyle y_{2}x_{1}-y_{1}x_{2}=0}$したがって、このような結果となる。

トゥエの補題の元の証明は、解を計算するための高速な方法を提供しないという意味で効率的ではありません。拡張ユークリッドアルゴリズムにより、ユークリッドアルゴリズムと同じ計算複雑度を持つ効率的なアルゴリズムにつながる証明を提供できます。^{[ 6 ]}

より正確には、Thueの補題に現れる2つの整数mとaが与えられた場合、拡張ユークリッドアルゴリズムは、次の3つの整数列( t _i )、 ( x _i )、( y _i )を計算します。

${\displaystyle t_{i}m+y_{i}a=x_{i}\quad {\text{for }}i=0,1,...,}$

ここで、x _iは非負で厳密に減少します。求める解は、符号を除いて、x _i < Xとなる最初のペア( x _i , y _i )です。

• パデ近似法は、テイラー級数を有理関数で近似するための同様の理論である。