Information Technology Reference
In-Depth Information
We may similarly define the shift and subtract property. It is helpful here to
use rational representations of sequences. If
a
is periodic with minimal period
T
then for some
q
and
f
we have
a
=
f/q
with
0 and gcd(
q, f
)=1.
Then a shift
a
τ
of
a
also corresponds to a rational number of this form, say
a
(
τ
)
=
f
τ
/q
. Moreover, there is an integer
c
τ
so that
a
(
τ
)
=
c
τ
+
N
T−τ
a.
−
q
≤
f
≤
Thus
f
τ
=
c
τ
q
+
N
T−τ
f
. It follows that
N
T−τ
f
f
τ
≡
mod
q.
The set of integers
mod
q, N
2
f
C
f
=
{
f, Nf
mod
q,
···}
is called the
f
th cyclotomic coset modulo
q
relative to
N
(the terms “modulo
q
”
and “relative to
N
” may be omitted if
q
and/or
N
are understood). It follows
that the set of numerators
f
τ
of the
N
-adic numbers associated with the cyclic
shifts of
a
is the
f
th cyclotomic coset modulo
q
relative to
N
.
Now suppose that (
a
+
a
τ
)
τ
=
a
.Let
g/r
be the rational representation of
the
N
-adic number associated with
a
+
a
τ
.Then
g
r
=
d
+
N
τ
f
q
for some integer
d
. In particular, we can take
r
=
q
.Then
g
=
qd
+
N
τ
f
.Thus
g
N
τ
f
mod
q
,sothat
≡
−
g
is in the cyclotomic coset of
f
.
Theorem 7.
The periodic
N
-ary sequence
a
with associated
N
-adic number
f/q
with
gcd(
q, f
)=1
has the arithmetic shift and add property if and only if
G
=
C
f
∪{
0
}
is an additive subgroup of
Z
/
(
q
)
.
Proof (Sketch).
The proof amounts to showing that addition in
G
corresponds
mod
q
to addition of the associated numerators of fractions, and that the integer
multiple of
q
difference does not affect the periodic part.
Corollary 1.
A sequence has the arithmetic shift and add property if and only
if it has the arithmetic shift and subtract property.
How can it be that
C
f
∪{
0
}
is a subgroup of
Z
/
(
q
)? It implies, in particular,
that
C
f
∪{
is closed under multiplication by integers modulo
q
.Ifwetake
q
and
f
so that gcd(
f, q
) = 1, then for any integer
g
,
C
f
∪{
0
}
0
}
is closed under
multiplication by
gf
−
1
modulo
q
,sothat
g
∈
C
f
∪{
0
}
.Thatis,
C
f
∪{
0
}
=
Z
/
(
q
),
and so
C
f
=
. In particular, every nonzero element of
Z
/
(
q
)isof
the form
N
i
f
, hence is a unit. Thus
q
is prime. Moreover, 1
Z
/
(
q
)
−{
}
0
∈
C
f
,sothat
Z
/
(
q
))
∗
=
C
1
=
{
N
i
mod
q, i
=0
,
1
,
···
,q
−
}
.Thatis,
N
is a primitive
(
2
element modulo
q
.
Theorem 8.
Anon-zero
N
-ary sequence has the arithmetic shift and add prop-
erty if and only if it is an
-sequence.
