|
6.5. Exponent of a Prime and Legendre’s Formula
123
Theorem 6.5.1.
(Legendre’s formula)
For any prime p and any positive integer n,
e
p
(
n
)
=
i
≥
1
%
n
p
i
&
=
n
−
S
p
(
n
)
p
−
1
,
where S
p
(
n
)
is the sum of the digits of n when written in base p.
Proof.
For
n
<
p
it is clear that
e
p
(
n
)
=
0. If
n
≥
p
, then in order to determine
e
p
(
n
)
we need to consider only the multiples of
p
in the product 1
·
2
· · ·
n
, that
is,
(
1
·
p
)(
2
·
p
)
· · ·
(
kp
)
=
p
k
k
!
, where
k
=
n
p
. Hence
e
p
(
n
)
=
%
n
p
&
+
e
p
%
n
p
&
.
Replacing
n
by
n
p
and taking into account that
%
n
p
p
&
=
%
n
p
2
&
,
we obtain
e
p
%
n
p
&
=
%
n
p
2
&
+
e
p
%
n
p
2
&
.
Continuing this procedure, we get
e
p
%
n
p
2
&
=
%
n
p
3
&
+
e
p
%
n
p
3
&
,
. . .
e
p
%
n
p
m
−
1
&
=
%
n
p
m
&
+
e
p
%
n
p
m
&
,
where
m
is the least positive integer such that
n
<
p
m
+
1
, that is,
m
=
ln
n
ln
p
.
Summing up the relations above yields
e
p
(
n
)
=
%
n
p
&
+
%
n
p
2
&
+ · · · +
%
n
p
m
&
.
The other relation is not difficult. Indeed, let us write
n
=
a
0
+
a
1
p
+ · · · +
a
k
p
k
,
where
a
0
,
a
1
, . . . ,
a
k
∈ {
0
,
1
, . . . ,
p
−
1
}
and
a
k
=
0. Then
%
n
p
&
+
%
n
p
2
&
+· · · =
a
1
+
a
2
p
+· · ·+
a
k
p
k
−
1
+
a
2
+
a
3
p
+· · ·+
a
k
p
k
−
2
+· · ·+
a
k
.
124
I Fundamentals, 6. Arithmetic Functions
The coefficient of
a
i
on the right-hand side is 1
+
p
+ · · · +
p
i
−
1
, so using the
formula
1
+
p
+ · · · +
p
i
−
1
=
p
i
−
1
p
−
1
,
we obtain exactly the second part in the expression of
e
p
(
n
)
.
Remark.
An alternative proof of the first half of Legendre’s formula is to note
that
e
p
(
n
)
=
n
k
=
1
v
p
(
k
)
=
n
k
=
1
v
p
(
k
)
m
=
1
1
.
Now look at the total contribution of a particular value of
m
to this double sum.
You will get a contribution of 1 for every multiple of
p
m
in the set
{
1
,
2
, . . . ,
n
}
.
The number of such multiples is
n
p
m
; hence
e
p
(
n
)
=
m
≥
1
%
n
p
m
&
.
Examples.
(1) Let us find the exponent of 7 in 400
!
. Applying Legendre’s for-
mula, we have
e
7
(
400
)
=
%
400
7
&
+
%
400
7
2
&
+
%
400
7
3
&
=
57
+
8
+
1
=
66
.
(2) Let us determine the exponent of 3 in
((
3
!
)
!
)
!
. We have
((
3
!
)
!
)
! =
(
6
!
)
! =
720
!
. Applying Legendre’s formula yields
e
3
(
720
)
=
%
720
3
&
+
%
720
3
2
&
+
%
720
3
3
&
+
%
720
3
4
&
+
%
720
3
5
&
=
240
+
80
+
26
+
8
+
2
=
356
.
Problem 6.5.1.
Let p be a prime. Find the exponent of p in the prime factorization
of
(
p
m
)
!
.
Solution.
Using the first half of Legendre’s formula, we have
e
p
(
p
m
)
=
i
≥
1
%
p
m
p
i
&
=
p
m
−
1
+
p
m
−
2
+ · · · +
p
+
1
=
p
m
−
1
p
−
1
.
An easier argument for the above formula follows directly from the second
version of Legendre’s formula. Then it is just
S
p
(
p
m
)
=
1, so
e
p
(
p
m
)
=
(
p
m
−
1
)/(
p
−
1
)
.
Problem 6.5.2.
Find all positive integers n such that n
!
ends in exactly
1000
zeros.
6.5. Exponent of a Prime and Legendre’s Formula
125
First solution.
There are clearly more 2’s than 5’s in the prime factorization of
n
!
; hence it suffices to solve the equation
#
n
5
$
+
#
n
5
2
$
+ · · · =
1000
.
But
#
n
5
$
+
#
n
5
2
$
+ · · ·
<
n
5
+
n
5
2
+ · · · =
n
5
1
+
1
5
+ · · ·
=
n
5
·
1
1
−
1
5
=
n
4
;
hence
n
>
4000.
On the other hand, using the inequality
a
>
a
−
1, we have
1000
>
n
5
−
1
+
n
5
2
−
1
+
n
5
3
−
1
+
n
5
4
−
1
+
n
5
5
−
1
=
n
5
1
+
1
5
+
1
5
2
+
1
5
3
+
1
5
4
−
5
=
n
5
·
1
−
1
5
5
1
−
1
5
−
5
,
so
n
<
1005
·
4
·
3125
3124
<
4022
.
We have narrowed
n
down to
{
4001
,
4002
, . . . ,
4021
}
. Using Legendre’s for-
mula we find that 4005 is the first positive integer with the desired property and
that 4009 is the last. Hence
n
=
4005, 4006, 4007, 4008, 4009.
Second solution.
It suffices to solve the equation
e
5
(
n
)
=
1000. Using the second
form of Legendre’s formula, this becomes
n
−
S
5
(
n
)
=
4000. Hence
n
>
4000.
We work our way upward from 4000 looking for a solution. Since
e
5
(
n
)
can
change only at multiples of 5, we step up 5 each time:
e
5
(
4000
)
=
4000
−
4
5
−
1
=
999
,
e
5
(
4005
)
=
4005
−
5
5
−
1
=
1000
,
e
5
(
4010
)
=
4010
−
6
5
−
1
=
1001
.
Any
n
>
4010 will clearly have
e
5
(
n
)
≥
e
5
(
4010
)
=
1001. Hence the only
solutions are
n
=
4005, 4006, 4007, 4008, 4009.
Problem 6.5.3.
Prove that for any positive integer n,
2
n
does not divide n
!
.
126
I Fundamentals, 6. Arithmetic Functions
First solution.
The exponent of 2 in the prime factorization of
n
!
is
k
=
e
2
(
n
)
=
#
n
2
$
+
#
n
2
2
$
+ · · ·
.
We have
k
<
n
2
+
n
2
2
+ · · · =
n
2
1
+
1
2
+ · · ·
=
n
2
·
1
1
−
1
2
=
n
,
and we are done.
Second solution.
Using the second version of Legendre’s formula, we have
e
2
(
n
)
=
n
−
S
2
(
n
) <
n
, and we are done.
Remark.
Similarly, for any prime
p
,
p
n
does not divide
((
p
−
1
)
n
)
!
.
Problem 6.5.4.
Find all positive integers n such that
2
n
−
1
divides n
!
.
First solution.
If
n
=
2
s
,
s
=
0
,
1
,
2
, . . .
, then
e
2
(
n
)
=
2
s
−
1
+ · · · +
2
+
1
=
2
s
−
1
;
hence 2
n
−
1
divides
n
!
.
Assume that
n
is odd,
n
=
2
n
1
+
1. Then from 2
n
−
1
=
2
2
n
1
|
(
2
n
1
+
1
)
! =
(
2
n
1
)
!
(
2
n
1
+
1
)
it follows that 2
2
n
1
|
(
2
n
1
)
!
, which is not possible, by Problem
6.5.3. We get
n
=
2
m
1
. If
m
1
is odd,
m
1
=
2
n
2
+
1, we have
2
n
−
1
=
2
4
n
2
+
1
|
(
4
n
2
+
2
)
! =
(
4
n
2
)
!
(
4
n
2
+
1
)
·
2
·
(
2
n
2
+
1
),
and we obtain 2
4
n
2
|
(
4
n
2
)
!
, a contradiction. Continuing this procedure, we get
n
=
2
s
.
Do'stlaringiz bilan baham: |
