Prove that if
divides
, then
divides
, where
denotes Euler’s totient function.
First, note that the theorem is trivial for
. In the remainder we will assume that
is not one of these.
By the Fundamental Theorem of Arithmetic, every integer
can be expressed as a finite and nonempty product of primes
in a unique way (up to order). We will call the number
of distinct prime factors of
the length of
.
Let
and
be integers such that
. We wish to show that
; we will proceed by induction on the length of
.
For the base case, note that if
has length 1 then
for some nonnegative integer
. Moreover, since
we have
for some nonnegative integer
with
. Then
, so that
.
Suppose now that the proposition is true for all integers of length
, and let
be an integer of length
. Then we may factor
as
where
is a prime not dividing
and
has length
. Now if
, we may factor
as
for some
and
dividing
. Since
has length
, we have
for some h. Thus
so that
. By induction, for all integers
we have that if
then
. 
First, note that the theorem is trivial for
By the Fundamental Theorem of Arithmetic, every integer
Let
For the base case, note that if
Suppose now that the proposition is true for all integers of length
= | ||
= | ||
= |
No comments:
Post a Comment