Information Technology Reference
In-Depth Information
Proof.
We prove by induction on
n
.Thecase
n
= 2 is trivial and hence we
assume that
n
≥
3 and the lemma holds for
n
−
1. For the derivative we have
dH
n
dx
=
nx
n−
1
1)
n−
1
=
n
(
H
n−
1
(
x
)+1)
.
−
n
(
x
−
(2)
By the induction hypothesis we have that
H
n−
1
(
x
)
>
0, for
x>
1. Therefore
using (2) we complete the proof.
Lemma 2.
Let
q
≥
2
be a prime power. Let
a
and
n
≥
2
be positive integers.
Then
>
1
n
1
q
na
1
q
a
1
−
−
.
Proof.
Let
H
n
(
x
) be the real valued function on
R
defined in Lemma 1. Note
that
q
a
>
1and
1)
n
.
H
n
(
q
a
)=
q
na
(
q
a
−
−
−
1
Therefore using Lemma 1 we obtain that
1)
n
.
q
na
1
>
(
q
a
−
−
(3)
Dividing both sides of (3) by
q
na
we complete the proof.
Lemma 3.
Let
r
∈
F
q
[
x
]
be an irreducible polynomial. For positive integers
m
and
e
we have
Φ
(
m
)
(
r
e
)=
Φ
(1)
q
m
(
r
e
)
if
gcd(deg(
r
)
,m
)=1
,
and
q
Φ
(
m
)
(
r
e
)
>Φ
(1)
q
m
(
r
e
)
if
gcd(deg(
r
)
,m
)
>
1
.
q
Proof.
It follows from [4, Lemma 2.2, (iii)] that
(
r
e
)=
q
me
deg(
r
)
1
.
1
q
m
deg(
r
)
Φ
(
m
)
q
−
(4)
If gcd(deg(
r
)
,m
) = 1, then, by Proposition 1,
r
is irreducible over
F
q
m
as well
and hence using [4, Lemma 2.2, (iii)] again we obtain that
Φ
(1)
q
m
(
r
e
)=
Φ
(
m
q
(
r
e
).
Assume that
u
:= gcd(deg(
r
)
,m
)
>
1. It follows from Proposition 1 that the
canonical factorization of
r
into irreducibles over
F
q
m
is of the form
r
=
t
1
t
2
...t
u
,
and deg(
t
1
)=
···
=deg(
t
u
)=deg(
r
)
/u
. Using [4, Lemma 2.2, (iii)] we have
q
m
(
r
e
)=
q
me
deg(
r
)
1
u
1
q
m
deg(
r
)
/u
Φ
(1)
−
.
(5)
Therefore using Lemma 2, (4) and (5) we complete the proof.
