is said to be a quadratic surd when there exist 
-integers
such that 
is not a perfect square and is a root of the polynomial 
.
In such a case, we can additionally require that 
and
are coprime. This unique polynomial
is said to be "associated" to . When 
,
we say that is a quadratic integer.
To any polynomial 
, defined as ,
we associate the matrix 
. With this convention, we have:
over the polynomial 
,
defined by:
, we have following formulae:
are
coprime if and only if are coprime.
.
be a quadratic surd
and consider the "complete quotients" 
defined
in 2.1. Then it exists a rank 
where 
,
and this relation remains true for all 
. The corresponding polynomials
are said to be reduced.
, the confrac expansion of these
numbers must become different somewhere. If, for a given 
, we
have 
then 
.
On the contrary, 
implies 
so that 
.
In any case, we have a such that 
.
Using formulae 3.1, we have 
,
, 
and, since 
, 
.
Thus 
is a reduced polynomial and, by induction, all the
where .
such that 
. We have 
and therefore, the number is a fixed point of the fractional-linear
transform 
. Since
is a quadratic surd, and so is as a fractional
linear function of .
The converse part follows from lemma 3.3
and proposition 3.6.
is purely periodic if and only if 
and the
associated polynomial 
is reduced.
are reduced
when 
is reduced. These polynomials share the same discriminant
and verify 
. Thus 
and 
are divisors of 
.
The number of such polynomials is therefore finite, we must have 
for some and the (ultimate) periodicity is proven. If 
,
we have 
.
Thus 
can be obtained by a -translation acting over
. These polynomials being reduced, this translation can
only be the identity. By induction, we arrive to 
and therefore to 
as required.
On the contrary, if the confrac expansion is purely periodic,
has to verify 
for some 
. Since
, we must have 
. Describing 
as
, the polynomial is proportional to 
.
From theorem 2.6, we have 
, 
and 
. This implies that the other root
lies in 
.
be a quadratic surd,
a matrix such that 
. If
verifies conditions 2.7, the confrac
expansion of is purely periodic and is a power of
where is the (smallest) period of . is decomposable
as a product 
. By the unique
factorization theorem, the confrac expansion of is 
.
But any period is obtained by repetition of the fundamental period
and the property follows.
is a square-free natural integer and 
,
the set of the quadratic integers that belong to 
is 
, i.e. the set of the 
where 
are -integers. When 
, this
set enlarges to 
, i.e. the
set of the 
where
are -integers with the same parity.
will be referred as quadratic integers of the first
kind, while the 
where are
odd and 
will be referred as quadratic integers
of the second kind. Defining 
as 
, the discriminant
of the associated polynomial is 
in
the first case, and 
in the second case.
. Moreover,
the expansions of 
and of 
(when 
)
are purely periodic.
and 
, we have 
and 
.
From proposition 3.6, the expansions of
and are purely periodic. By -translations,
this result can be propagated to all other quadratic integers.
not
being a perfect square, it exists an integer sequence 
and if 
another integer sequence 
such that
 |
 |
 |
|
 |
|
 |
(resp. 
) occurs only at a period boundary
(
, resp. 
).
For others quadratic integers, the period starts with the palindromic
part. For example:
 |
|
 |
|
 |
|
 |
is purely periodic, we
have
and the matrix 
is a (may be empty) product of matrices 
. Thus is
a root of the polynomial
is a quadratic integer, the coefficients have to be
-integers. Especially, 
. From theorem
2.6, we have 
and 
or we have 
and 
, so that 
. In any case,
we have and is symmetrical. Since each matrix
is symmetrical, we have 
.
By theorem 2.6, such a factorization is unique,
proving the palindromic property in the special case of or
. By -translations, this result can be propagated to
all other quadratic integers.
Let 
be a quotient occurring in the confrac expansion of
. We have 
from 3.10 and 
from 3.4. Since all 
are even, we obtain that 
. Therefore 
implies 
and 
, i.e. 
.
Finally, let be a quotient occurring in the confrac expansion
of . We have 
from 3.10 and 
from 3.4. Since all
are odd, we obtain that 
. Therefore 
implies and 
, i.e. .
and 
.
as in theorem 3.12. Then
. The same palindromic property
holds for the polynomials related to ., the property is obvious if 
, i.e. 
.
Otherwise, define 
, 
for 
, 
for 
and
go to infinity using 
. Construct 
,
,
and
so on. For integer values of , the 
are the polynomials
of proposition 3.6, while 
.
For any polynomial , we have 
and therefore the relation
. Since 
and
, relation 3.5
is extendable by induction to all , 
.
When 
is even, we have 
. Therefore
and the property holds. When is odd, we have 
.
Therefore
as required.
Conversely, if 
holds when 
, an obvious recurrence shows that the sequence
of quotients 
will conduct back to : 
and 
are periods
of the confrac expansion of and we must have 
. The
odd case is similar.
In the case, the parity of 
becomes odd and a slight
change has to be done. If 
, we define 
,
, and others 
as before. Then 
,
while 
, and relation 3.5
starts to be true at 
instead of . Everything else
remains unchanged.
By theorem 3.14, we can stop the computation
of the successive quotients associated to (or ) when
we encounter the palindromic property 3.4
and complete the period by symmetry. Using 3.4,
we obtain LISTING 2, where
is either 
(first kind) or itself when 
(second kind).
is odd (even pattern, without middle
element), then is explicitely obtained as a sum of two squares.
Therefore the square-free part of cannot contain any prime 
.
is prime, 
is odd (and polynomial 
gives an explicit decomposition of
as a sum of squares).
into another process. Let us consider the set 
:
by
is : iterate 
as much as
you can, then do a (single) 
and repeat. It is clear that
a polynomial having its both roots in 
could
not be a 
. Conversely, a polynomial 
is a 
or a 
according to 
or not.
Let us start with 
(formerly designed as 
) and consider the sequence
. It is obvious that polynomials
obtained by a -move are the reduced polynomials occurring
in the confrac expansion of . In theorem 3.14,
the existence of a 
minimal such that 
has been proven. Thus
 |
(3.6) |
and therefore for all , 
.
At the center of the loop, it exists a such that either
, but all 
are odd.
Assuming 
leads to 
, so
that 
. Since
is prime, we should have 
, i.e. 
.
But 
is minimal. The occurrence of (iii) is therefore proven
and we have 
.
Therefore, the reduced polynomial verifies the characteristic property
of in 3.14 and the period of
is odd.
process relative to is:
. When 
is prime, 
is even
and 
. Since is
ever odd, this period length is even, explaining the non-occurrence
of case (i).
The algorithm described by proposition 3.18
is not the most efficient to decompose a prime (
) into
a sum of squares. Euclidean algorithm is indeed fast... relative to
the size of 
, but the pattern can be huge relative to
. This problem is addressed by the Cornacchia algorithm.
. Define 
and 
. Then, for all 
,
when 
(i.e. 
when 
(i.e. 
.
with 
.
Thus 
.