|
Second solution.
We use the second version of Legendre’s formula. It is just
e
2
(
n
)
=
n
−
S
2
(
n
)
=
n
−
1 if and only if
S
2
(
n
)
=
1, that is, if and only if
n
is a
power of 2.
Problem 6.5.5.
Let p be an odd prime. Prove that the exponent of p in the prime
factorization of
1
·
3
·
5
· · ·
(
2
m
+
1
)
is
k
≥
1
%
2
m
+
1
p
k
&
−
%
m
p
k
&
.
Solution.
We have
1
·
3
·
5
· · ·
(
2
m
+
1
)
=
(
2
m
+
1
)
!
m
! ·
2
m
.
Because
p
is odd, the desired exponent is
e
p
(
2
m
+
1
)
−
e
p
(
m
)
=
k
≥
1
%
2
m
+
1
p
k
&
−
k
≥
1
%
m
p
k
&
,
and the conclusion follows.
6.5. Exponent of a Prime and Legendre’s Formula
127
Problem 6.5.6.
If p is a prime and p
α
|
n
m
, then p
α
≤
n.
Solution.
Because
n
m
=
n
!
m
!
(
n
−
m
)
!
,
the exponent of
p
in the prime factorization of
n
m
is
β
=
e
p
(
n
)
−
e
p
(
m
)
−
e
p
(
n
−
m
)
=
k
≥
1
%
n
p
k
&
−
%
m
p
k
&
−
%
n
−
m
p
k
&
.
This sum has at most
s
nonzero terms, where
p
s
≤
n
<
p
s
+
1
. Using the
inequality
x
+
y
−
x
−
y
≤
1 for
x
=
m
p
k
and
y
=
n
−
m
p
k
, it follows that
β
≤
s
. Because
p
α
|
n
m
, we obtain
α
≤
β
≤
s
; hence
p
α
≤
p
s
≤
n
.
Additional Problems
Problem 6.5.7.
(a) If
p
is a prime, prove that for any positive integer
n
,
−
#
ln
n
ln
p
$
+
n
ln
n
ln
p
k
=
1
1
p
k
<
e
p
(
n
) <
n
p
−
1
.
(b) Prove that
lim
n
→∞
e
p
(
n
)
n
=
1
p
−
1
.
Problem 6.5.8.
Show that for all nonnegative integers
m
,
n
, the number
(
2
m
)
!
(
2
n
)
!
m
!
n
!
(
m
+
n
)
!
is also an integer.
(14th International Mathematical Olympiad)
Problem 6.5.9.
Prove that
(
3
a
+
3
b
)
!
(
2
a
)
!
(
3
b
)
!
(
2
b
)
!
(
2
a
+
3
b
)
!
(
a
+
2
b
)
!
(
a
+
b
)
!
a
!
(
b
!
)
2
is an integer for any positive
integers
a
,
b
.
(American Mathematical Monthly)
Problem 6.5.10.
Prove that there exists a constant
c
such that for any positive
integers
a
,
b
,
n
for which
a
! ·
b
! |
n
!
, we have
a
+
b
<
n
+
c
ln
n
.
(Paul Erd˝os)
128
I Fundamentals, 6. Arithmetic Functions
Problem 6.5.11.
Prove that for any integer
k
≥
2, the equation
1
10
n
=
1
n
1
!
+
1
n
2
!
+ · · · +
1
n
k
!
does not have integer solutions such that 1
≤
n
1
<
n
2
<
· · ·
<
n
k
.
(Tuymaada Olympiad)
7
More on Divisibility
7.1
Congruences Modulo a Prime:
Fermat’s Little Theorem
In this section,
p
will denote a prime number. We begin by noticing that it makes
sense to consider a polynomial with integer coefficients
f
(
x
)
=
a
0
+
a
1
x
+ · · · +
a
d
x
d
,
but reduced modulo
p
. If for each
j
,
a
j
≡
b
j
(
mod
p
)
, we write
a
0
+
a
1
x
+ · · · +
a
d
x
d
≡
b
0
+
b
1
x
+ · · · +
b
d
x
d
(
mod
p
),
and talk about the residue class of a polynomial modulo
p
. We will denote the
residue class of
f
(
x
)
by
f
(
x
)
p
. We say that
f
(
x
)
has
degree d modulo p
if
a
d
≡
0
(
mod
p
)
.
For an integer
c
, we can evaluate
f
(
c
)
and reduce the answer modulo
p
to
obtain
f
(
c
)
p
. If
f
(
c
)
p
=
0 modulo
p
, then
c
is said to be a
root of f
(
x
)
modulo p
.
Theorem 7.1.1.
(Lagrange)
If f
(
x
)
has degree d modulo p, then the number of
distinct roots of f
(
x
)
modulo p is at most p.
Proof.
Begin by noticing that if
c
is root of
f
(
x
)
modulo
p
, then
f
(
x
)
≡
f
(
x
)
−
f
(
c
) (
mod
p
).
Hence
f
(
x
)
≡ [
a
1
+
a
2
(
x
+
c
)
+ · · ·
+
a
d
(
x
d
−
1
+
x
d
−
2
c
+ · · · +
xc
d
−
2
+
c
d
−
1
)
]
(
x
−
c
) (
mod
p
),
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
129
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/b11856_7,
130
I Fundamentals, 7. More on Divisibility
and we get
f
(
x
)
≡
f
1
(
x
)(
x
−
c
)
, where
f
1
(
x
)
is a polynomial of degree
d
−
1
modulo
p
with integer coefficients. If
c
is another root of
f
(
x
)
modulo
p
such
that
c
≡
c
(
mod
p
)
, then since
f
1
(
c
)(
c
−
c
)
≡
0
(
mod
p
)
, we have
p
|
f
1
(
c
)(
c
−
c
)
. Hence, by Euclid’s lemma (Proposition 1.3.2),
p
|
f
1
(
c
)
. Thus
c
is a root of
f
1
(
x
)
modulo
p
.
If now the integers
c
1
,
c
2
, . . . ,
c
k
are the distinct roots of
f
(
x
)
modulo
p
, then
f
(
x
)
≡
(
x
−
c
1
)(
x
−
c
2
)
· · ·
(
x
−
c
k
)
g
(
x
) (
mod
p
).
In fact, the degree modulo
p
of
g
(
x
)
is
d
−
k
. This implies 0
≤
k
≤
d
.
Theorem 7.1.2.
(Fermat’s little theorem)
Let a be a positive integer and let p be
a prime. Then
a
p
≡
a
(
mod
p
).
Proof.
We induct on
a
. For
a
=
1 everything is clear. Assume that
p
|
a
p
−
a
.
Then
(
a
+
1
)
p
−
(
a
+
1
)
=
(
a
p
−
a
)
+
p
−
1
k
=
1
p
k
a
k
.
Using the fact that
p
|
p
k
for 1
≤
k
≤
p
−
1 and the inductive hypothesis, it
follows that
p
|
(
a
+
1
)
p
−
(
a
+
1
)
, that is,
(
a
+
1
)
p
≡
(
a
+
1
) (
mod
p
)
.
Alternative proof.
Suppose that gcd
(
a
,
p
)
=
1 and let us show that
a
p
−
1
≡
1
(
mod
p
)
. Consider the integers
a
,
2
a
, . . . , (
p
−
1
)
a
, whose remainders when
divided by
p
are distinct (otherwise, if
i a
≡
j a
(
mod
p
)
, then
p
|
(
i
−
j
)
a
, that
is,
p
|
i
−
j
, which holds only if
i
=
j
). Hence the remainders are 1
,
2
, . . . ,
p
−
1
in some order and
a
·
(
2
a
)
· · ·
(
p
−
1
)
a
≡
1
·
2
· · ·
(
p
−
1
) (
mod
p
),
i.e.,
a
p
−
1
(
p
−
1
)
! ≡
(
p
−
1
)
!
(
mod
p
).
Because
p
and
(
p
−
1
)
!
are relatively prime, the conclusion follows.
Remark.
The converse is not true. For example, 3
·
11
·
17 divides
a
3
·
11
·
17
−
a
,
since 3, 11, 17 each divide
a
3
·
11
·
17
−
a
(for instance, if 11 did not divide
a
, then
from Fermat’s little theorem, we would have 11
|
a
10
−
1; hence 11
|
a
10
·
56
−
1,
i.e., 11
|
a
561
−
a
and 561
=
3
·
11
·
17).
The composite integers
n
satisfying
a
n
≡
a
(
mod
n
)
for any integer
a
are
called
Carmichael numbers
. There exist such integers, for example
n
=
2
·
73
·
1103. For other comments see the remark after Problem 7.3.11.
For problems involving
x
n
it might be good to work modulo a prime
p
with
p
≡
1
(
mod
n
)
.
Do'stlaringiz bilan baham: |
