Pellova rovnice - algoritmus řešení
Ahoj všem,
Pellova rovnice je druh Diofantické rovnice a má tvar x^2 - D*y^2 = 1, přičemž se hledá netriviální řešení (dvojice x, y) v oboru celých čísel. Konstanta D nesmí být druhou mocninou nějakého celého čísla. Triviální řešení x=1, y=0 se nepočítá.
Řešení je nekonečně mnoho, my však hledáme první řešení (nejmenší x) a pak případně další řešení.
Vypadá to vědecky, ale někde se to učí již na základních školách. Ruční postup je známý (a pracný) a vychází z rozkladu čísla "odmocnina(D)" na řetězové zlomky. Na internetu je o tom hodně materiálu, dokonce i weby s javovskými applety, které to počítají.
Algoritmus na řešení jsem však nenašel (má to být upravený Eukleidův algoritmus pro výpočet NSD - největšího společného dělitele dvou čísel, nebo nějak podobný). Vím, že výpočet s ním je jednoduchý a rychlý.
Umí někdo popsat a vysvětlit hledaný algoritmus? Díky.
Pellova rovnice je druh Diofantické rovnice a má tvar x^2 - D*y^2 = 1, přičemž se hledá netriviální řešení (dvojice x, y) v oboru celých čísel. Konstanta D nesmí být druhou mocninou nějakého celého čísla. Triviální řešení x=1, y=0 se nepočítá.
Řešení je nekonečně mnoho, my však hledáme první řešení (nejmenší x) a pak případně další řešení.
Vypadá to vědecky, ale někde se to učí již na základních školách. Ruční postup je známý (a pracný) a vychází z rozkladu čísla "odmocnina(D)" na řetězové zlomky. Na internetu je o tom hodně materiálu, dokonce i weby s javovskými applety, které to počítají.
Algoritmus na řešení jsem však nenašel (má to být upravený Eukleidův algoritmus pro výpočet NSD - největšího společného dělitele dvou čísel, nebo nějak podobný). Vím, že výpočet s ním je jednoduchý a rychlý.
Umí někdo popsat a vysvětlit hledaný algoritmus? Díky.