|
I Fundamentals, 6. Arithmetic Functions
Hence
ϕ(
n
)
=
n
− |
T
1
∪ · · · ∪
T
k
| =
n
−
k
i
=
1
|
T
i
| +
1
≤
i
<
j
≤
k
|
T
i
∩
T
j
|
− · · · +
(
−
1
)
k
|
T
1
∩ · · · ∩
T
k
|
.
We have
|
T
i
| =
n
p
i
,
|
T
i
∩
T
j
| =
n
p
i
p
j
, . . . ,
|
T
1
∩ · · · ∩
T
k
| =
n
p
1
· · ·
p
k
.
Finally,
ϕ(
n
)
=
n
1
−
n
i
=
1
1
p
i
+
1
≤
i
<
j
≤
k
1
p
i
p
j
− · · · +
(
−
1
)
k
1
p
1
· · ·
p
k
=
n
1
−
1
p
1
· · ·
1
−
1
p
k
.
Remarks.
(1) A natural generalization of Euler’s totient function is given in Prob-
lem 6.1.6; hence it is possible to derive the properties contained in Theorems
6.4.1-6.4.3 directly from the results of this problem.
(2) Writing the formula in Theorem 6.4.3 as
ϕ(
n
)
=
n
p
1
· · ·
p
k
(
p
1
−
1
)
· · ·
(
p
k
−
1
),
it follows that
ϕ(
n
)
is an even integer for any
n
≥
3.
Problem 6.4.1.
Prove that there are infinitely many even positive integers k such
that the equation
ϕ(
n
)
=
k has no solution.
(Schinzel
4
)
Solution.
Take
k
=
2
·
7
m
,
m
≥
1. If
n
=
p
α
1
1
· · ·
p
α
h
h
, then
ϕ(
n
)
=
p
α
1
1
1
−
1
p
1
· · ·
p
α
h
h
1
−
1
p
h
=
p
α
1
−
1
1
· · ·
p
α
h
−
1
h
(
p
1
−
1
)
· · ·
(
p
h
−
1
).
If at least two of the primes
p
1
, . . . ,
p
h
are odd, then 4
|
ϕ(
n
)
and
ϕ(
n
)
=
k
.
4
Andrzej Schinzel (1935– ), Polish mathematician with important work on exponential congru-
ences, Euler’s
ϕ
-function, Diophantine equations, and applications of transcendental number theory
to arithmetic problems.
6.4. Euler’s Totient Function
121
If
p
i
=
7, for some
i
, then 3
|
φ(
n
)
and
φ(
n
)
=
k
. If any odd prime
p
i
=
7 has
α
i
>
1, then
p
i
|
φ(
n
)
and again
φ(
n
)
=
k
. Thus the only remaining possibilities
are
n
=
2
α
or 2
α
p
for some
p
≥
3. In the first case
φ(
n
)
=
2
α
−
1
=
k
. In
the second case, if
α >
1, then again 4
|
φ(
n
)
and
φ(
n
)
=
k
. If
α
≤
1, then
φ(
n
)
=
p
−
1. For this to be
k
we need
p
−
1
=
2
·
7
m
or
p
=
2
·
7
m
+
1. However,
one easily checks that 3
|
2
·
7
m
+
1, so this forces
p
=
3 and
m
=
0, contrary to
our assumption.
Problem 6.4.2.
Prove that there are infinitely many positive integers n such that
ϕ(
n
)
=
n
3
.
Solution.
Let
n
=
2
·
3
m
, where
m
is a positive integer. Then
ϕ(
n
)
=
ϕ(
2
·
3
m
)
=
ϕ(
2
)ϕ(
3
m
)
=
3
m
−
3
m
−
1
=
2
·
3
m
−
1
=
n
3
for infinitely many values of
n
, as desired.
Problem 6.4.3.
If n is a composite positive integer, then
ϕ(
n
)
≤
n
−
√
n
.
Solution.
because
n
is composite, it has a prime factor
p
j
≤
√
n
. We have
ϕ(
n
)
=
n
1
−
1
p
1
· · ·
1
−
1
p
k
≤
n
1
−
1
p
j
≤
n
1
−
1
√
n
=
n
−
√
n
.
Problem 6.4.4.
For any positive integer n, n
=
2
, n
=
6
,
ϕ(
n
)
≥
√
n
.
Solution.
If
n
=
2
m
, where
m
≥
2, then
ϕ(
n
)
=
2
m
−
2
m
−
1
=
2
m
−
1
≥
√
2
m
=
√
n
.
If
n
=
p
m
, where
p
is an odd prime and
m
≥
2, then
ϕ(
n
)
=
p
m
−
p
m
−
1
=
p
m
−
1
(
p
−
1
)
≥
2
p
m
=
√
2
n
.
If
n
=
p
m
, where
p
is a prime greater than or equal to 5, then
ϕ(
n
)
≥
√
2
n
.
If
n
is odd or 4
|
n
, then
ϕ(
n
)
=
ϕ(
p
α
1
1
)
· · ·
ϕ(
p
α
k
k
)
≥
6
p
α
1
1
· · ·
6
p
α
k
k
=
√
n
.
If
n
=
2
t
, where
t
is odd, then since
n
=
6, we see that
t
has at least one
prime power factor that is at least 5. Hence
ϕ(
n
)
=
ϕ(
t
)
≥
√
2
t
.
122
I Fundamentals, 6. Arithmetic Functions
Additional Problems
Problem 6.4.5.
For a positive integer
n
, let
ψ(
n
)
be the number of prime factors
of
n
. Show that if
ϕ(
n
)
divides
n
−
1 and
ψ(
n
)
≤
3, then
n
is prime.
(1998 Korean Mathematical Olympiad)
Problem 6.4.6.
Show that the equation
ϕ(
n
)
=
τ(
n
)
has only the solutions
n
=
1
,
3
,
8
,
10
,
18
,
24
,
30.
Problem 6.4.7.
Let
n
>
6 be an integer and let
a
1
,
a
2
, . . . ,
a
k
be all positive
integers less than
n
and relatively prime to
n
. If
a
2
−
a
1
=
a
3
−
a
2
= · · · =
a
k
−
a
k
−
1
>
0
,
prove that
n
must be either a prime number or a power of 2.
(32nd International Mathematical Olympiad)
6.5
Exponent of a Prime and Legendre’s Formula
Let
p
be a prime and let us denote by
v
p
(
a
)
the exponent of
p
in the decomposi-
tion of
a
. Of course, if
p
doesn’t divide
a
, then
v
p
(
a
)
=
0.
It is easy to prove the following properties of
v
p
:
(1) min
{
v
p
(
a
), v
p
(
b
)
} ≤
v
p
(
a
+
b
)
. If
v
p
(
a
)
=
v
p
(
b
)
, then
v
p
(
a
+
b
)
=
min
{
v
p
(
a
), v
p
(
b
)
}
.
(2)
v
p
(
ab
)
=
v
p
(
a
)
+
v
p
(
b
)
.
(3)
v
p
(
gcd
(
a
1
,
a
2
, . . . ,
a
n
))
=
min
{
v
p
(
a
1
), v
p
(
a
2
), . . . , v
p
(
a
n
)
}
.
(4)
v
p
(
lcm
(
a
1
,
a
2
, . . . ,
a
n
))
=
max
{
v
p
(
a
1
), v
p
(
a
2
), . . . , v
p
(
a
n
)
}
.
If we have to prove that
a
|
b
, then it is enough to prove that the exponent
of any prime number in the decomposition of
a
is at least the exponent of that
prime in the decomposition of
b
. Now let us repeat the above idea in terms of the
function
v
p
. We have
a
|
b
if and only if for every prime
p
we have
v
p
(
a
)
≤
v
p
(
b
)
. Also, we have
a
=
b
if and only if for every prime
p
,
v
p
(
a
)
=
v
p
(
b
)
.
For each positive integer
n
, let
e
p
(
n
)
be the exponent of the prime
p
in the
prime factorization of
n
!
.
The arithmetic function
e
p
is called the
Legendre
5
function
associated with
the prime
p
, and it is connected to the function
v
p
by the relation
e
p
(
n
)
=
v
p
(
n
!
)
.
The following result gives a formula for the computation of
e
p
(
n
)
.
5
Adrien-Marie Legendre (1752–1833), French mathematician who was a disciple of Euler and
Lagrange. In number theory, he studied the function
e
p
, and he proved the unsolvability of Fermat’s
last theorem for
n
=
5.
Do'stlaringiz bilan baham: |
