Cryptography Reference
In-Depth Information
≥
Theorem 2.17
If
n
1
and n
2
are relatively prime positive integers
2
then
φ(
n
1
n
2
)
=
φ(
n
1
)φ(
n
2
)
.
Proof
This follows from Theorem 2.14 which, in particular, gives a bijection
between
Z
n
1
n
2
and
Z
n
1
× Z
n
2
.
The preceding theorem, together with the fundamental theorem of arithmetic,
reduces the computation of
p
k
,
φ(
n
)
to the case in which
n
is a prime power. If
n
=
where
p
is prime and
k
>
0, the only numbers between 1 and
n
which are not
p
k
−
1
p
p
k
, so that
p
k
p
k
p
k
−
1
.
relatively prime to
n
are
p
,
2
p
,
3
p
,...,
=
φ(
)
=
−
From this, using the multiplicativity of
φ
,wehave:
=
i
=
1
p
e
i
Theorem 2.18
If n
is the prime factorization of n, then
i
1
k
1
p
i
φ(
n
)
=
n
−
.
i
=
1
)
=
i
=
1
φ(
p
e
i
i
Proof
Bearing in mind the previous remark we have that
φ(
n
)
=
i
=
1
(
)
=
i
=
1
(
p
e
i
i
p
i
)
=
i
=
1
p
e
i
n
i
=
1
(
p
e
i
i
p
e
i
−
1
i
p
e
i
i
1
1
−
−
(
1
−
p
i
)
=
1
−
p
i
)
.
i
We next record a useful consequence of the multiplicativity of the
φ
-function:
Proposition 2.8
d
|
n
φ(
d
)
=
n.
)
=
d
|
n
φ(
Proof
Let
f
(
n
d
)
, where
d
runs on the set of the positive divisors of
n
.
We have to show that
f
n
and, in order to do that, we first show that
f
is a
multiplicative function, i.e., that
f
(
n
)
=
1.
Observe that the divisors of
n
1
n
2
can be written in a unique way in the form
d
1
d
2
where
d
1
|
(
n
1
n
2
)
=
f
(
n
1
)
f
(
n
2
)
whenever gcd
(
n
1
,
n
2
)
=
n
1
and
d
2
|
φ
n
2
and so, bearing in mind that
is multiplicative we have:
⎛
⎝
⎞
⎛
⎝
⎞
d
1
|
n
1
,
d
2
|
n
2
φ(
⎠
⎠
=
f
(
n
1
n
2
)
=
d
1
)φ(
d
2
)
=
d
1
|
n
1
φ(
d
1
)
d
2
|
n
2
φ(
d
2
)
f
(
n
1
)
f
(
n
2
)
=
i
=
1
p
e
i
Now let
n
be the prime factorization of
n
. Then, by the multiplicativity
)
=
i
=
1
i
p
e
i
i
of
f
we have that
f
(
n
f
(
)
, so that it suffices to prove that
f
is the
p
e
p
e
whenever
p
is prime. But, as we
identity on prime powers, i.e., that
f
(
)
=
p
i
p
i
p
i
−
1
for
i
have seen,
φ(
)
=
−
≥
1 and hence we have:
e
e
p
e
p
i
p
i
p
i
−
1
p
e
f
(
)
=
0
φ(
)
=
1
+
1
(
−
)
=
,
i
=
i
=
which completes the proof.
