Cryptography Reference
In-Depth Information
Proof
Let
z
be a primitive
n
th root of unity. Then every
n
th root of unity is a power of
z
and, for 0
i<n
,
z
i
is a primitive
n
th root of unity if and only if gcd(
n,i
)
≤
=
1. Therefore
z
i
)
n
(
x
)
=
(
x
−
0
≤
i<n,
gcd(
n,i
)
=
1
=
and so deg(
n
(
x
))
ϕ
(
n
).
Galois theory implies
n
(
x
)
∈ Q
[
x
] and, since
z
is an algebraic integer, it follows that
n
(
x
)
[
x
].
1
The third fact follows since
x
n
∈ Z
=
n
−
1
z
i
) and each
z
i
has some order
d
n
.
Let
z
be a root of gcd(
n
(
x
)
,
m
(
x
)). Then
z
has order equal to both
n
and
m
, which is
impossible if
n
−
1
i
=
0
(
x
−
|
m
.
Finally, writing
z
d
for some primitive
d
th root of unity, note that
=
x
z
n/d
µ
(
d
)
n/d
(
x
n/d
1)
µ
(
d
)
−
=
−
d
|
n
d
|
n
j
=
1
n/d
x
z
d
n
µ
(
d
)
=
−
d
|
n
j
=
1
n
z
i
n
)
d
|
gcd(
n,i
)
µ
(
d
)
.
=
(
x
−
i
=
1
Since
d
|
n
µ
(
d
) is 0 when
n>
1 and is 1 when
n
=
1 (Theorem 4.7 of [
420
]) the result
follows.
x
2
Exercise
6.1.3
Show
that
1
(
x
)
=
x
−
1
,
2
(
x
)
=
x
+
1,
6
(
x
)
=
−
x
+
1
and
x
l
−
1
x
l
−
2
l
(
x
)
=
+
+···+
x
+
1if
l
is prime.
n
(
x
p
) and that if
p
Exercise 6.1.4
Prove that if
p
|
n
then
pn
(
x
)
=
n
then
pn
(
x
)
=
n
(
x
p
)
/
n
(
x
). Prove that if
n
is odd then
2
n
(
x
)
=
n
(
−
x
).
[Hint: Use part 5 of Lemma
6.1.2
.]
It is well-known that
n
(
x
) is irreducible over
Q
; we do not need this result, so we omit
the proof.
. The greatest common divisor of the polynomials
(
x
n
1)
/
(
x
d
Lemma 6.1.5
Let n
∈ N
−
−
1)
over all
1
≤
d<nsuch that d
|
n is
n
(
x
)
.
Proof
Define
I
={
d
∈ N
:1
≤
d<n,d
|
n
}
. By part 3 of Lemma
6.1.2
,wehave
n
(
x
)
=
=
d
∈
I
d
(
x
)
(
x
n
−
=
lcm(
x
d
−
∈
1)
/f
(
x
) where
f
(
x
)
1:
d
I
). Hence
gcd
x
n
I
.
x
n
−
1
−
1
n
(
x
)
=
I
)
=
:
d
∈
lcm(
x
d
−
1:
d
∈
x
d
−
1
1
One can find more elementary proofs of this fact in any topic on polynomials.
