# Engel Series and Cohen-Egyptian  Fraction Expansions

Authors: Vichian Laohakosol; Tuangrat Chaichana; Jittinart Rattanamoong; Narakorn Rompurk Kanasri
Journal: International Journal of Mathematics and Mathematical Sciences
 (2009)

---

## Abstract

Two kinds of series representations, referred to as the Engel series and the Cohen-Egyptian fraction expansions, of elements in two different fields, namely, the real number and the discrete-valued non-archimedean fields are constructed. Both representations are shown to be identical in all cases except the case of real rational numbers.


---

## Body

## 1. Introduction

It is well known [1] that each nonzero real number can be uniquely written as an Engel series expansion, or ES expansion for short, and an ES expansion represents a rational number if and only if each digit in such expansion is identical from certain point onward. In 1973, Cohen [2] devised an algorithm to uniquely represent each nonzero real number as a sum of Egyptian fractions, which we refer to as its Cohen-Egyptian fraction (or CEF) expansion. Cohen also characterized the real rational numbers as those with finite CEF expansions. At a glance, the shapes of both expansions seem quite similar. This naturally leads to the question whether the two expansions are related. We answer this question affirmatively for elements in two different fields. In Section 2, we treat the case of real numbers and show that for irrational numbers both kinds of expansion are identical, while for rational numbers, their ES expansions are infinite, periodic of period 1, but their CEF expansions always terminate. In Section 3, we treat the case of a discrete-valued non-archimedean field. After devising ES and CEF expansions for nonzero elements in this field, we see immediately that both expansions are identical. In Section 4, we characterize rational elements in three different non-archimedean fields.


## 2. The Case of Real Numbers

Recall the following result, see, for example, Kapitel IV of [1], which asserts that each nonzero real number can be uniquely represented as an infinite ES expansion and rational numbers have periodic ES expansions of period 1.Theorem 2.1.
EachA∈ℝ∖{0} is uniquely representable as an infinite series expansion, called its Engel series (ES) expansion, of the form
(2.1)A=a0+∑n=1∞1a1a2⋯an,
where
(2.2)a0={[A],ifA∉ℤ,A-1ifA∈ℤ,a1≥2,an+1≥an(n≥1).
Moreover, A∈ℚ if and only if an+1=an(≥2) for all sufficiently large n.Proof.
DefineA1=A-a0, then 0<A1≤1. If An≠0(n≥1) is already defined, put
(2.3)an=1+[1An],(2.4)An+1=anAn-1.
Observe that an is the least integer >1/An and
(2.5)1an<An≤1an-1.
We now prove the folowing.Claim 2.
We have0<⋯≤An+1≤An≤⋯≤A2≤A1≤1.Proof.
First, we show thatAn>0 for all n≥1 by induction. If n=1, we have seen that A1>0. Assume now that An>0 for n≥1. By (2.3), we see that an∈ℕ. Since
(2.6)An+1=anAn-1=(An-1an)an
and 1/an<An, we have An+1>0. If there exists k∈ℕ such that Ak+1>Ak, then
(2.7)akAk-1=Ak+1>Ak
and so ak-1>1/Ak, contradicting the minimal property of an and the Claim is proved.From the Claim and (2.3), we deduce that a1≥2 and an+1≥an(n≥1). Iterating (2.4), we get
(2.8)A1=1a1+1a1a2+⋯+1a1a2⋯an+An+1a1a2⋯an.
To establish convergence, let
(2.9)Bn=1a1+1a1a2+⋯+1a1a2⋯an(n≥1).
Since An>0 and an∈ℕ for all n≥1, the sequence of real numbers (Bn) is increasing and bounded above by A1. Thus, limn→∞Bn exists and so
(2.10)1a1a2⋯an→0(n→∞).
By the Claim,
(2.11)0<An+1a1a2⋯an≤1a1a2⋯an→0(n→∞),
showing that any real number has an ES expansion. To prove uniqueness, assume that we have two infinite such expansions such that
(2.12)a0+∑n=1∞1a1a2⋯an=b0+∑n=1∞1b1b2⋯bn,
with the restrictions a0∈ℤ,a1≥2,an+1≥an(n≥1) and the same restrictions also for the bn's. From the restrictions, we note that
(2.13)0<A1:=∑n=1∞1a1a2⋯an≤1.
If A1=1, then by (2.12) we also have ∑n≥11/b1b2⋯bn=1, forcing a0=b0. If 0<A1<1, then (2.12) shows that 0<∑n≥11/b1b2⋯bn<1, forcing again a0=b0. In either case, cancelling out the terms a0,b0 in (2.12) we get
(2.14)A1:=∑n=1∞1a1a2⋯an=∑n=1∞1b1b2⋯bn.
Since an+1≥an, then
(2.15)a1A1-1=1a2+1a2a3+1a2a3a4+⋯≤1a1+1a1a2+1a1a2a3+⋯=A1,
so 0<a1-1/A1≤1. But there is exactly one integer a1 satisfying these restrictions. Thus, a1=b1. Cancelling out the terms a1 and b1 in (2.14) and repeating the arguments we see that ai=bi for all i.
Concerning the rationality characterization, if its ES expansion is infinite periodic of period1, it clearly represents a rational number. To prove its converse, let A=a/b∈ℚ∖{0}. Since
(2.16)A1=A-a0=a-ba0b,
we see that A1 is a rational number in the interval (0,1] whose denominator is b. In general, from (2.4), we deduce that each An(n≥1) is a rational number in the interval (0,1] whose denominator is b. But the number of rational numbers in the interval (0,1] whose denominator is b is finite implying that there are two least suffixes h,k∈ℕ such that Ah+k=Ah. Thus, by (2.3), we have ah+k=ah. From (2.2), we know that the sequence {an} is increasing. We must then have k=1 and the assertion follows.Remark 2 s.
In passing, we make the following observations.(a)
Forn≥1, we have
(2.17)an+1=an⟸An+1=An⇔anAn-1=An⇔an=1+1An⇔1An∈ℤ.(b)
IfA∈ℚc, then An∈ℚc and so 1/An∉ℚ for all n≥1.(c)
IfA∈ℤ, then its ES expansion is
(2.18)A=A-1+12+122+123+⋯.To construct a Cohen-Egyptian fraction expansion, we proceed as in [2] making use of the following lemma.Lemma 2.2.
For anyy∈(0,1), there exist a unique integer n≥2 and a unique r∈ℝ such that
(2.19)1=ny-r,0≤r<y.Proof.
Letn=⌈1/y⌉∈ℕ and r=ny-1. Put 〈1/y〉:=n-1/y∈[0,1) and so
(2.20)r=ny-1=y〈1y〉∈[0,y).
To prove uniqueness, assume  ny-r=1=my-s  so that
(2.21)1+1y>n=1+ry≥1y.
Since there is only one integer with this property, we deduce n=m and consequently, r=s proving the lemma.Theorem 2.3.
EachA∈ℝ∖{0} is uniquely representable as a CEF expansion of the form
(2.22)A=n0+∑k=1∞1n1n2⋯nk,
subject to the condition
(2.23)n0∈ℤ,n1≥2,nk+1≥nk(k≥1),
and no term of the sequence appears infinitely often. Moreover, each CEF expansion terminates if and only if it represents a rational number.Proof.
To construct a CEF expansion forA∈ℝ∖{0}, define
(2.24)r0=A-n0∈[0,1).
If r0=0, then the process stops and we write A=n0. If r0≠0, by Lemma 2.2, there are unique n1∈ℕ and r1∈ℝ such that
(2.25)1=n1r0-r1,0≤r1<r0,n1≥2.
Thus,
(2.26)A=n0+r0=n0+1n1+r1n1.
If r1=0, then the process stops and we write A=n0+1/n1. If r1≠0, by Lemma 2.2, there are n2∈ℕ and r2∈ℝ such that
(2.27)1=n2r1-r2,0≤r2<r1,n2≥n1,
the last inequality being followed from n1=⌈1/r0⌉,n2=⌈1/r1⌉, and r1<r0. Observe also that
(2.28)A=n0+1n1+1n1n2+r2n1n2.
Continuing this process, we get
(2.29)A=n0+1n1+1n1n2+⋯+1n1n2⋯nk+rkn1n2⋯nk,
with
(2.30)1=niri-1-ri,1>ri-1>ri≥0,2≤ni≤ni+1(i=1,2,…).
If some rk=0, then the process stops, otherwise the series convergence follows at once from
(2.31)|rkn1n2⋯nk|→0(k→∞).
To prove uniqueness, let
(2.32)n0+∑k=1∞1n1n2⋯nk=A=m0+∑k=1∞1m1m2⋯mk,
with the restrictions (2.23) on both digits ni and mj. Now
(2.33)∑k≥11n1n2⋯nk≤∑k≥112k=1.
It is clear that the restrictions (2.23) imply the strict inequality in (2.33). This also applies to the right-hand sum in (2.32). Equating integer and fractional parts in (2.32), we get
(2.34)n0=m0,∑k=1∞1n1n2⋯nk=∑k=1∞1m1m2⋯mk=:w,say.
Since nk+1≥nk, then
(2.35)n1w-1=1n2+1n2n3+1n2n3n4+⋯≤1n1+1n1n2+1n1n2n3+⋯=w,
so  0<n1-1/w≤1. But there is exactly one integer n1 satisfying these restrictions. Then n1=m1 and
(2.36)∑k≥21n2⋯nk=∑k≥21m2⋯mk.
Proceeding in the same manner, we conclude that ni=mi for all i.
Finally, we look at its rationality characterization. IfA∈ℚ, then r0∈ℚ, say r0:=p/q, where p,q∈ℕ. From (2.30), we see that each ri is a rational number whose denominator is q. Using this fact and the second inequality condition in (2.30), we deduce that rj=0 for some j≤p, that is, the expansion terminates. On the other hand, it is clear that each terminating CEF expansion represents a rational number. Now suppose that A is irrational and there is a j and integer n such that ni=n for all i≥j. Then
(2.37)A=n0+∑k=1j1n1n2⋯nk+1n1n2⋯nj∑k=1∞1nk.
Since ∑k≥11/nk=1/(n-1), it follows that A is rational, which is impossible.The connection and distinction between ES and CEF expansions of a real number are described in the next theorem.Theorem 2.4.
LetA∈ℝ∖{0} and the notation be as set out in Theorems 2.1 and 2.3.
(i) IfA∈ℚ, then its ES expansion is infinite periodic of period 1, while its CEF expansion is finite. More precisely, for A∈ℚ∖ℤ, let its ES and CEF expansions be, respectively,
(2.38)A=a0+∑n=1∞1a1a2⋯an=n0+∑k=1∞1n1n2⋯nk.
If m is the least positive integer such that 1/Am∈ℤ, then
(2.39)a0=n0,a1=n1,…,am-1=nm-1,am=nm+1,am=am+i(i≥1),
and the digits ni terminate at nm.
(ii) IfA∈ℝ∖ℚ, then its ES and its CEF expansions are identical.Proof.
Both assertions follow mostly from Theorems2.1, 2.3, and Remark (b) except for the result related to the expansions in (2.38) which we show now.
LetA∈ℚ∖ℤ and let m be the least positive integer such that 1/Am∈ℤ. We treat two seperate cases.
Case 1 (m=1).
In this case, we have1/A1∈ℤ and a1=1+[1/A1]=1+1/A1. Since r0=A-n0=A-[A]=A-a0=A1, we get n1=1/A1 and so a1=n1+1. We have r1=n1r0-1=0, and so the CEF expansion terminates. On the other hand, by Remark (a) after Theorem 2.1, we have a1=ai(i≥2).Case 2 (m>1).
Thus,1/A1∉ℤ and A1=r0. By Lemma 2.2, we have a1=n1. For 1≤i≤m-2, assume that Ai=ri-1 and ai=ni. Then
(2.40)Ai+1=aiAi-1=niri-1-1=ri.
Since 1/Ai+1∉ℤ, again by Lemma 2.2, ai+1=ni+1. This shows that a1=n1,…,am-1=nm-1. Since 1/Am∈ℤ, we have am=1+[1/Am]=1+1/Am and thus
(2.41)Am=am-1Am-1-1=nm-1rm-2-1=rm-1.
From the construction of CEF, we know that nm=⌈1/rm-1⌉. Thus, nm=1/Am showing that am=nm+1. Furthermore, rm=nmrm-1-1=0, implying that the CEF terminates at nm, and by Remark (a) after Theorem 2.1, am=am+i(i≥1).


## 3. The Non-Archimedean Case

We recapitulate some facts about discrete-valued non-archimedean fields taken from [3, Chapter 4]. Let K be a field complete with respect to a discrete non-archimedean valuation |·| and 𝒪:={A∈K;|A|≤1} its ring of integers. The set 𝒫:={A∈K;|A|<1} is an ideal in 𝒪 which is both a maximal ideal and a principal ideal generated by a prime element π∈K. The quotient ring 𝒪/𝒫 is a field, called the residue class field. Let 𝒜⊂𝒪 be a set of representatives of 𝒪/𝒫. Every A∈K∖{0} is uniquely of the shape(3.1)A=∑n=N∞bnπn(bn∈𝒜,bN≠0)
for some N∈ℤ, and define the orderv(A) of A by |A|=2-v(A)=2-N, with v(0):=+∞. The head part〈A〉 of A is defined as the finite series(3.2)〈A〉=∑n=v(A)0bnπnifv(A)≤0,and0otherwise.
Denote the set of all head parts by(3.3)S:={〈A〉;A∈K}.
The Knopfmachers' series expansion algorithm for series expansions in K [4] proceeds as follows. For A∈K, let
(3.4)a0:=〈A〉∈S.
Define
(3.5)A1:=A-a0.
If An≠0(n≥1) is already defined, put(3.6)an=〈1An〉,An+1=(An-1an)snrn
if an≠0, where rn and sn∈K∖{0} which may depend on a1,…,an. Then for n≥1(3.7)A=a0+A1=⋯=a0+1a1+r1s11a2+⋯+r1⋯rn-1s1⋯sn-11an+r1⋯rns1⋯snAn+1.
The process ends in a finite expansion if some An+1=0. If some an=0, then An+1 is not defined. To take care of this difficulty, we impose the condition(3.8)v(sn)-v(rn)≥2v(an)-1.
Thus(3.9)A=a0+1a1+∑n=1∞r1⋯rns1⋯sn·1an+1.
When rn=1,sn=an, the algorithm yields a well-defined (with respect to the valuation) and unique series expansion, termed non-archimedean Engel series expansion. Summing up, we have the following.Theorem 3.1.
EveryA∈K∖{0} has a finite or an infinite convergent non-archimedean ES expansion of the form
(3.10)A=a0+∑n=1∞1a1a2⋯an,
where the digits an are subject to the restrictions
(3.11)a0=〈A〉∈S,an∈S,v(an)≤-n,v(an+1)≤v(an)-1(n≥1).Now we turn to the construction of a non-archimedean Cohen-Egyptian fraction expansion, in the same spirit as that of the real numbers, that is, by way of Lemma2.2. To this end, we start with the following lemma.Lemma 3.2.
For anyy∈K∖{0} such that v(y)≥1, there exist a unique n∈S such that v(n)≤-1 and a unique r∈K such that
(3.12)1=ny-r,v(r)≥v(y)+1(i.e.,0≤|r|<|y|).Proof.
Letn=〈1/y〉. Then v(n)=v(1/y)=-v(y)≤-1. Putting r=ny-1, we show now that v(r)≥v(y)+1. Since n=〈1/y〉, we have
(3.13)1y=n+∑k≥1ckπk,
where ck∈𝒜, and so
(3.14)ny-1=-y∑k≥1ckπk.
Thus
(3.15)v(r)=v(ny-1)=v(-y)+v(∑k≥1ckπk)≥v(y)+1>v(y).
To prove the uniqueness, assume that there exist n1∈S such that v(n1)≤-1 and r1∈K such that
(3.16)1=n1y-r1,0≤|r1|<|y|.
From ny-r=1=n1y-r1, we get (n-n1)y=r-r1. If n≠n1, since n,n1∈S we have |n-n1|≥1. Using |y|>|r-r1|, we deduce that
(3.17)|r-r1|<|y|≤|n-n1||y|=|r-r1|,
which is a contradiction. Thus, n=n1 and so r=r1.For a non-archimedean CEF expansion, we now prove the following.Theorem 3.3.
Eachy∈K∖{0} has a non-archimedean CEF expansion of the form
(3.18)y=n0+∑k=1∞1n1n2⋯nk,
where
(3.19)nk∈S,v(nk)≤-k,v(nk+1)≤v(nk)-1(k≥1).
This series representation is unique subject to the digit condition (3.19).Proof.
Definen0=〈y〉 and r0=y-n0. Then v(r0)≥1. If r0=0, the process stops and we write y=n0. If r0≠0, by Lemma 3.2, there are n1∈S and r1∈K such that
(3.20)n1=〈1r0〉,r1=n1r0-1,
where v(n1)≤-1 and v(r1)≥v(r0)+1. So
(3.21)y=n0+r0=n0+1n1+r1n1.
If r1=0, the process stops and we write y=n0+1/n1. If r1≠0, by Lemma 3.2, there are n2∈S and r2∈K such that
(3.22)n2=〈1r1〉,r2=n2r1-1,
where v(n2)≤-1 and v(r2)≥v(r1)+1. So
(3.23)y=n0+1n1+1n1n2+r2n1n2.
Continuing the process, in general,
(3.24)nk=〈1rk-1〉,rk=nkrk-1-1,y=n0+1n1+1n1n2+⋯+1n1n2⋯nk+rkn1n2⋯nk,
where
(3.25)nk∈S,v(nk)≤-1,v(rk)≥v(rk-1)+1(k≥1).
Thus,
(3.26)v(nk+1)=-v(rk)≤-v(rk-1)-1=v(nk)-1(k≥1).
We observe that the process terminates if rk=0. Next, we show that v(nk)≤-k(k≥1). By construction, we have v(n1)≤-1. Assume that v(nk)≤-k, then
(3.27)v(nk+1)≤v(nk)-1≤-k-1.
Regarding convergence, consider
(3.28)v(rkn1n2⋯nk)=-v(n1)-v(n2)-⋯-v(nk)+v(rk)=-v(n1)-v(n2)-⋯-v(nk)-v(nk+1)≥1+2+⋯+k+(k+1)→∞(k→∞).
It remains to prove the uniqueness. Suppose that x∈K∖{0} has two such expansions
(3.29)x=n0+∑j1n1n2⋯nj=m0+∑i1m1m2⋯mi.
Since v(∑j1/n1n2⋯nj)=v(1/n1)≥1 and n0∈S, we have n0=〈y〉. Similarly, m0=〈y〉 yielding by uniqueness n0=m0 and ∑j≥11/n1n2⋯nj=∑i≥11/m1m2⋯mi. Putting
(3.30)ω:=∑j≥11n1n2⋯nj=∑i≥11m1m2⋯mi,
we have n1ω=1+∑j≥21/n2⋯nj and so
(3.31)1=n1ω-∑j≥21n2⋯nj,v(∑j≥21n2⋯nj)=v(1n2)=-v(n2)≥-v(n1)+1=v(ω)+1.
By Lemma 3.2, since n1 is the unique element in S with such property, we deduce n1=m1. Continuing in the same manner, we conclude that the two expansions are identical.It is clear that the construction of non-archimedean ES and CEF expansions is identical which implies at once that the two representations are exactly the same in the non-archimedean case.


## 4. Rationality Characterization in the Non-Archimedean Case

In the case of real numbers, we have seen that both ES and CEF expansions can be used to characterize rational numbers with quite different outcomes. In the non-archimedean situation, though ES and CEF expansions are identical, their use to characterize rational elements depend significantly on the underlying nature of each specific field. We end this paper by providing information on the rationality characterization in three different non-archimedean fields, namely, the field ofp-adic numbers and the two function fields, one completed with respect to the degree valuation and the other with respect to a prime-adic valuation.The following characterization of rational numbers byp-adic ES expansions is due to Grabner and Knopfmacher [5].Theorem 4.1.
Letx∈pℤp∖{0}. Then x is rational, x=α/β, if and only if either the p-adic ES expansion of x is finite, or there exist an m and an s≥m, such that
(4.1)am+j=ps+j+1-γps+j(j=0,1,2,…),
where γ∣β.Now for function fields, we need more terminology. Let𝔽 denote a field and π(x) an irreducible polynomial of degree d over 𝔽. There are two types of valuation in the field of rational functions 𝔽(x), namely, the π(x)-adic valuation |·|π, and the degree valuation |·|1/x defined as follows. From the unique representation in 𝔽(x),(4.2)f(x)g(x)=π(x)mr(x)s(x),f(x),g(x),r(x),s(x)∈𝔽[x]∖{0};π(x)∤r(x)s(x),m∈ℤ,
set
(4.3)|0|π=0,|f(x)g(x)|π=2-md;|0|1/x=0,|f(x)g(x)|1/x=2degf(x)-degg(x).
Let 𝔽((π)) and 𝔽((1/x)) be the completions of 𝔽(x), with respect to the π(x)-adic and the degree valuations, respectively. The extension of the valuations to 𝔽((π)) and 𝔽((1/x)) is also denoted by |·|π and |·|1/x.For a characterization of rational elements, we prove the following.Theorem 4.2.
The CEF ofy∈𝔽((π)) or in 𝔽((1/x)) terminates if and only if y∈𝔽(x).Proof.
Although the assertions in both fields𝔽((π)) and 𝔽((1/x)) are the same, their respective proofs are different. In fact, when the field 𝔽 has finite characteristic, both results have already been shown in [6] and the proof given here is basically the same.
We use the notation of the last section with added subscriptsπ or 1/x to distinguish their corresponding meanings.
If the CEF ofy in either field is finite, then y is clearly rational. It remains to prove the converse and we begin with the field 𝔽((π)). Assume that y∈𝔽(x)∖{0}. By construction, each rk∈𝔽(x) and so can be uniquely represented in the form
(4.4)rk=π(x)v(rk)pk(x)qk(x),
where pk(x),qk(x)(≠0)∈𝔽[x] with gcd(pk(x),qk(x))=1,π(x)∤pk(x)qk(x). Since nk=〈1/rk-1〉∈Sπ and v(nk)≤-k, it is of the form
(4.5)nk=sv(nk)(x)π(x)v(nk)+sv(nk)+1(x)π(x)v(nk)+1+⋯+s-1(x)π(x)-1+s0(x)=:mk(x)π(x)v(nk),
where sv(nk)(x),…,s0(x) are polynomials over 𝔽, not all 0, of degree <d and mk(x)∈𝔽[x]. Thus,
(4.6)|nk|1/x≤max{|sv(nk)(x)π(x)v(nk)|1/x,|sv(nk)+1(x)π(x)v(nk)+1|1/x,…,|s-1(x)π(x)-1|1/x,|s0(x)|1/x}≤2d-1,
yielding
(4.7)|mk(x)|1/x≤2d-dv(nk)-1.
By construction, we have
(4.8)rk=nkrk-1-1.
Substituting (4.4) and (4.5) into (4.8) and using v(rk-1)=-v(nk) lead to
(4.9)π(x)-v(nk+1)pk(x)qk-1(x)=qk(x)(mk(x)pk-1(x)-qk-1(x)).
Since gcd(π(x)-v(nk+1)pk(x),qk(x))=1, it follows that qk(x)∣qk-1(x), and so successively, we have
(4.10)|qk(x)|1/x≤|qk-1(x)|1/x≤⋯≤|q1(x)|1/x,
which together with (4.9) yield
(4.11)|pk(x)|1/x≤|π(x)|1/xv(nk+1)max{|mk(x)pk-1(x)|1/x,|q1(x)|1/x}.
Using (3.19) and (4.7), we consequently have
(4.12)|pk(x)|1/x≤2d(v(nk)-1)max{2d-dv(nk)-1|pk-1(x)|1/x,|q1(x)|1/x}≤max{12|pk-1(x)|1/x,|q1(x)|1/x2d(k+1)}.
This shows that |pk(x)|1/x≤(1/2)|pk-1(x)|1/x for all large k which implies that from some k onwards, pk(x)=0, and so rk=0, that is, the expansion terminates.
Finally for the field𝔽((1/x)), assume that y=p(x)/q(x)∈𝔽(x)∖{0}. Without loss of generality, assume degp(x)≥degq(x). By the Euclidean algorithm, we have
(4.13)y=p(x)q(x)=N0(x)+R0(x)q(x):=n0+r0,
where
(4.14)n0:=N0(x)=〈y〉1/x,R0(x)∈𝔽[x],0≤degR0<degq,r0=R0(x)q(x).
From the Euclidean algorithm,
(4.15)q(x)R0(x)=N1(x)+R1(x)R0(x),N1(x),R1(x)∈𝔽[x],0≤degR1<degR0<degq,
which is, in the terminology of Lemma 3.2,
(4.16)1=r0N1+R1q=r0n1-r1.
Again, from the Euclidean algorithm,
(4.17)-q(x)R1(x)=N2(x)+R2(x)R1(x),N2(x),R2(x)∈𝔽[x],0≤degR2<degR1<degR0<degq,
which is, in the terminology of Lemma 3.2,
(4.18)1=r1N2-R2q=r1n2-r2.
Proceeding in the same manner, in general we have
(4.19)rj=(-1)jRjq,0≤degRj<degRj-1<⋯<degR1<degq.
There must then exist k∈ℕ such that degRk=0, that is, Rk∈𝔽∖{0}. Thus, the CEF of y is
(4.20)y=n0+1n1+⋯+1n1⋯nk+rkn1⋯nk=n0+1n1+⋯+1n1⋯nk+1n1⋯nknk+1,
where nk+1=(-1)kRk-1q∈𝔽[x], which is a terminating CEF.



---

*Source: 865705-2009-12-31.xml*