Integer Solutions to Quadratic Diophantine Equations using Efficient Algorithms with Elementary and Quadratic Ring Methods

Abstract

In this paper, we study the solvability of quadratic Diophantine equations x² - Dy² =N, where x and y are unknown integers, and D is a positive integer that is a square free and N is a nonzero integer. We use elementary and quadratic ring methods to find integer solutions of these equations. These methods involve concepts like units, fundamental units, norms, and conjugates in quadratic rings. We propose efficient algorithms to solve the equations for cases where |N| > \sqrt{D} and |N| < \sqrt{D}. The algorithms include the continued fraction algorithm, periodic quadratic algorithm, Lagrange-Matthew-Mollin algorithm, and brute-force search. These algorithms can be implemented in programming languages. Finally, we compare the algorithms and analyze their time complexity.