Pell's equation   (also called the Pell–Fermat equation)   is a   Diophantine equation   of the form:

   x2   -   ny2   =   1  
with integer solutions for   x   and   y,   where   n   is a given non-square positive integer.



Task requirements

   find the smallest solution in positive integers to Pell's equation for   n = {61, 109, 181, 277}.


See also

   Wikipedia entry: Pell's equation.


func solve_pell(n) {
 
    var x = n.isqrt
    var y = x
    var z = 1
    var r = 2*x
 
    var (e1, e2) = (1, 0)
    var (f1, f2) = (0, 1)
 
    loop {
 
        y = (r*z - y)
        z = floor((n - y*y) / z)
        r = floor((x + y) / z)
 
        (e1, e2) = (e2, r*e2 + e1)
        (f1, f2) = (f2, r*f2 + f1)
 
        var A = (e2 + x*f2)
        var B = f2
 
        if (A**2 - n*B**2 == 1) {
            return (A, B)
        }
    }
}
 
for n in [61, 109, 181, 277] {
    var (x, y) = solve_pell(n)
    printf("x^2 - %3d*y^2 = 1 for x = %-21s and y = %s\n", n, x, y)
}