Dobré aproximace
Pomocí teorie dobrých aproximací popsané v textu se poměrně snadno odvodí
následující věta o algoritmu hledání dobrých aproximací reálného čísla:
Věta. Nechť 9 G E. Generujme rekurentně celá čísla pn, qn, an; nejprve
položme
Po = 1,
Ví = [0],
Qo = 0,
qi = l.
Pak pro libovolné přirozené n pokračujme takto: jestliže qn9 = pn, generování
končí, jinak položíme
\qn-i0 -- Pn-l\
a dále
\qn9 - pn
Pn+l -- dnPn + Pn-1,
Qn+1 Q"nQn * Qn-- 1 ˇ
Pak všechny dobré aproximace čísla 9 jsou právě čísla -- pro n > 1, je-li
a\ > 1, resp. pro n > 2, je-li CL\ = 1. Navíc platí
(-l)n
(qn9-pn) < 0,
Qn+lPn - QnPn+l = ( - I ) " Pomocí
konstrukce dobrých aproximací nyní dokážeme nepatrně slabší
variantu užívaného případu Lehmannovy věty pro r = [v7
^]Věta.
Nechť N je liché, N = pq, kde p < q jsou prvočísla. Pak existují
celá čísla x, y, k tak, že
(1) x2
-y2
= AkN
(2) 2\k
l<k< [VŇ\;
x = 1 (mod 2); 2\k x = k + N (mod4);
(3) 0 < x2
- AkN < N
ˇffi\"
1
Důkaz. Je-li p = q, věta platí pro x = 2p, y = 0, k = 1, neboť
N = p2
= 1 (mod 4),
a tedy k + N = 2 = 2p (mod 4). Nechť dále p < q. Sestrojme posloupnost
dobrých aproximací -- čísla 9 = - a zvolme n tak, aby pnqn < \/Ň <
Pn+iQn+i- To lze, protože algoritmus výpočtu dobrých aproximací se zastaví
až pro pn = q, qn = p, kdy je přesně dosaženo 9. Protože 9 > 1, jsou čísla pn,
Pn+i, Qn, Qn+i kladná. Položme
k = pnqn, x = 'ppn + qqn, y = ppn- qqnZřejmě
x2
-- y2
= 4:ppnqqn = 4kN, odkud plyne (1). Jestliže 2\k, pak je právě
jedno z čísel pn a qn sudé (vždyť jsou nesoudělná), a protože p a q jsou lichá,
je x liché. Je-li naopak k liché, jsou pn a qn lichá, odkud
qnpx = qnp2
pn + qq2
np = qnpn + qp = k + N (mod 4)
a ze sudosti x plyne qnpx = x (mod 4), celkem tedy (2). Z teorie dobrých
aproximací
Pn q
odkud
Dále
odkud
qn p
\y\ = \PPn - qqn\ =
<
Pr,
qn
Pn+i q
qn,qn+i
_ q
p
i
<
ˇpqn <
P
qn+i
Pn+1 qn+1
qn+\ P
Pn+i q
2 :
qn+i
jinými slovy
q
Pn+l
q
p qn+i p
qn+i i_
J^ qn+l Pn+l
qqn+i
i
qqn+i p
Qn + l
qqn+i
Vynásobením levé nerovnosti číslem ^ ^ dostaneme
qn+l Pn+iqn+l 1
pq
Pn+iqn+l
p* pq pq N
Ovšem pn+iqn+i > \^Ň > [\/Ň], tedy pn+iqn+i -- 1 > [v^ŽV]- Dohromady
x AkN = y2
<
p" N
<
qn+l Pn+iq-n+l
<
N
N]
a platí i (3).
2
Poznámka. Odhadneme-li x + 2ykŇ > AykŇ pomoci (3) ve výrazu
z-- x2
- AkN
x - 2VkN = = = <
N
x 2VkŇ [^Ň] AVkŇ 4[v/
ÍV] V k
dostáváme nepatrně slabší odhad, než je odhad uvedený v Lehmannově větě
v textu:
i ÍW
x -2VkN<
4([^]V] + 1) V k '
avšak i námi získaný odhad postačí k odvození udané časové náročnosti
Lehmannova algoritmu.
3