Quadratic Form Representations via Generalized Continuants

Charles Delorme^{1} Laboratoire de Recherche en Informatique Bâtiment 650 Université Paris Sud 91405 Orsay Cedex France

                       cd@lri.fr

Guillermo Pineda-Villavicencio Centre for Informatics and Applied Optimisation Federation University Australia Mount Helen, Victoria 3350 Australia

                 work@guillermo.com.au

Abstract

H. J. S. Smith proved Fermat’s two-square theorem using the notion of palindromic continuants. In this paper we extend Smith’s approach to proper binary quadratic form representations in some commutative Euclidean rings, including rings of integers and rings of polynomials over fields of odd characteristic. Also, we present new deterministic algorithms for finding the corresponding proper representations.

1Deceased.

1 Introduction

Fermat’s two-square theorem is without doubt a remarkable result. Many proofs of the theorem have been provided; see, for instance, [28, 11, 21, 4, 1]. It is also true that most proofs have much in common, for instance, Smith’s proof is very similar to Hermite’s [11], Serret’s [21], and Brillhart’s [1].

Let us recall here, for convenience, suitable definitions of Euclidean rings and continuant.

Definition 1 ([12, Section 2.15]). Euclidean rings are rings R with no zero divisors which are endowed with a Euclidean function N from R to the nonnegative integers such that for all τ_{1}, τ_{2} ∈ R with τ_{1} ≠ 0, there exist q, r ∈ R such that τ_{2} = qτ_{1} + r and N(r) < N(τ_{1}).

Well-known examples of Euclidean rings include the integers with N(u) = |u|, and the polynomials over a field with N(0) = 0 and N(P) = 2^{degree(P)}. In this paper we only consider Euclidean commutative rings.

Definition 2 (Continuants in arbitrary rings, [9, Sec. 6.7]). Let Q be a sequence of elements q_{1}, q_{2}, …, q_{n} of a ring R. We associate with Q an element [Q] of R via the following recurrence formula

[ ] = 1, [q_{1}] = q_{1}, [q_{1}, q_{2}] = q_{1}q_{2} + 1, and
[q_{1}, q_{2}, …, q_{n}] = [q_{1}, …, q_{n−1}]q_{n} + [q_{1}, …, q_{n−2}], if n ≥ 3.

The value [Q] is called the continuant of the sequence Q.

Properties of continuants in commutative rings are given by Graham et al. [9, Sec. 6.7].

Lemma 3 (Carroll’s identity, [8]). Let C be an n × n matrix in a commutative ring. Let C_{i_{1},...,i_{s};j_{1},...,j_{s}} denote the matrix obtained from C by omitting the rows i_{1}, …, i_{s} and the columns j_{1}, …, j_{s}. Then

det(C) det(C_{i,j;i,j}) = det(C_{i;i}) det(C_{j;j}) − det(C_{i;j}) det(C_{j;i})

where det(M) denotes the determinant of a matrix M, and the determinant of the 0 × 0 matrix is 1 for convenience.

The use of Carroll’s identity provides two more properties.

P–1 [q_{1}, q_{2}, …, q_{n}][q_{2}, …, q_{n−1}] = [q_{1}, …, q_{n−1}][q_{2}, …, q_{n}] + (−1)^{n} (n ≥ 2).

P–2 [q_{1}, q_{2}, …, q_{n}] = [q_{n}, …, q_{2}, q_{1}].

Given two elements m_{1} and m_{2} in a Euclidean ring R, the Euclidean algorithm outputs a sequence (q_{1}, q_{2}, …, q_{n}) of quotients and a greatest common divisor (gcd) h of m_{1} and m_{2}. A sequence of quotients given by the Euclidean algorithm is called a continuant representation of m_{1} and m_{2} as we have the equalities m_{1} = [q_{1}, q_{2}, …, q_{n}]h and m_{2} = [q_{2}, …, q_{n}]h, unless m_{2} = 0.

A representation of an element m by the form Q(x, y) = αx^{2} + γxy + βy^{2} is called proper if gcd(x, y) = 1. In this paper we are mostly concerned with proper representations.

For us the quadratic forms f(x, y) = ax^{2} + bxy + cy^{2} and g(x, y) = Ax^{2} + Bxy + Cy^{2} are equivalent if there is a 2 × 2 matrix M = (a_{ij}) with determinant 1 such that g(x, y) = f(a_{11}x + a_{12}y, a_{21}x + a_{22}y). For equivalent forms f and g it follows that an element m is (properly) represented by f iff m is (properly) represented by g.

1.1 Our work

This paper can be considered as a follow-up to our earlier paper [7]. In that paper we studied the use of continuants in some integer representations (e.g., sums of four squares) and sums of two squares in rings of polynomials over fields of characteristic different from 2. Here we deal with the following problems. We let u denote a unit in a ring; the ring under consideration will become clear from the context.

Problem 4 (From x^{2} + gxy + hy^{2} to z^{2} + gz + h). If m = u(x^{2} + gxy + hy^{2}) and x, y are coprime, can we find z such that z^{2} + gz + h is a multiple of m using “continuants”?

Problem 5 (From z^{2} + gz + h to x^{2} + gxy + hy^{2}). If m divides z^{2} + gz + h, can we find x, y such that m = u(x^{2} + gxy + hy^{2}) using “continuants”?

We emphasize that, while Problem 5 has a positive answer in some situations (see below), in general it has a negative answer. More information is given in Subsection 3.2.

In this paper we use a generalization of continuants [22] to produce proper representations Q(x, y) = x^{2}+gxy+hy^{2}, up to multiplication by a unit u, of an element m in some Euclidean rings. This generalization allows us to present the following new deterministic algorithms.

1. Algorithm 1: for every m in a commutative Euclidean ring, it finds a solution z_{0} of Q(z, 1) ≡ 0 (mod m), given a proper representation uQ(x, y) of m.

2. Algorithm 2: for every polynomial m ∈ 𝔽[X], where 𝔽 is a field of odd characteristic, it finds a proper representation u(x^{2} + hy^{2}) of m, given a solution z_{0} of Q(z, 1) ≡ 0 (mod m). Here h is a polynomial in 𝔽[X] of degree at most one.

3. Algorithm 3: for all negative fundamental discriminants of class number one, it finds a representation uQ(x, y) of an integer m, given a solution z_{0} of Q(z, 1) ≡ 0 (mod m).

A simple modification of Algorithm 3 produces representations uQ(x, y) for some positive discriminants of class number one, including all the determinants studied by Matthews [15]. This modification is discussed in Section 5.

Recall the class number of a determinant Δ ∈ ℤ [2, p. 7] gives the number of equivalence classes of integral binary quadratic forms with discriminant Δ. As is customary, we ignore negative definite forms; see [2, p. 7] and [16, p. 152].

When trying to extend Smith’s approach to other Euclidean rings R, one is confronted by the lack of uniqueness of the continuant representation. The uniqueness of the continuant representation boils down to the uniqueness of the quotients and the remainders in the division algorithm. This uniqueness is achieved only when R is a field or R = 𝔽[X], the polynomial algebra over a field 𝔽 [13] (considering the degree as the Euclidean function).

1.2 A short review of related results

Let p be a prime number of the form 4k + 1. In his proof of Fermat’s two-square theorem, Smith [4] first shows the existence of a palindromic sequence Q = (q_{1}, …, q_{s}, q_{s}, …, q_{1}) such that p = [Q] through an elegant parity argument. This sequence then allows him to derive a solution for z^{2} + 1 ≡ 0 (mod p) and a representation x^{2} + y^{2} for p.

With regard to the question of finding square roots modulo a prime p, Schoof [20] presented a deterministic algorithm and Wagon [24] wrote an interesting article on the topic.

Brillhart’s refinement [1] of Smith’s construction took full advantage of the palindromic structure of the sequence (q_{1}, …, q_{s−1}, q_{s}, q_{s}, q_{s−1}, …, q_{1}) given by the Euclidean algorithm on p and z_{0}, a solution of z^{2} + 1 ≡ 0 (mod p). He noted that the Euclidean algorithm gives the remainders

r_{i} = [q_{i+2}, …, q_{s−1}, q_{s}, q_{s}, q_{s−1}, …, q_{1}] (i = 1, …, 2s − 1), and
r_{2s} = 0.

So, by virtue of Smith’s construction, rather than computing the whole sequence, we only need to obtain x = r_{s−1} = [q_{s}, q_{s−1}, …, q_{1}] and y = r_{s} = [q_{s−1}, …, q_{1}]. In this case, we have y < x < \sqrt{p}, Brillhart’s stopping criterium.

In the ring of integers, Cornacchia [5] extended Smith’s ideas to cover representations of numbers m = p, with p prime, by forms x^{2} + hy^{2}. It has been noticed that Cornacchia’s algorithm can be used to obtain representations for all 1 ≤ h < m, with m not necessarily prime [14]. Further extensions of Smith’s and Brillhart’s ideas have appeared in the literature [10, 25, 26], where the authors provided algorithms for finding proper representations of natural numbers as primitive, positive-definite, integral and binary quadratic forms. Matthews [15] provided representations of certain integers as x^{2}−hy^{2}, where h = 2, 3, 5, 6, 7. In all these papers continuants have featured as numerators (and denominators) of continued fractions. For instance, the continuant [q_{1}, q_{2}, q_{3}] equals the numerator of the continued fraction

q_{1} + \frac{1}{q_{2} + \frac{1}{q_{3}}},

while the continuant [q_{2}, q_{3}] equals its denominator.

For us the set of natural numbers ℕ includes the zero.

Concerning other rings, one of the most important results is due to Choi, Lam, Reznick and Rosenberg [3]. They [3] proved the following theorem.

Theorem 6 ([3, Thm. 2.5]). Let R be an integral domain, let 𝔽_{R} be its field of fractions, let −h be a non-square in 𝔽_{R}, and let R[\sqrt{−h}] be the smallest ring containing R and \sqrt{−h}.

If both R and R[\sqrt{−h}] are UFDs (unique factorisation domains), then the following assertions hold.

(1) Any element m ∈ R which is representable by the form x^{′2} + hy^{′2} with x′, y′ ∈ 𝔽_{R} is also representable by the form x^{2} + hy^{2} with x, y ∈ R.

(2) Any element m ∈ R which is representable by the form x^{2} + hy^{2} can be factored into p_{1}^{2} ⋯ p_{k}^{2}q_{1} ⋯ q_{l} where p_{i}, q_{j} are irreducible elements in R and q_{j} is representable by x^{2} + hy^{2} for all j.

(3) Some associate of a non-null prime element p ∈ R is representable by x^{2} + hy^{2} iff −h is a square in 𝔽_{R/Rp}, where 𝔽_{R/Rp} denotes the field of fractions of the quotient ring R/Rp.

The rest of the paper is structured as follows. In Section 2 we define a generalization of the notion of continuant and describe some of its properties. Section 3 is devoted to studying proper representations x^{2} + gxy + hy^{2} in some commutative Euclidean rings, mainly in the ring of polynomials over a field of odd characteristic. In Section 4 we consider proper representations x^{2} + gxy + hy^{2} in the ring of integers. Some final remarks are presented in Section 5.

2 Generalized continuants

With the aim of considering the problem of properly representing an element m as x^{2}+gxy+ hy^{2}, we extend the notion of continuants. Generalizations of continuants have previously appeared in the literature, mainly in commutative rings, where these generalizations can be considered determinants of certain matrices; see [23, Sec. 8] and [22].

Definition 7 (Generalized Continuants in Arbitrary Rings). In a ring R we associate with the element [Q; h, s] the 3-tuple formed from a sequence Q of elements q_{1}, q_{2}, …, q_{n} of R, an element h of R and an integer s ≥ 1 via the following recurrence formula

[q_{1}, … q_{n}; h, s] = \begin{cases}[q_{1}, …, q_{n}], & if s ≥ n; \\ [q_{1}, …, q_{n−1}]q_{n} + [q_{1}, …, q_{n−2}]h, & if s = n − 1; \\ [q_{1}, …, q_{n−1}; h, s]q_{n} + [q_{1}, …, q_{n−2}; h, s], & if s < n − 1. \end{cases}

This definition of generalized continuants carries several consequences, all of which are proved in Appendix A. These properties are referred to as Generalized Continuant Properties.

P–3 [q_{1}, …, q_{n}; h, s] = [q_{1}, …, q_{s−1}]h[q_{s+2}, …, q_{n}] + [q_{1}, …, q_{s}][q_{s+1}, …, q_{n}], for s < n.

P–4 If in a ring R we find a unit u commuting with each element q_{i}, then

[u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n}}q_{n}; h, s] = \begin{cases}[q_{1}, …, q_{n}; h, s], & for even n; \\ u^{−1}[q_{1}, …, q_{n}; h, s], & for odd n. \end{cases}

The next two properties pertain to commutative rings.

P–5 The generalized continuant [q_{1}, …, q_{n}; h, s] is the determinant of the tridiagonal n × n matrix A = (a_{ij}) with a_{i,i} = q_{i} for 1 ≤ i ≤ n, a_{i,i+1} = 1 for 1 ≤ i < n, a_{s+1,s} = −h and a_{i+1,i} = −1 for 1 ≤ i < n and i ≠ s. See the determinant of the matrix below for a small example.

[q_{1}, q_{2}, q_{3}, q_{4}, q_{5}; h, 3] = det [\begin{matrix}q_{1} & 1 \\ −1 & q_{2} & 1 \\ & −1 & q_{3} & 1 \\ & & −h & q_{4} & 1 \\ & & & −1 & q_{5} \end{matrix}]

P–6 [q_{1}, q_{2}, …, q_{n}; h, n − s] = [q_{n}, …, q_{2}, q_{1}; h, s].

3 From Q(x, y) to Q(z, 1) and back

In this section, considering the form Q(x, y) = x^{2} + gxy + hy^{2}, we deal with the problem of going from a representation Q(x, y) of an element m to a multiple Q(z, 1) of m and back.

3.1 From Q(x, y) to Q(z, 1)

We begin with a general proposition which is valid for every commutative ring.

Proposition 8. If Rx + Ry = R then there exist z ∈ R such that Q(x, y) divides Q(z, 1), where Rm denotes the ideal generated by m.

If R is Euclidean, we can explicitly find z and the quotient Q(z, 1)/Q(x, y) with generalized continuants.

Proof. We have u and v such that xu + yv = 1. Then, computation with norms in the ring obtained from R by adjoining formally a root of the polynomial T^{2} − gT + h provides the identity

Q(x, y)Q(v − ug, u) = Q(xv − xug − yuh, xu + yv),

which proves the first assertion. This identity can be interpreted also as a kind of Carroll’s identity.

The determinant of the tridiagonal matrix

M = [\begin{matrix}q_{s} & 1 \\ −1 & ... & ... \\ & ... & q_{2} & ... \\ & & −1 & q_{1} & ... \\ & & & −h & q_{1} + g & ... \\ & & & & −1 & q_{2} & ... \\ & & & & & ... & ... & 1 \\ & & & & & & −1 & q_{s} \end{matrix}]  (1)

is Q(x, y) with x = [q_{1}, …, q_{s}] and y = [q_{2}, …, q_{s}] if s ≥ 1.

Also, Q(x, y)Q([q_{1}, … q_{s−1}], [q_{2}, … q_{s−1}]) = Q(z, 1), where z = (−1)^{s+1}c and c is the determinant of the matrix formed by the 2s − 1 first rows and columns of M.

The proof of Proposition 8 can be readily converted into a deterministic algorithm which finds a solution z_{0} of Q(z, 1) ≡ 0 (mod m), given a representation uQ(x, y) of an element m in a Euclidean ring R with a computable function N. See Algorithm 1.

Algorithm 1: Deterministic algorithm for constructing a solution z_{0} of Q(z, 1) ≡ 0 (mod m), given a proper representation uQ(x, y) of an element m. input : A commutative Euclidean ring R with a computable function N.

An element m ∈ R.

A proper representation uQ(x, y) of m, where Q(x, y) = x^{2} + gxy + hy^{2}. output: A solution z_{0} of Q(z, 1) ≡ 0 (mod m) with N(1) ≤ N(z_{0}).

/* Apply the Euclidean algorithm to x and y and obtain a sequence
   (q_{1}, . . . , q_{s}) of quotients.                                            */

s ← 0; m_{0} ← m; r_{0} ← z; repeat

s ← s + 1;

m_{s} ← r_{s−1};

find q_{s}, r_{s} ∈ R such that m_{s−1} = q_{s}m_{s} + r_{s} with N(r_{s}) < N(m_{s}); until r_{s} = 0 ; z_{0} ← (−1)^{s+1}[q_{s}, q_{s−1}, …, q_{1}, q_{1} + g, q_{2}, …, q_{s−1}; h, s]; return z_{0}

3.2 From Q(z, 1) to Q(x, y)

We begin the subsection with the following remark.

Remark 9. Let R be a commutative ring.

If 2 is invertible, the form x^{2} + gxy + hy^{2} can be rewritten as (x + gy/2)^{2} + (h − g^{2}/4)y^{2}. We may then assume g = 0 without loss of generality.

If moreover −h is an invertible square, say h + k^{2} = 0, then x = (\frac{x+1}{2})^{2} + h (\frac{x−1}{2k})^{2}

Below we provide a proposition which can be considered as an extension of [7, Prop. 16].

Proposition 10. Let R = 𝔽[X] be the ring of polynomials over a field 𝔽 with characteristic different from 2, and let −h be a (non-null) non-square of 𝔽.

If m divides z^{2} + ht^{2} with z, t coprime, then m is an associate of some x^{2} + hy^{2} with x, y coprime.

Proof. We introduce the extension 𝔾 of 𝔽 by a square root ω of −h. The ring 𝔾[X] is principal and z^{2} + ht^{2} factorizes as (z − ωt)(z + ωt). The two factors are coprime, since 2 and ω are units, and any common divisor must divide their sum 2z and their difference 2ωt.

Introduce x + ωy = gcd(m, z + ωt). Then x − ωy is a gcd of m and z − ωt, using the natural automorphism of 𝔾. The polynomials x − ωy and x + ωy are coprime and both divide m. Thus, m is divisible by (x−ωy)(x+ωy) = x^{2} +hy^{2}. On the other hand, m divides (z − ωt)(z + ωt). Consequently, m is an associate of x^{2} + hy^{2}. Since x − ωy and x + ωy are coprime, x and y are also coprime.

In the case of m being prime, Proposition 10 is embedded in Theorem 2.5 of the aforementioned paper of Choi et al. [3].

Proposition 11. Let R = 𝔽[X] be the ring of polynomials over a field 𝔽 with characteristic different from 2, and let h be a polynomial of degree 1.

If m divides z^{2} + ht^{2} with z, t coprime, then m is an associate of some x^{2} + hy^{2} with x, y coprime.

Proof. Consider the extension of the ring R = 𝔽[X] by a root of T^{2} + h; this extension of R is isomorphic to 𝔽[T].

First assume that h does not divide m. If h and z are not coprime, then z can be rewritten as z = z_{1}h. Thus, m dividing h(hz_{1}^{2} + t^{2}) implies that m divides hz_{1}^{2} + t^{2}, with h and t being coprime. Thus, we can assume that h and z are coprime. Consequently, z^{2} + ht^{2} factors as (z − T t)(z + T t), with the two factors being coprime. Reasoning as in Proposition 10, we let x + T y be the gcd of m and z + T t and we obtain that x − T y is the gcd of m and z − T t and that m is an associate of x^{2} + hy^{2} with x, y coprime.

If m is a multiple of h, then h does not divide m/h, since z and t are coprime. From the previous case it then follows that m/h is an associate of some x^{2} + hy^{2}, with x and y coprime. Thus, m is an associate of (hy)^{2} + hx^{2}, with hy and x coprime.

The next remark generalizes [7, Rem. 19].

Remark 12 (Algorithmic considerations). For the cases covered in Propositions 10 and 11, given an element m and a solution z_{0} of z^{2} +h ≡ 0 (mod m), we can obtain a representation x^{2} + hy^{2} of an associate of m via generalized continuants and Brillhart’s [1] optimisation. Indeed, divide m by z_{0} and stop when a remainder r_{s−1} with degree at most deg(m)/2 is encountered. This will be the (s − 1)-th remainder, and (uq_{s}, u^{−1}q_{s−1}, …, u^{(−1)^{s−2}}q_{2}) will be the quotients so far obtained. Then

x = \begin{cases}r_{s−1}, & for odd s; \\ u^{−1}r_{s−1}, & for even s. \end{cases}

y = \begin{cases}[uq_{s}, u^{−1}q_{s−1}, …, u^{(−1)^{s−2}}q_{2}], & for odd s; \\ u^{−1}[uq_{s}, u^{−1}q_{s−1}, …, u^{(−1)^{s−2}}q_{2}], & for even s. \end{cases}

This conclusion follows from dividing

m/u = [q_{s}, …, q_{1}, q_{1}, …, q_{s}; h, s] by
z_{0} = [q_{s−1}, …, q_{1}, q_{1}, …, q_{s}; h, s − 1],

using generalized continuant properties.

Remark 12 can be readily translated into a deterministic algorithm for computing representations Q(x, y); see Algorithm 2.

The argument presented in [7, Prop. 17] can be applied to the form x^{2}+hy^{2} in polynomials over a field 𝔽 of characteristic different from 2, where −h is either a non-square ∈ 𝔽 or a polynomial in 𝔽[X] of degree 1. This argument implicitly invokes the uniqueness of the quotients and the remainders in the division algorithm.

Corollary 13 (of Proposition 10: −h a non-square unit in 𝔽[X]). Let m be a non-unit of 𝔽[X] and a divisor of z^{2}+h for some z ∈ 𝔽[X] with deg(z) < deg(m). Then, m = (x^{2}+hy^{2})u for some unit u and the Euclidean algorithm on m and z gives the unit u and the sequence

(uq_{s}, u^{−1}q_{s−1}, …, u^{(−1)^{s+1}}q_{1}, u^{(−1)^{s}}h^{−1}q_{1}, …, u^{−1}h^{(−1)^{s}}q_{s})

such that x = [q_{1}, … q_{s}] and y = [q_{2}, …, q_{s}].

In the next example we illustrate Remark 12 and the method of Corollary 13, in this order, for the case of 𝔽 = ℚ. Let h = 3 and m = 1 + 2X + 3X^{2} + 2X^{3} + X^{4}. Then m divides ((5 + 12X + 6X^{2} + 4X^{3})/3)^{2} + 3. The Euclidean division gives

1 + 2X + 3X^{2} + 2X^{3} + X^{4} =((5 + 12X + 6X^{2} + 4X^{3})/3)(3X/4 + 3/8)
+ 3/8 − 3X/4 − 3X^{2}/4.

Here the first remainder has degree at most deg(m)/2, thus we stop the division process and obtain s = 2, x = (3/8 − 3X/4 − 3X^{2}/4)/u and y = [3X/4 + 3/8]/u. It is now routine to get u = 9/16.

If instead we use the method of Corollary 13, then we obtain the unit u = 9/16 and the sequence

(9/16 · 2/3 · (1 + 2X), 16/9 · (−1/2 − X), 9/16 · 1/3 · (−1/2 − X), 16/9 · 3 · 2/3 · (1 + 2X)).

From this sequence we conclude that

x = [2/3 · (1 + 2X), −1/2 − X],
y = [2/3 · (1 + 2X)].

Corollary 14 (of Proposition 11: h of degree 1 in 𝔽[X]). Let m be a polynomial over 𝔽[X] and a divisor of z^{2} + h for some z ∈ 𝔽[X] with deg(z) < deg(m) and z, h coprime. Then, m = (x^{2} + hy^{2})u for some unit u and the values of x and y can be obtained by Remark 12.

Consider the following example. Let h = X, m = 1 + X + X^{3} + X^{4} and z = (X^{3} + 2X^{2} + 1)/2. Then, the division gives

1 + X + X^{3} + X^{4} =(X^{3} + 2X^{2} + 1)/2 · (−2 + 2X) + 2 + 2X^{2}.

At this step we should stop the division process as the first remainder has at most half the degree of m. Now we know that s = 2, x = (2 + 2X^{2})/u and y = u^{−1}[−2 + 2X] for a unit u. It plainly follows that u = 4.

We may now wonder how far can we push this method for polynomials over a field of characteristic different from 2? That is, will the method work for h with deg(h) > 1 over any such field?

We first note that the property

“m|z^{2} + h ⇒ ∃x, y, u (m = u(x^{2} + y^{2}h) ∧ u unit)” does not hold in general for h reducible. Consider h = X^{3} + X^{2} + X in polynomials over a field of characteristic ≠ 3. Then, X^{2} + X + 1 divides 0^{2} + 1^{2}h and is certainly not of the form x^{2} + y^{2}h. Indeed, here we have either y^{2}h null or of odd degree ≥ 3. In the former case, it follows that x^{2} + y^{2}h = x^{2} is a square, but X^{2} + X + 1 is not a square in a field of characteristic ≠ 3, while in the latter case x^{2} + y^{2}h has degree ≥ 3 > degree(X^{2} + X + 1).

What about irreducible h with deg(h) ≥ 2? Already for degree 2 the property does not hold in general. Indeed, consider in ℚ[X] the polynomials h = X^{2} − 2, z = X^{2} and m = X − 1. Observe that X − 1 divides X^{4} + X^{2} − 2 and that X − 1 is not of the form u(x^{2} + y^{2}(X^{2} − 2)). To see this, note that the degree of x^{2} + y^{2}(X^{2} − 2) is either 2 deg(x) or 2 + 2 deg(y).

Algorithm 2: Deterministic algorithm for constructing a proper representation uQ(x, y) = u(x^{2} + hy^{2}) of an element m. input : A field 𝔽 with characteristic different from 2.

The ring R = 𝔽[X] of polynomials over 𝔽.

A square-free element h ∈ 𝔽 or a polynomial h ∈ R of degree 1. A polynomial m with N(1) < N(m). A solution z_{0} of Q(z, 1) ≡ 0 (mod m) with N(1) < N(z_{0}) < N(m_{0}).

output: A unit u and a proper representation uQ(x, y) of m. assumptions: The polynomials z and h are coprime.

/* Divide m by z using the Euclidean algorithm until we find a
   remainder r_{s−1} with degree at most deg(m)/2.                        */

s ← 1; m_{0} ← m; r_{0} ← z; repeat

s ← s + 1;

m_{s−1} ← r_{s−2};

find k_{s−1}, r_{s−1} ∈ R such that m_{s−2} = k_{s−1}m_{s−1} + r_{s−1} with N(r_{s−1}) < N(m_{s−1}); until deg(r_{s−1}) ≤ deg(m)/2 ;

/* Here we have a sequence (k_{1}, . . . , k_{s−1}) of quotients.                  */

x_{temp} ← r_{s−1}; y_{temp} ← [k_{1}, …, k_{s−1}];

/* We obtain a unit u.                                                */

if s is odd then Solve m = u(x_{temp}^{2} + hy_{temp}^{2}) for u else Solve um = x_{temp}^{2} + hy_{temp}^{2} for u

/* We obtain (x, y) so that m = (x^{2} + hy^{2})u.                             */

if s is odd then x ← x_{temp} else x ← u^{−1}x_{temp}; if s is odd then y ← y_{temp} else y ← u^{−1}y_{temp}; return (x, y, u)

For specific fields we find situations where the property holds. Take, for instance, the field ℝ of reals, h = X^{2} + 1 and every real polynomial m taking only positive values over ℝ. It is known that any polynomial m over ℝ, which takes at every point of ℝ a positive value, has the form ∏(a_{k}X^{2} + 2b_{k}X + c_{k}), where a_{k}, b_{k}, c_{k} ∈ ℝ and b_{k}^{2} − a_{k}c_{k} < 0. Thus, it suffices to consider the case of m = aX^{2} + 2bX + c with a > 0, c > 0 and b^{2} − ac < 0. If b = 0, then

m = \begin{cases}(\sqrt{a − c}X)^{2} + \sqrt{c}^{2}(X^{2} + 1), & if a ≥ c; \\ \sqrt{c − a}^{2} + \sqrt{a}^{2}(X^{2} + 1), & if a ≤ c. \end{cases}

If instead b ≠ 0, then, setting d = \sqrt{(a + c − \sqrt{(a − c)^{2} + 4b^{2}})/2}, we obtain m = (\sqrt{a − d^{2}}X + e\sqrt{c − d^{2}})^{2} + d^{2}(X^{2} + 1), where e = ±1 is the sign of b.

For h = −X^{2} − 1 and every real polynomial m over ℝ, we have another situation where the property holds. Observe that the form Q(x, y) = x^{′2} + (−X^{2} − 1)y^{′2} is equivalent to the form Q(x, y) = x^{2} + 2Xxy − y^{2} (by Remark 9). Any polynomial of degree 1 is an associate of some a^{2} − b^{2} + 2abX with units a and b. We now take care of polynomials m = k(X^{2} + 2vX + w) with no real zeros and k, v, w ∈ ℝ. Here note that v^{2} < w. Set p(X) = (X + a)^{2} + 2b(X + a)X − b^{2}. We solve the equation p(X) = m in (a, b, k). We first find that k = 1 + 2b, a = kv/(1 + b) (if b ≠ −1) and w = (a^{2} − b^{2})/k = −X^{2} − 2vX. If b = −1 then v = 0, k = −1 and a = ±\sqrt{1 − w} with 0 < w ≤ 1. If instead b ≠ −1, then, substituting a = kv/(1 + b) into −(1 + b)^{2}p(X), we obtain

b^{4} + 2(w + 1)b^{3} + (5w − 4v^{2} + 1)b^{2} + 4(w − v^{2})b + w − v^{2} = 0.

This expression in b is 1/16 when b = −1/2 and −v^{2} when b = −1. Hence there is a solution b in the open interval (−1, −1/2) for w > 1. Consequently, each real polynomial is an associate of some polynomial x^{2} + 2xyX − y^{2} = (x + Xy)^{2} + (−1 − X^{2})y^{2}.

Using the automorphisms of ℝ[x], both previous approaches can easily be applied to any real polynomial of degree 2 with no real roots.

4 From Q(z, 1) to Q(x, y): integral quadratic forms

In this section, given integers m, z such m|Q(z, 1), we provide an algorithm that proves the existence of representations Q(x, y)u of m for a unit u and certain forms Q.

Since 2 is not invertible in ℤ, we have to consider the rings of algebraic integers of ℚ[\sqrt{−h}], that is, the rings ℤ[\sqrt{−h}] for forms x^{2} + hy^{2} with |h| square-free and h ≢ −1 (mod 4), and the ring ℤ[(1 + \sqrt{1 − 4h})/2] for forms x^{2} + xy + hy^{2} with |1 − 4h| square-free; see [19, p. 35].

What are those rings of integers for which the following property holds?

“m|Q(z, 1) ⇒ ∃x, y, u (m = uQ(x, y) ∧ u unit).”

The answer is given by the rings whose corresponding forms have class number H(Δ) equal to one [2, pp. 6–7, pp. 81–84]. Here Δ denotes the form discriminant. In the case of Δ < 0, all the principal rings satisfy the property; these values of Δ are the following: −3, −4, −7, −8, −11, −19, −43, −67, −163; see [17, A014602] and [2, pp. 81]. For these negative fundamental discriminants, generalized continuants provide a constructive proof of the property. It is also known that there are four negative non-fundamental discriminants of class number one, namely −12, −16, −27 and −28; see [2, pp. 81] and [6, Thm. 7.30]. For the case of Δ > 0, while we do not even know whether the list of such determinants is infinite, it is conjectured this is the case; see [2, pp. 81–82] and [17, A003655].

Recall the class number H(Δ) [2, p. 7] gives the number of equivalence classes of integral binary quadratic forms with discriminant Δ ∈ ℤ.

Next we recall the following well-known result of Rabinowitsch [18].

Theorem 15 ([18]). For a fundamental discriminant Δ = 1 − 4κ ≤ −7, it follows that H(Δ) = 1 iff x^{2} + x + κ attains only prime values for −(κ − 1) ≤ x ≤ κ − 2.

Below we present a division algorithm (Algorithm 3) which, for any negative fundamental discriminant of class number one, gives a proper representation Q(x, y) of m, provided that m divides Q(z, 1).

Since m = 1 trivially admits the proper representation (1, 0) of Q(x, y) = x^{2} + gxy + hy^{2}, Algorithm 3 assumes |m| > 1.

Algorithm 3: Deterministic algorithm for constructing a proper representation Q(x, y) = x^{2} + gxy + hy^{2} of an element m. input : A negative fundamental discriminant Δ of class number one.

An integer m_{0} with 1 < |m_{0}|.

A solution z_{0} of Q(z, 1) ≡ 0 (mod m_{0}) with 1 < |z_{0}| < |m_{0}|.

output: A proper representation Q(x, y) of m_{0}/u (u = ±1).

s ← 0;

while |m_{s}| ≠ 1 do s ← s + 1; 4 m_{s} ← Q(z_{s−1}, 1)/m_{s−1}; 5 find k_{s}, z_{s} ∈ R such that z_{s−1} = k_{s}m_{s} + z_{s} with |z_{s}| < |m_{s}|;

      /* We prioritize non-null quotients k_{s}.                            */

end

   /* Here we have the unit m_{s} and sequence (k_{1}, . . . , k_{s}).                  */
   /* To keep consistency with the previous sections of the paper we
      reverse the subscripts of the quotients                            */

(q_{1}, q_{2}, …, q_{s}) ← (k_{s}, k_{s−1}, …, k_{1});

x ← [m_{s}q_{1}, m_{s}^{−1}q_{2}, …, m_{s}^{(−1)^{s−2}}q_{s−1}, m_{s}^{(−1)^{s−1}}q_{s}];

y ← [m_{s}^{−1}q_{2}, …, m_{s}^{(−1)^{s−2}}q_{s−1}, m_{s}^{(−1)^{s−1}}q_{s}];

return (x, y)

Remark 16 (Algorithm 3: Prioritizing non-null quotients). In the Euclidean division of z_{s−1} by m_{s} with |z_{s−1}| < |m_{s}|, a valid quotient k_{s} could be ±1 or 0. By “prioritizing non-null quotients k_{s}” we mean that, in this situation, we always choose the k_{s} which is not null.

Proposition 17 (Algorithm 3 Correctness). Let h, g, Δ, u, m_{0}, z_{0}, and m_{i}, z_{i}, q_{i} (i = 1, …, s) be as in Algorithm 3. Then, Algorithm 3 produces a proper representation Q(x, y) of m_{0}/u.

Proof. In the ring ℤ[(1 + \sqrt{1 − 4h})/2] we consider the form Q(x, y) = x^{2} + xy + hy^{2}, while in the ring ℤ[\sqrt{−h}] we consider the form Q(x, y) = x^{2} + hy^{2}. As the proof method is the same in both cases, we restrict ourselves to the former case, that is, to the case of Δ = −3, −7, −11, −19, −43, −67, −163 and h = 1, 2, 3, 5, 11, 17, 41.

Claim 1. Algorithm 3 terminates with the last m_{j} being ±1.

As a general approach we show that the sequence |m_{i}| (i = 0, …, s − 1) is decreasing, that is, |m_{i+1}| < |m_{i}| . Once this decreasing character fails, we show that the algorithm stops with the last m_{i} being a unit.

Recall we have |m_{i}| ≥ |z_{i}| + 1 for i = 1, …, s − 1.

Case (Δ, h) = (−3, 1), (−7, 2): |m_{i}||m_{i}| ≥ z_{i}^{2} + 2|z_{i}| + 1 > |z_{i}^{2} + z_{i} + h| = |m_{i}||m_{i+1}|, and thus |m_{i}| > |m_{i+1}| for |z_{i}| > 1. Assume that for a certain z_{i}, say z_{s−1}, |z_{s−1}| = 1. If h = 1 then Line 4 (z_{s−1}^{2} + z_{s−1} + 1 = m_{s−1}m_{s}) gives that |m_{s}| = 1, as desired. In the case of h = 2 and z_{s−1} = −1, we have that z_{s−1}^{2} + z_{s−1} + 2 = 2 and |m_{s}| = 1. If h = 2 and z_{s−1} = 1, we have from Line 4 again that 1 + 1 + 2 = m_{s−1}m_{s}. Then we deduce that either |m_{s−1}| = 2 and |m_{s}| = 2 or |m_{s−1}| = 4 and |m_{s}| = 1. The configuration |m_{s−1}| = 4 and |m_{s}| = 1 will cause the algorithm to stop with m_{s} being a unit. In the case of |m_{s−1}| = 2 and |m_{s}| = 2, in Line 5 we have z_{s−1} = k_{s}m_{s} + z_{s} and the algorithm would give z_{s} = −1, which implies |m_{s+1}| = 1.

Consequently, in these two cases Algorithm 3 terminates with the last m_{j} being a unit.

Case (Δ, h) = (−11, 3), (−19, 5), (−43, 11), (−67, 17), (−163, 41):

Reasoning as in the previous case, we have that |m_{i}||m_{i}| ≥ z_{i}^{2} + 2|z_{i}| + 1 > |z_{i}^{2} + z_{i} + h| = |m_{i}||m_{i+1}|, unless |z_{i}| ≤ h − 1. Suppose |z_{s−1}| ≤ h − 1. Note that |m_{s−1}| > 1, otherwise the algorithm would have stopped. By Theorem 15, the polynomial Q(z_{s−1}, 1) = z_{s−1}^{2} + z_{s−1} + h is prime for −(h − 1) ≤ z_{s−1} ≤ h − 2. Thus, we have that |m_{s−1}| > |m_{s}| with |m_{s}| = 1.

If instead z_{s−1} = h − 1, then |m_{s−1}| = |m_{s}| = h, which implies that z_{s} = −1 and |m_{s+1}| = 1, causing the algorithm to stop.

Claim 2. Algorithm 3 produces a proper representation Q(x, y).

It only remains to prove that x and y have the required form. First we reverse the subscripts of the quotients, that is, the quotient k_{s} becomes q_{1}, the quotient k_{s−1} becomes q_{2}, and so on. Thus, after the “while” loop we have that z_{s−1} = m_{s}q_{1}, where m_{s} is a unit. We know that Q(m_{s}q_{1}, 1) = m_{s−1}m_{s}. Consequently, m_{s−1}m_{s} = [m_{s}q_{1} + 1, m_{s}q_{1}; h, 1]. Then, by Property P–6 and Property P–3 it follows

z_{s−2} = [m_{s}^{−1}q_{2}, m_{s}q_{1} + 1, m_{s}q_{1}; h, 2].

Then, from the equation m_{s−2}m_{s−1} = Q(z_{s−2}, 1) we obtain

m_{s−2}m_{s}^{−1} = [m_{s}^{−1}q_{2}, m_{s}q_{1} + 1, m_{s}q_{1}, m_{s}^{−1}q_{2}; h, 2] = Q([m_{s}q_{1}, m_{s}^{−1}q_{2}], [m_{s}^{−1}q_{2}]).

Continuing this process, we have

z_{0} = [m_{s}^{(−1)^{s−1}}q_{s}, K, m_{s}q_{1} + 1, m_{s}q_{1}, K^{−1}; h, s],
m_{0}m_{s}^{(−1)^{s+1}} = [m_{s}^{(−1)^{s−1}}q_{s}, K, m_{s}q_{1} + 1, m_{s}q_{1}, K^{−1}, m_{s}^{(−1)^{s−1}}q_{s}; h, s],

where K = m_{s}^{(−1)^{s−2}}q_{s−1}, …, m_{s}^{−1}q_{2} and K^{−1} = m_{s}^{−1}q_{2}, …, m_{s}^{(−1)^{s−2}}q_{s−1}.

Consequently, from Property P–4 it follows that m_{0}m_{s}^{(−1)^{s+1}} = Q(x, y), where

x =[m_{s}q_{1}, m_{s}^{−1}q_{2}, …, m_{s}^{(−1)^{s−2}}q_{s−1}, m_{s}^{(−1)^{s−1}}q_{s}],
y =[m_{s}^{−1}q_{2}, …, m_{s}^{(−1)^{s−2}}q_{s−1}, m_{s}^{(−1)^{s−1}}q_{s}].

Using Property P–6 we can write m_{0}m_{s}^{(−1)^{s+1}} as follows; see Equation (1).

m_{0}m_{s}^{(−1)^{s+1}} = [m_{s}^{(−1)^{s−1}}q_{s}, K, m_{s}q_{1}, m_{s}q_{1} + 1, K^{−1}, m_{s}^{(−1)^{s−1}}q_{s}; h, s].

Remark 18. Note that we require all the numbers m_{i} to be represented by the form Q(x′, y′). This is assured by the fact that Q has class number one.

As a result, each root z_{0} of Q(z, 1) ≡ 0 (mod m_{0}) with 1 < |z_{0}| < |m_{0}| gives rise to a proper representation of m_{0}m_{s}^{(−1)^{s+1}} as Q(x, y). The coprimality of x and y follows from Property P–1.

Let us see an example. For the ring ℤ[(1 + \sqrt{−19})/2] the form is x^{2} + xy + 5y^{2}. Take m_{0} = 251 and z_{0} = 52. Then 251 · 11 = 52^{2} + 52 + 5, and the division gives

251 · 11 = 52^{2} + 52 + 5  →  52 = 4 · 11 + 8,
11 · 7 = 8^{2} + 8 + 5  →  8 = 1 · 7 + 1,
7 · 1 = 1^{2} + 1 + 5  →  1 = 1 · 1.

Thus, we have m_{3} = 1 and (q_{3}, q_{2}, q_{1}) = (4, 1, 1). From this we recover the continuant representation of m_{0} = 251

251 = det [\begin{matrix}4 & 1 \\ −1 & 1 & 1 \\ & −1 & 1 & 1 \\ & & −5 & 1 + 1 & 1 \\ & & & −1 & 1 & 1 \\ & & & & −1 & 4 \end{matrix}] .

Consequently, we conclude that 251 = x^{2} + xy + 5y^{2} with x = [1, 1, 4] = 9 and y = [1, 4] = 5.

5 Final remarks

In Algorithm 3 we require m_{s} to be ±1. However, this may be an unnecessarily strong restriction. If in Algorithm 3 we replace the condition of the while loop by z_{s} ≠ 0, then this modified Algorithm 3 may also end with the last m_{j}, say m_{s}, being different from ±1. Further, if such m_{s} admits a representation as Q(x, y), then the formula

(x^{2} + gxy + hy^{2})(z^{2} + gzw + hw^{2}) =(xz − hyw)^{2} + g(xz − hyw)×  (2)
× (xw + yz + gyw)+
+ h(xw + yz + gyw)^{2}

will provide a desired representation of m = m_{0} for a larger number of forms Q(x, y). First recall that in Algorithm 3

m_{0}m_{s}^{(−1)^{s+1}} =x^{2} + gxy + hy^{2},

where

x =[m_{s}q_{1}, m_{s}^{−1}q_{2}, …, m_{s}^{(−1)^{s−2}}q_{s−1}, m_{s}^{(−1)^{s−1}}q_{s}],
y =[m_{s}^{−1}q_{2}, …, m_{s}^{(−1)^{s−2}}q_{s−1}, m_{s}^{(−1)^{s−1}}q_{s}].

Then, to recover the representation of m_{0} (associated with z_{0}) we just need to express m_{s} or −m_{s} as Q(x, y). This simple modification of Algorithm 3 will provide proper representations Q(x, y) of ±m for some forms Q with discriminant Δ > 0 and H(Δ) = 1; see [?]. The following two examples illustrate this idea. Recall that the condition of the “while” loop is now z_{s} ≠ 0.

For the ring ℤ[(1 + \sqrt{17})/2] the form is x^{2} + xy − 4y^{2}. Take m_{0} = 3064 and z_{0} = 564. Noticing 3064 · 104 = 564^{2} + 564 − 4, the division gives

3064 · 104 = 564^{2} + 564 − 4  →  564 = 5 · 104 + 44,
104 · 19 = 44^{2} + 44 − 4  →  44 = 2 · 19 + 6,
19 · 2 = 6^{2} + 6 − 4  →  6 = 3 · 2.

Thus, we have s = 3, m_{3} = 2 and (q_{3}, q_{2}, q_{1}) = (5, 2, 3). From this we recover the continuant representation of m_{0} · 2 = 6128

6128 = det [\begin{matrix}10 & 1 \\ −1 & 1 & 1 \\ & −1 & 6 & 1 \\ & & 4 & 6 + 1 & 1 \\ & & & −1 & 1 & 1 \\ & & & & −1 & 10 \end{matrix}] .

The representation Q(x, y) of 6128 is given by x = [2 · 3, 2^{−1} · 2, 2 · 5] = 76 and y = [2^{−1} · 2, 2 · 5] = 11. Note that 2 = 2^{2} + 2 · 1 − 4 · 1^{2}. Using Equation (2) in the form 3064·(2^{2}+2·1−4·1) = 76^{2}+76·11−4·11^{2}, we conclude that 3064 = 92^{2}+92·(−27)−4(−27)^{2}.

For the ring ℤ[\sqrt{6}] the form is Q(x, y) = x^{2} − 6y^{2}. Take m_{0} = 37410 and z_{0} = 1326. Noticing 37410 · 47 = 1326^{2} − 6, the division gives

37410 · 47 = 1326^{2} − 6  →  1326 = 28 · (47) + 10,
47 · 2 = 10^{2} − 6  →  10 = 5 · 2.

Thus, we have s = 2, m_{2} = 2 and (q_{2}, q_{1}) = (28, 5). The representation Q(x, y) of 37410 · 2^{−1} is x = [2·5, 2^{−1} ·28] = 141 and y = [2^{−1} ·28] = 14. Note that −2 = 2^{2} −6·1^{2}. Using Equation (2) in the form (141^{2} − 6 · 14^{2})(2^{2} − 6 · 1^{2}) = −37410, we have that −37410 = 366^{2} − 6 × 169^{2}.

Below we present some of the forms Q(x, y) for which the proposed modification of Algorithm 3 will give the representation of m_{0} associated with the given z_{0}. The forms are given in the format (Q, {list of possible values of m_{s}}). Note that m_{s} is a divisor of h and that, for every case, either m_{s} or −m_{s} is represented by the form.

\begin{matrix}(x^{2} − 2y^{2}, \{±1, ±2\}) & (x^{2} + xy − 4y^{2}, \{±1, ±2, ±4\}) \\ (x^{2} − 3y^{2}, \{±1, ±3\}) & (x^{2} + xy − 7y^{2}, \{±1, ±7\}) \\ (x^{2} − 6y^{2}, \{±1, ±2, ±3, ±6\}) & (x^{2} + xy − 9y^{2}, \{±1, ±3, ±9\}) \\ (x^{2} − 7y^{2}, \{±1, ±7\}) & (x^{2} + xy − 10y^{2}, \{±1, ±2, ±5, ±10\}) \\ (x^{2} + xy − y^{2}, \{±1\}) & (x^{2} + xy − 13y^{2}, \{±1, ±13\}) \\ (x^{2} + xy − 3y^{2}, \{±1\}) & (x^{2} + xy − 15y^{2}, \{±1, ±3, ±5, ±15\}) \end{matrix}

Recall that Matthews [15] provided representations of certain integers as x^{2} − hy^{2}, where h = 2, 3, 5, 6, 7. From the previous remarks it follows that the modified Algorithm 3 covers all the cases studied by Matthews [15]. Observe that the form x^{2} − 5y^{2}, studied by Matthews [15] and associated with the non-principal ring ℤ[\sqrt{5}], has been superseded by the form x^{2} + xy − y^{2} associated with the integral closure of ℤ[\sqrt{5}], that is, ℤ[(1 + \sqrt{5})/2]. It is known that the forms x^{2} + xy − y^{2} and x^{2} − 5y^{2} represent the same integers. Indeed, if an integer m is represented by x^{2} − 5y^{2} then the identity x^{2} − 5y^{2} = (x − y)^{2} + (x − y)(2y) − (2y)^{2} gives a representation, not necessarily proper, of m by the form x^{′2} + x′y′ − y^{′2}. If instead an integer m is represented by the form x^{2} + xy − y^{2}, then, depending on the parity of x and y, one of the identities

x^{2} + xy − y^{2} = (x + y + \frac{x + 2y}{2} )^{2} − 5 (\frac{x + 2y}{2} )^{2} ,

= (2x − y + \frac{−x + y}{2} )^{2} − 5 (\frac{−x + y}{2} )^{2} ,

= (x + \frac{y}{2})^{2} − 5 (\frac{y}{2})^{2}

gives a representation by the form x^{′2} − 5y^{′2}.

Unsatisfactorily, our algorithm does not terminate for every Δ > 0 with H(Δ) = 1. For instance, take Δ = 73, m_{0} = 267 and z_{0} = 23. The corresponding quadratic form is x^{2} + xy − 18y^{2}, and we have that 267 = (−69)^{2} + (−69) · 14 − 18 · 14^{2} and 267|23^{2} + 23 − 18.

The approach presented in the paper is likely to work for other representations if new generalized continuants are defined.

Mathematica^{®}[27] implementations of most of the algorithms presented in the paper and other related algorithms are available at

   http://guillermo.com.au/wiki/List_of_Publications

under the name of this paper.

6 Acknowledgments

The authors thank the referee for his/her careful and thoughtful review. The paper’s presentation has certainly benefited from his/her comments.

A Proofs of some of the generalized continuant properties

Proposition 19 (Property P–3). For integers n, h, s such that 1 ≤ s < n and elements q_{1}, …, q_{n} of a ring R, the following identity holds:

[q_{1}, …, q_{n}; h, s] = [q_{1}, …, q_{s−1}]h[q_{s+2}, …, q_{n}] + [q_{1}, …, q_{s}][q_{s+1}, …, q_{n}].

Proof. In the case of h = 1 generalized continuants reduce to the traditional continuants and Property P–3 reduces to the well-known identity

[q_{1}, …, q_{n}] = [q_{1}, …, q_{s−1}][q_{s+2}, …, q_{n}] + [q_{1}, …, q_{s}][q_{s+1}, …, q_{n}].

This identity is proved for commutative rings in [4, Lem. 1] and [9, Sec. 6.7], but the approach by Graham et al. [9, Sec. 6.7] works for any ring.

For any h > 1 and s = n − 1, Property P–3 follows from the definition of generalized continuants.

Consider any h > 1 and s = n − 2. Then, from Definition 7 it follows that

[q_{1}, … q_{n}; h, n − 2] = [q_{1}, …, q_{n−1}; h, n − 2]q_{n} + [q_{1}, …, q_{n−2}; h, n − 2],
= ([q_{1}, …, q_{n−3}]h + [q_{1}, …, q_{n−2}][q_{n−1}])q_{n} + [q_{1}, …, q_{n−2}],
= [q_{1}, …, q_{n−3}]hq_{n} + [q_{1}, …, q_{n−2}]([q_{n−1}])q_{n} + 1),
= [q_{1}, …, q_{n−3}]hq_{n} + [q_{1}, …, q_{n−2}][q_{n−1}, q_{n}].

Finally, fix h > 1 and s < n − 2 and proceed by induction on n. The base cases n = 1, 2 fall in the previous cases. From Definition 7 it follows that

[q_{1}, … q_{n}; h, s] = [q_{1}, …, q_{n−1}; h, s]q_{n} + [q_{1}, …, q_{n−2}; h, s].

By the induction hypothesis we have the following.

[q_{1}, …, q_{n−1}; h, s] = [q_{1}, …, q_{s−1}]h[q_{s+2}, …, q_{n−1}] + [q_{1}, …, q_{s}][q_{s+1}, …, q_{n−1}];
[q_{1}, …, q_{n−2}; h, s] = [q_{1}, …, q_{s−1}]h[q_{s+2}, …, q_{n−2}] + [q_{1}, …, q_{s}][q_{s+1}, …, q_{n−2}].

Thus

[q_{1}, … q_{n}; h, s] = ([q_{1}, …, q_{s−1}]h[q_{s+2}, …, q_{n−1}] + [q_{1}, …, q_{s}][q_{s+1}, …, q_{n−1}])q_{n}
+ [q_{1}, …, q_{s−1}]h[q_{s+2}, …, q_{n−2}] + [q_{1}, …, q_{s}][q_{s+1}, …, q_{n−2}],
= [q_{1}, …, q_{s−1}]h ([q_{s+2}, …, q_{n−1}]q_{n} + [q_{s+2}, …, q_{n−2}])
+ [q_{1}, …, q_{s}]([q_{s+1}, …, q_{n−1}]q_{n} + [q_{s+1}, …, q_{n−2}]),
= [q_{1}, …, q_{s−1}]h[q_{s+2}, …, q_{n}] + [q_{1}, …, q_{s}][q_{s+1}, …, q_{n}].

Proposition 20 (Property P–4). Let n, h, s be integers such that 1 ≤ s, and let q_{1}, …, q_{n} be elements of a ring R. If there is a unit u in R commuting with each q_{i}, then

[u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n}}q_{n}; h, s] = \begin{cases}[q_{1}, …, q_{n}; h, s], & for even n; \\ u^{−1}[q_{1}, …, q_{n}; h, s], & for odd n. \end{cases}

Proof. Fix s ≥ 1 and h and proceed by induction on n. If n = 1, 2 then the property follows from Definition 7.

If s ≥ n then [u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n}}q_{n}; h, s] becomes [u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n}}q_{n}] and the result follows from induction by using

[u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n}}q_{n}] = [u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n−1}}q_{n−1}]u^{(−1)^{n}}q_{n}
+ [u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n−2}}q_{n−2}].

If s = n − 1 then we have

[u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n}}q_{n}] = [u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n−1}}q_{n−1}]u^{(−1)^{n}}q_{n}
+ [u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n−2}}q_{n−2}]h,

and the result follows from induction.

If s < n − 1 then Definition 7 gives that

[u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n}}q_{n}; h, s] = [u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n−1}}q_{n−1}; h, s]u^{(−1)^{n}}q_{n}
+ [u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n−2}}q_{n−2}; h, s].

Then the induction hypothesis gives that

[u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n−1}}q_{n−1}; h, s]u^{(−1)^{n}}q_{n} = u^{−1}[q_{1}, q_{2}, …, q_{n−1}; h, s]uq_{n},

if n is even; and it gives that

[u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n−1}}q_{n−1}; h, s]u^{(−1)^{n}}q_{n} = [q_{1}, q_{2}, …, q_{n−1}; h, s]u^{−1}q_{n},

if n is odd.

Furthermore, the induction hypothesis gives the following.

[u^{−1}q_{1}, uq_{2}, …, u^{(−1)^{n−2}}q_{n−2}; h, s] = \begin{cases}[q_{1}, q_{2}, …, q_{n−2}; h, s], & if n is even; \\ u^{−1}[q_{1}, q_{2}, …, q_{n−2}; h, s], & if n is odd. \end{cases}

As a consequence, the result follows.

Proposition 21 (Property P–5). Let n, h, s be integers such that 1 ≤ s, and let q_{1}, …, q_{n} be elements of a commutative ring R. Then the generalized continuant [q_{1}, …, q_{n}; h, s] is the determinant of the tridiagonal n × n matrix A = (a_{ij}) with a_{i,i} = q_{i} for 1 ≤ i ≤ n, a_{i,i+1} = 1 for 1 ≤ i < n, a_{s+1,s} = −h and a_{i+1,i} = −1 for 1 ≤ i < n and i ≠ s.

Proof. The result follows from using the Laplace expansion on the determinant along the last row.

Proposition 22 (Property P–6). Let n, h, s be integers such that 1 ≤ s, and let q_{1}, …, q_{n} be elements of a commutative ring R. Then [q_{1}, q_{2}, …, q_{n}; h, n − s] = [q_{n}, …, q_{2}, q_{1}; h, s].

Proof. Apply Property P–3 on both sides of the equality, and then use Property P–2.

References

[1] J. Brillhart, Note on representing a prime as a sum of two squares, Math. Comp. 26 (1972), 1011–1013.

[2] D. A. Buell, Binary Quadratic Forms: Classical Theory and Modern Computations, Springer-Verlag, 1989.

[3] M. D. Choi, T. Y. Lam, B. Reznick, and A. Rosenberg, Sums of squares in some integral domains, J. Algebra 65 (1980), 234–256.

[4] F. W. Clarke, W. N. Everitt, L. L. Littlejohn, and S. J. R. Vorster, H. J. S. Smith and the Fermat two squares theorem, Amer. Math. Monthly 106 (1999), 652–665.

[5] G. Cornacchia, Su di un metodo per la risoluzione in numeri interi dell’ equazione ∑_{h=0}^{n} C_{h}x^{n−h} = P, Giornale di Mat. 46 (1908), 33–90.

[6] D. A. Cox, Primes of the Form x^{2} + ny^{2}: Fermat, Class Field Theory and Complex Multiplication, John Wiley & Sons Inc., 1989.

[7] C. Delorme and G. Pineda-Villavicencio, Continuants and some decompositions into squares, Integers 15 (2015), paper A3.

[8] C. L. Dodgson, Condensation of determinants, being a new and brief method for computing their arithmetical values, Proc. Roy. Soc. Lond. 15 (1866), 150–155.

[9] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd ed., Addison-Wesley, 1994.

[10] K. Hardy, J. B. Muskat, and K. S. Williams, A deterministic algorithm for solving n = fu^{2} + gv^{2} in coprime integers u and v, Math. Comp. 55 (1990), 327–343.

[11] C. Hermite, Note au sujet de l’article précédent, J. Math. Pures Appl. 5 (1848), 15.

[12] N. Jacobson, Basic Algebra I, 2nd ed., W. H. Freeman and Company, 1985.

[13] M. A. Jodeit, Jr., Uniqueness in the division algorithm, Amer. Math. Monthly 74 (1967), 835–836.

[14] J. Magalona-Basilla, On the solution of x^{2} + dy^{2} = m, Proc. Japan Acad. Ser. A Math. Sci. 80 (2004), 40–41.

[15] K. Matthews, Thue’s theorem and the Diophantine equation x^{2} − Dy^{2} = ±N, Math. Comp. 71 (2002), 1281–1286.

[16] I. Niven, H. S. Zuckerman, and H. L. Montgomery, An Introduction to the Theory of Numbers, 5th ed., Wiley, 1991.

[17] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences,

    http://oeis.org.

[18] G. Rabinowitsch, Eindeutigkeit der Zerlegung in Primzahlfaktoren in quadratischen Zahlkörpern, J. Reine Angew. Math. 142 (1913), 153–164.

[19] P. Samuel, Algebraic Theory of Numbers, Houghton Mifflin Co., 1970, Translated from the French by A. Silberger.

[20] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 44 (1985), 483–494.

[21] J. A. Serret, Sur un théorème relatif aux nombres entiers, J. Math. Pures Appl. 5 (1848), 12–14.

[22] L. R. Shenton, Linear difference equations and generalized continuants part I: Algebraic developments, Fibonacci Quart. 10 (1972), 585–634.

[23] H. D. Ursell, Simultaneous linear recurrence relations with variable coefficients, Proc. Edinb. Math. Soc. (2) 9 (1958), 183–206.

[24] S. Wagon, Editor’s corner: the Euclidean algorithm strikes again, Amer. Math. Monthly 97 (1990), 125–129.

[25] K. S. Williams, On finding the solutions of n = au^{2} + buv + cv^{2} in integers u and v, Util. Math. 46 (1994), 3–19.

[26] K. S. Williams, Some refinements of an algorithm of Brillhart, in Number Theory (Halifax, NS, 1994), CMS Conf. Proc., Vol. 15, Amer. Math. Soc., 1995, pp. 409–416.

[27] Wolfram Research, Inc., Mathematica Edition: Version 8.0, Wolfram Research, Inc., 2010.

[28] D. Zagier, A one-sentence proof that every prime p ≡ 1 (mod 4) is a sum of two squares, Amer. Math. Monthly 97 (1990), 144.

2010 Mathematics Subject Classification: Primary 11E25, Secondary 11D85, 11A05. Keywords: Fermat’s two-square theorem; continuant; generalized continuant; integer representation.

(Concerned with sequences \underline{A003655} and \underline{A014602}.)

Received July 18 2014; revised version received April 21 2015; May 27 2015. Published in Journal of Integer Sequences, May 31 2015.

Return to Journal of Integer Sequences home page.