Introduction

A Comparative Study of Continued Fraction and AI Methods for Polynomial Pell Equations

Liđan

Edin

Tatjana

Stanković

Third Gymnasium, Sarajevo, Bosnia and Herzegovina. Belgrade Business and Arts Academy of Applied Studies, Belgrade, Serbai.

In this paper, we provide an overview of the comparative analysis of solving the Pell’s equation x2 −Dy2 = 1 and the corresponding Pell’s type equation x2 − Dy2 = −1, where D is a given quadratic polynomial that is not a perfect square, by using tools based on generative artificial intelligence. The use of artificial intelligence today has a large and diverse application in society and science. It is important to carefully consider when, to what extent and whether to use artificial intelligence tools in some learning, research or analysis. Therefore, it is very meaningful to test AI tools in its wide range of applications. The use of artificial intelligence in mathematics is not a new form of research, but more modern and technologically improved with the respect to the previously used tools. In this paper, we compared the success of using AI in solving equations x2 − dy2 = 1 and x2 − dy2 = −1. The analysis clearly indicates that both tools still show a high degree of vagueness, a poor strategy and a uniform approach in the selection of methods for solving equations. Since ChatGPT and Gemini are one of the most available artificial intelligence tools a comparison of the solutions provided by these tools is conducted. In addition to the given artificial intelligence solutions, we also present classical mathematical solutions. The number of correct, incorrect and undetermined answers is used as a measurement for the success these tools in solving the mentioned equations.

Pell’s equationequations of Pell’s typegenerative AIChatGPTGemini

1Introduction

An algebraic equation of the form

x2 − Dy2 = C (1)

with two variables x and y, where D is a natural number and C is an integer, is called a Pell’s type equation. For C = 1, we get an algebraic equation (Diophantine equation) of the form

x2 − Dy2 = 1, (2)

which is called Pell’s equation.

When D = m2, where m is a natural number, i.e. when D is a perfect square, Pell’s equation (1) has the form

x2 − (my)2 = (x − my)(x + my) = 1, (3)

from which it follows

x − my = x + my = ±1. (4)

Based on equality (4) we obtain trivial solutions of the given equation, i.e. (x, y) = (±1, 0). Therefore, due to the triviality of the solution, the case of D as a perfect square will not be considered. In this paper, we exclusively consider the cases when D is not a perfect square [2], [3], [4] and [7].

The study of this form of algebraic equations has a long and rich mathematical history. This type of equation was among the first to be dealt with by Archimedes (287 BC - 212 BC), studying the livestock problem and setting it up gives the form of the equation. Besides him, Diophantus (200 BC - 284 BC) also dealt with this problem [2].

Indian mathematicians Brahmagupta [2] in the sixth century, and Jayadeva and Bhaskara II in the 11th century, gave a special contribution to the methodical study of Pell’s type algebraic equations. Brahmagupta gave a method for finding infinitely many solutions of a Pell’s type equation based on one known particular solution, while Jayadeva and Bhaskara II gave an algorithm for finding the first solution. Although the algebraic equation (2) was named after the English mathematician John Pell (1611-1685), its study and development cannot be directly linked to Pell. The name is thought to have originated from a misattribution of credit to Pell by Leonhard Euler (1707-1783). In the 17th and 18th centuries, Pierre de Fermat (1601-1665), Leonhard Euler and Joseph Louis Lagrange (1736-1813) stand out for finding methods for solving these equations, with Lagrange being the first to provide a rigorous proof of the proposed method. In this paper, we will focus on the analysis and method of solving Pell’s equation (2) and Pell’s type equation

x2 − Dy2 = −1 (5)

using the continued fraction method.

2Mathematical Background and the Continued Fraction

Method for Solving Pell’S Equations.

In this chapter, we will provide an overview of the basic mathematical theory of continued fractions and a description of the continued fraction method for solving Pell’s equation (2) and Pell’s type equation (5).

2.1Continued Fraction

Let α be a real number and let a0 be defined by a0 := ⌊α⌋. If a0 ̸= α let α = a0 + α 11 , then let a1 = ⌊α1⌋, for α1 > 1. For α1 ̸= a1, then α1 = a1 + α 12 , where α2 > 1 and further a2 = ⌊α2⌋. We can keep repeating this process until we get that αn = an, n ∈ N. When αn = an, n ∈ N then the relation (6) holds [3], [7].

[a0, a1, a2, ..., an] = a0 + , (6) a1 + a2 + .. 1

an−1 + an

The relation (6) represents a finite continued fraction written in a simpler form [a0, a1, a2, ..., an]. If α ̸= an for each n ∈ N the relation (6) becomes

[a0, a1, a2, . . . , an, . . .] = a0 + , (7) a1 + a2 + .. 1

an−1 + an +

Expension into a simple continued fraction is finite in the case when α is a rational number, and its expansion into a continued fraction can also be obtained using the Euclidean algorithm, where a0, a1, a2, . . . represent the quotients from the Euclidean algorithm applied to the numerator and denominator of a given rational number. Every rational number pk = [a0, a1, a2, . . . , ak] (8) qk for k ≤ n is called the k-th convergent of [a0, a1, a2, . . . , an]. The numerator pk and the denominator qk, the k convergent expansion into a continued fraction of [a0, a1, a2, . . . , an] satisfy the following recursive relations pk = akpk−1 + pk−2, p0 = a0, p1 = a0a1 + 1, (9) qk = akqk−1 + qk−2, q0 = 1, q1 = a1. (10) for k ∈ {2, 3, 4, . . . , n}. In the case when α is an irrational number, the expansion into a continued fraction is infinite, i.e. [a0, a1, a2, . . . , an, . . .], and the values a0, a1, a2, . . . , an in the relations (6) and (7) are called partial quotients. In this paper, we will specifically consider the case of periodic infinite continued fractions. A continued fraction [a0, a1, a2, . . . , an, . . .] is periodic if there are l ∈ N and m ∈ N such that ak = ak+l, for each k ≥ m. Then we label l as the length of the period of the continued fraction with notation α = [a0, a1, a2, . . . , am−1, am, am+1, . . . , am+l−1], (11) where am, am+1, . . . , am+l−1 means that the numbers am, am+1, . . ., am+l−1 are the one that are repeating. For m = 0, we will get a purely periodic continued fraction, i.e. [a0, a1, a2, . . . , al−1], [3], [7].

By quadratic irrationality we mean every irrational number α of the form a + b√d, where a, b ∈ Q and d ∈ N, d = ̸ □ that satisfies the given quadratic equation with rational coefficients. If α is a quadratic irrationality then the expansion into a continued fraction is periodic and vice versa. The proof of this statement was given by Euler and Lagrange [7].

For a given quadratic irrationality α = s0+ t0√d , where s0, t0 ∈ Z, t0 ̸= 0, t0|(d − s2 0), d ∈ N and d ∈ N. For i > 0, the partial quotients are obtained as follows:

d − s2 i+1 si+1 + √d ai = ⌊αi⌋, si+1 = aiti − si ti+1 = αi+1 = (12) ti ti+1 We will use this algorithm in expanding into a continued fraction while solving Pell’s equation (2) and Pell’s type equation (5).

2.2The Continued Fraction Method for Solving Pell’S Equations

There are a number of different methods for solving Pell and Pell’s type equations: continued fraction method, recursive method, Euler method, unimodular plane transformation method. One of the methods is the continued fraction method, which we will consider in this paper mathematically and through the application of artificial intelligence. The first step in solving algebraic equations of the form (2) and (5) is to find the expansion of the number or expression into a simple continued fraction as it is described in the previous section. Due to the symmetry of Pell’s equation, it is sufficient to observe the solutions only in the set of natural numbers, i.e. if the ordered pair (x, y), x, y ∈ N is a solution of the equation (2), then its solutions are also (x, −y), (−x, y) and (−x, −y). It is obvious that one solution is (1, 0) and due to its triviality we will not consider it. By the fundamental solution (x1, y1) we mean a non-trivial solution where x1 and y1 are the smallest natural numbers such that the equation (2) is satisfied, and we write it as follows

x1 + y1√D. (13)

Based on the fundamental solution (13) of the equation (2) we determine all other solutions in the set of natural numbers using the relation

xn + yn√D = (x1 + y1√D)n ∈ N.

As n ∈ N it is obvious that the equation (2) has infinitely many solutions. The given relation is stated as Theorem 10.11 in [3], where its proof can be found. Based on Theorem 10.12 in [3] the value of the trivial solution becomes obvious when finding all natural solutions of Pell’s equation (2) using relations

xn+2 = 2x1xn+1 − xn, (14) yn+2 = 2x1yn+1 − yn, n ≥ 0. (15)

and using the fundamental solution. In this way, a series of solutions is obtained in ascending order [3], [7].

It is obvious that the role of the fundamental solution in finding all solutions is significant. The key moment in solving Pell’s equation (2) is to find the fundamental solution. The question arises how to determine the fundamental solution. One of the most effective ways is to establish a connection between the solution of Pell’s equation (2) and the Diophantine approximation of the number or expression √D, where D is not a perfect square.

The solutions of Pell’s and the Pell’s type equation depend on the length of the period l of the expansion of the number or expression √D into a continued fraction (Theorem 10.20 in [3]). Each Pell’s equation (2) is also given with a relation

(x, y) = (pnl−1, qnl−1), n ∈ N, (16)

if the length of the period l is an even number where the fundamental solution is (pl−1, ql−1) i.e. or with the relation

(x, y) = (p2nl−1, q2nl−1), n ∈ N, (17)

if the length of the period l is an odd number, where fundamental solution of the equation (2) (p2l−1, q2l−1). Unlike Pell’s equation, each Pell’s type equation does not always have a solution. In the case when the length of the period l is an even number, the Pell equation (5) will not have a solution, and in the case when the length of the period l is an odd number, the solutions are given by

(x, y) = (p(2n−1)l−1, q(2n−1)l−1). (18)

Especially the Pell’s type equation (5) will not have a solution in the case where D ≡ 3 mod 4, in [3], [7].

3Discussion and Analysis of the Results

In this paper, we investigated how AI, specifically using ChatGPT and Gemini, solves and investigates polynomial Pell equations. For this research, we chose seven carefully selected polynomial expressions for D, which we used to form the Pell equations. The selection was not random but carefully and precisely chosen. The examples were chosen based on the working principles of generative AI. To investigate the operation of methods and modes of operation, we have chosen the following polynomial Pell equations.

x2 − ((89t − 44)2 + 110t − 54)y2 = 1, (19) x2 − ((70t + 1)2 + 58t + 1)y2 = 1, (20) x2 − ((169t + 1)2 + 140t + 1)y2 = 1, (21) x2 − ((29t + 1)2 + 58t + 1)y2 = 1, (22) x2 − (a2 − 4)y2 = 1, a > 3, a odd, (23) x2 − (a2 + 4)y2 = 1, a > 1, a odd, (24) x2 − ((na)2 − a)y2 = 1, n ∈ N, a > 1. (25)

The basic Pell’s equation using the method previously described in section 2 immediately offers a solution to equation (4) whose analysis and method of solution are also given in the discussion of this paper for selected problems.

Solving equations of the form x2 − Dy2 = ±1 is formally carried out entirely algorithmically. Solving the mentioned equations is carried out in several clearly defined and determined steps, which we described in the previous section. Below, we provide an overview of the mathematical solution, and AI tested on ChatGPT and Gemini. The first step of solving x2 − Dy2 = ±1 is the determination of the development into a simple continued fraction of the number √D. In Table 1, we provide an overview of the mathematical solutions [7] and ChatGPT.

Table 1

Review the math solution and the solution given by ChatGPT for developing √D into a simple continued fraction.