# Statement

onsider quadratic Diophantine equations of the form:

x^{2} – Dy^{2} = 1

For example, when D=13, the minimal solution in x is 6492 – 131802 = 1.

It can be assumed that there are no solutions in positive integers when D is square.

By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:

3^{2} – 2*2^{2} = 1

2^{2} – 3*1^{2} = 1

9^{2} – 5*4^{2} = 1

5^{2} – 6*2^{2} = 1

8^{2} – 7*3^{2} = 1

Hence, by considering minimal solutions in x for D 7, the largest x is obtained when D=5.

Find the value of D<=1000 in minimal solutions of x for which the largest value of x is obtained.

# Solution

The solution came out after reading and understanding this documents:

Wikipedia Pell's Equation

Wikipedia Convergent in continued fractions

Wikipedia Fundamental Recurrence Formulas

It's a basic implementation of all stated in those three articles.

def continued_fraction(n): m = 0 d = 1 a = a_0 = int(n ** 0.5) triple_set = list() while (m, d, a) not in triple_set: triple_set.append((m, d, a)) tmp_m = d * a - m tmp_d = (n - tmp_m ** 2) // d tmp_a = int((a_0 + tmp_m) / tmp_d) a = tmp_a d = tmp_d m = tmp_m triple_set.append((m, d, a)) return triple_set def min_x(n): resolution = continued_fraction(n) restart_index = resolution.index(resolution[-1]) index = min(2, len(resolution) - 1) stored_x = [] stored_y = [] x = resolution[0][2] y = 1 if x ** 2 - n * (y ** 2) == 1: return x stored_x.append(x) stored_y.append(y) x = resolution[0][2] * resolution[1][2] + 1 y = resolution[1][2] while x ** 2 - n * (y ** 2) != 1: stored_x.append(x) stored_y.append(y) x = resolution[index][2] * x + 1 * stored_x[-2] y = resolution[index][2] * y + 1 * stored_y[-2] index += 1 if index == len(resolution): index = restart_index + 1 return x if __name__ == '__main__': max_x = 0 result = 0 for d in filter(lambda d: int(d ** 0.5) ** 2 != d, range(1, 1001)): tmp = min_x(d) if tmp > max_x: max_x = tmp result = d print("The result is:", result)

The Python file is available for download here.