Information Technology Reference
In-Depth Information
t
. By part (3) of Lemma 1 we have
Let
I
=
{
(
m
1
,
···
,m
t
):0
≤
m
i
≤
e
i
}⊆
Z
1
2
n
E
n
≥
1)
Δ
n
(
q
)
(
λ
(
q
)
−
−
c
q|
∗
π
n
−
1
1
2
n
Δ
n
(
q
)
≥
log
2
|
N
(
q
)
|
−
c
−
1
(6)
q
|
∗
π
n
−
1
N
t
t
1
2
n
z
m
i
i
z
m
i
i
Δ
n
=
log
2
−
c
−
1
.
i
=1
i
=1
(
m
1
,··· ,m
k
)
∈I
m
i
not all 0
R
of
π
n
1
,
Δ
n
(
z
)=
(
R/
(
z
))
∗
|
Lemma 4.
For any divisor
z
∈
−
|
.
Proof:
By Lemma 2 the map
f
that takes the sequence associated with
u/z
to
u
is an injection from
U
z
into (
R/
(
z
))
∗
. On the other hand, if
u
∈
R
is a
unit modulo
z
, then by the argument following Lemma 2, there is a
y
∈
R
so
that
y
u
mod
z
and
y/z
has a strictly periodic
π
-adic expansion. Since
y
is
relatively prime to
z
,wehave
y
≡
U
z
,sothat
f
maps
U
z
onto (
R/
(
z
))
∗
.
∈
Lemma 5.
If
z
1
,
···
,z
t
∈
R
are not units and are pairwise relatively prime,
then
t
t
Δ
n
Δ
n
(
z
i
)
.
z
i
=
i
=1
i
=1
Proof Sketch:
By induction it suces to prove the result when
t
=2.Let
z
=
z
1
z
2
. We define
Γ
(
u, v
) to be the element of
U
z
that is congruent to
uz
2
+
vz
1
modulo
z
.Itcanbeshownthat
Γ
induces a one to one, onto function from
U
z
1
×
to
U
z
. It follows that
Δ
n
(
z
1
z
2
)=
Δ
n
(
z
1
)
Δ
∗
(
z
2
).
U
z
2
Lemma 6.
If
z
∈
R
is irreducible and
t
≥
1
,then
Δ
n
(
z
t
)=
t−
1
(
|
N
(
z
)
|
|
N
(
z
)
|−
1)
.
Therefore
t
Δ
n
(
z
i
)=
t
+3
.
|
N
(
z
)
|
i
=0
(
R/
(
z
))
∗
|
t
−
1
(
Proof:
By Lemma 4, it suces to show that
|
=
|
N
(
z
)
|
|
N
(
z
)
|−
1).
R
be a complete set of representatives for
R/
(
z
t−
1
). No two elements
of
V
t−
1
are congruent modulo
z
t−
1
, so no two elements of
zV
t−
1
are congruent
modulo
z
t
.Let
V
t
⊆
Let
V
t−
1
⊆
R
be a complete set of representatives for
R/
(
z
t
) containing
zV
t
.If
zx
zV
t−
1
,then
x
is not congruent to any element of
V
t−
1
modulo
z
t−
1
.Thus
zV
t−
1
contains all the elements of
V
t
that are multiples of
z
.Since
z
is irreducible, the elements of
V
t
that are not relatively prime to
z
t
are exactly
those elements of
V
that are multiples of
z
. Thus by part (1) of Lemma 1,
|
∈
V
t
−
(
R/
(
z
))
∗
|
t
t−
1
=
t−
1
(
=
|
V
t
|−|
V
t−
1
|
=
|
N
(
z
)
|
−|
N
(
z
)
|
|
N
(
z
)
|
|
N
(
z
)
|−
1).