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.


F solvePell(n)
   V x = Int(sqrt(n))
   V (y, z, r) = (x, 1, x << 1)
   BigInt e1 = 1
   BigInt e2 = 0
   BigInt f1 = 0
   BigInt f2 = 1
   L
      y = r * z - y
      z = (n - y * y) I/ z
      r = (x + y) I/ z
 
      (e1, e2) = (e2, e1 + e2 * r)
      (f1, f2) = (f2, f1 + f2 * r)
 
      V (a, b) = (f2 * x + e2, f2)
      I a * a - n * b * b == 1
         R (a, b)
 
L(n) [61, 109, 181, 277]
   V (x, y) = solvePell(n)
   print(‘x^2 - #3 * y^2 = 1 for x = #27 and y = #25’.format(n, x, y))