29 lines
718 B
Text
29 lines
718 B
Text
require "bignum"
|
|
local fmt = require "fmt"
|
|
|
|
local function solve_pell(n)
|
|
n = bigint.new(n)
|
|
local x = bigint.sqrt(n)
|
|
local y = x
|
|
local z = bigint.one
|
|
local r = x * 2
|
|
local e1 = bigint.one
|
|
local e2 = bigint.zero
|
|
local f1 = bigint.zero
|
|
local f2 = bigint.one
|
|
while true do
|
|
y = r * z - y
|
|
z = (n - y * y) / z
|
|
r = (x + y) / z
|
|
e1, e2 = e2, r * e2 + e1
|
|
f1, f2 = f2, r * f2 + f1
|
|
local a = e2 + x * f2
|
|
local b = f2
|
|
if (a * a - n * b * b == bigint.one) then return {a, b} end
|
|
end
|
|
end
|
|
|
|
for {61, 109, 181, 277} as n do
|
|
local [a, b] = solve_pell(n)
|
|
fmt.print("x² - %3dy² = 1 for x = %-21s and y = %s", n, a, b)
|
|
end
|