ディリクレの近似定理

この定理は鳩の巣原理の結果である。この結果を証明したペーター・グスタフ・ルジューヌ・ディリクレは、他の文脈（例えば、ペル方程式）でも同じ原理を使用し、原理に（ドイツ語で）名前を付けることでその使用を普及させたが、教科書的な用語としての地位は後になってからである。^{[ 2 ]}この方法は同時近似にも拡張される。^{[ 3 ]}

証明の概要：${\displaystyle \alpha }$無理数であり、${\displaystyle N}$整数とする。${\displaystyle k=0,1,...,N}$私たちは書くことができます${\displaystyle k\alpha =m_{k}+x_{k}}$そのため${\displaystyle m_{k}}$は整数であり、${\displaystyle 0\leq x_{k}<1}$区間を分割することができます${\displaystyle [0,1)}$の中へ${\displaystyle N}$より小さな測定間隔${\displaystyle {\frac {1}{N}}}$.今、私たちは${\displaystyle N+1}$数字${\displaystyle x_{0},x_{1},...,x_{N}}$そして${\displaystyle N}$区間。したがって、鳩の巣原理によ​​り、少なくとも2つは同じ区間に属します。それらを${\displaystyle x_{i},x_{j}}$そのため${\displaystyle i<j}$。 今：

${\displaystyle |(ji)\alpha -(m_{j}-m_{i})|=|j\alpha -m_{j}-(i\alpha -m_{i})|=|x_{j}-x_{i}|<{\frac {1}{N}}}$

両辺を${\displaystyle ji}$結果として、以下のようになります。

${\displaystyle \left|\alpha -{\frac {m_{j}-m_{i}}{ji}}\right|<{\frac {1}{(ji)N}}\leq {\frac {1}{\left(ji\right)^{2}}}}$

そして私たちはその定理を証明した。

ディリクレの近似定理のもう一つの簡単な証明は、ミンコフスキーの定理を集合に適用することに基づいている。

${\displaystyle S=\left\{(x,y)\in \mathbb {R} ^{2}:-N-{\frac {1}{2}}\leq x\leq N+{\frac {1}{2}},\vert \alpha x-y\vert \leq {\frac {1}{N}}\right\}.}$

量の${\displaystyle S}$より大きい${\displaystyle 4}$ミンコフスキーの定理は、整数座標を持つ非自明な点の存在を確立する。この証明は、集合を考えることで、同時近似に自然に拡張される。

${\displaystyle S=\left\{(x,y_{1},\dots ,y_{d})\in \mathbb {R} ^{1+d}:-N-{\frac {1}{2}}\leq x\leq N+{\frac {1}{2}},|\alpha _{i}x-y_{i}|\leq {\frac {1}{N^{1/d}}}\right\}.}$

アドリアン＝マリー・ルジャンドルは、著書『数の理論に関する試論』（1798年）の中で、有理数が与えられた実数の単純な連分数の収束となるための必要十分条件を導き出しました。 ^{[ 4 ]}この基準の帰結は、連分数の研究においてしばしばルジャンドルの定理と呼ばれ、次のようになります。 ^{[ 5 ]}

定理。αが実数で、 p、qが正の整数である場合、${\displaystyle \left|\alpha -{\frac {p}{q}}\right|<{\frac {1}{2q^{2}}}}$すると、p / qはαの連分数の収束値となる。

この定理は、 RSA暗号プロトコルの多項式時間攻撃であるウィーナー攻撃の基礎を形成しており、これは不適切な公開鍵と秘密鍵の選択によって発生する可能性があります（具体的には、公開鍵n = pqの素因数がp < q < 2 pを満たし、秘密鍵d が(1/3) n ^1/4未満である場合にこの攻撃は成功します）。^{[ 7 ]}