|
II Solutions, 6. Arithmetic Functions
Solution.
It is given that the reduced system of residues mod
n
chosen from the
set
{
1
,
2
, . . . ,
n
−
1
}
is an arithmetic progression. We write it as an increasing
sequence 1
=
a
1
<
a
2
<
· · ·
<
a
k
=
n
−
1.
Suppose the reduced system of residues for
n
is an arithmetic progression
with difference 1. Since 1 and
n
−
1 are relatively prime to
n
, this system must be
1
<
2
<
· · ·
<
n
−
1. Hence
n
has no factors in
{
2
, . . . ,
n
−
1
}
and
n
is prime. If
the reduced system of residues for
n
is an arithmetic progression with difference
2, then it must be 1
<
3
<
· · ·
<
n
−
1. Hence
n
has no odd factors and
n
is a
power of 2. The problem asks us to prove that only these cases can appear.
Let
a
2
be the second member of the progression. Because
a
2
>
1 is the least
positive number relatively prime to
n
, it is a prime number, say
p
and
p
>
3.
Then, the difference of the progression is
a
2
−
a
1
=
p
−
1, and
a
k
=
n
−
1
=
1
+
(
k
−
1
)(
p
−
1
)
. We obtain a “key” formula:
n
−
2
=
(
k
−
1
)(
p
−
1
).
Remembering the choice of
p
,
n
is divisible by 3, and then
n
−
2
≡
1
(
mod 3
)
.
Thus, by the key formula we cannot have
p
≡
1
(
mod 3
)
. Since
p
>
3, we have
p
≡
2
(
mod 3
)
. Then
a
3
=
1
+
2
(
p
−
1
)
≡
0
(
mod 3
)
, and this contradicts the
supposition that
a
3
and
n
are relatively prime numbers.
6.5
Exponent of a Prime and Legendre’s Formula
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
.
Solution.
(a) From Legendre’s formula,
e
p
(
n
)
=
k
≥
1
%
n
p
k
&
≤
k
≥
1
n
p
k
<
n
∞
j
=
1
1
p
j
=
n
p
−
1
.
For the left bound note that
ln
n
ln
p
is the least nonnegative integer
s
such that
n
<
p
s
+
1
. That is,
n
p
k
=
0 for
k
≥
s
+
1. It follows that
e
p
(
n
)
=
s
k
=
1
%
n
p
k
&
>
s
k
=
1
n
p
k
−
1
=
n
s
k
=
1
1
p
k
−
s
,
and we are done.
6.5. Exponent of a Prime and Legendre’s Formula
295
(b) From the inequalities
−
1
n
%
ln
n
ln
p
&
+
#
ln
n
ln
p
$
k
=
1
1
p
k
<
e
p
(
n
)
n
<
1
p
−
1
and the fact that
lim
n
→∞
1
n
%
ln
n
ln
p
&
=
0
and
lim
n
→∞
#
ln
n
ln
p
$
k
=
1
1
p
k
=
1
p
−
1
,
the desired formula follows.
Remark.
An easier to understand lower bound on
e
p
(
n
)
is
e
p
(
n
) >
n
p
−
1
−
?
log
n
log
p
@
,
which follows easily from the fact that
n
has at most
9
log
n
log
p
:
digits in base
p
. This
lower bound suffices to prove (b).
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)
Solution.
It is sufficient to prove that for any prime number
p
,
e
p
(
2
m
)
+
e
p
(
2
n
)
≥
e
p
(
m
)
+
e
p
(
n
)
+
e
p
(
m
+
n
).
Again, it is sufficient to prove that for all
i
,
j
≥
1, the following inequality
holds:
%
2
m
p
i
&
+
%
2
n
p
i
&
≥
%
m
p
i
&
+
%
n
p
i
&
+
%
m
+
n
p
i
&
.
This follows from a more general result.
Lemma.
For any real numbers a
,
b,
2
a
+
2
b
≥
a
+
b
+
a
+
b
.
Proof.
Let
a
=
a
+
x
,
b
=
b
+
y
, where 0
≤
x
,
y
<
1. If
x
+
y
<
1 we have
a
+
b
=
a
+
b
, and the required inequality becomes
2
a
+
2
b
≥
2
(
a
+
b
).
In this form, it is obvious.
296
II Solutions, 6. Arithmetic Functions
Let 1
≤
x
+
y
<
2. Then 2
x
≥
1 or 2
y
≥
1. Let 2
x
≥
1. Then
2
a
=
2
a
+
1
and
a
+
b
=
a
+
b
+
1
.
Thus
2
a
+
2
b
=
2
a
+
1
+
2
b
≥
2
a
+
1
+
2
b
=
a
+
b
+
a
+
b
.
The other cases follow in a similar way.
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 all pairs of
positive integers a
,
b.
(American Mathematical Monthly)
Solution.
First, let us clarify something. When we write
%
n
p
&
+
%
n
p
2
&
+
%
n
p
3
&
+ · · ·
,
we write in fact
"
k
≥
1
n
p
k
, and this sum has clearly a finite number of nonzero
terms. Now let us take a prime
p
and apply Legendre’s formula as well as the first
observations. We find that
v
p
((
3
a
+
3
b
)
!
(
2
a
)
!
(
3
b
)
!
(
2
b
)
!
)
=
k
≥
1
%
3
a
+
3
b
p
k
&
+
%
2
a
p
k
&
+
%
3
b
p
k
&
+
%
2
b
p
k
&
and also
v
p
(
2
a
+
3
b
)
!
(
a
+
2
b
)
!
(
a
+
b
)
!
a
!
(
b
!
)
2
=
k
≥
1
%
2
a
+
3
b
p
k
&
+
%
a
+
2
b
p
k
&
+
%
a
+
b
p
k
&
+
%
a
p
k
&
+
2
%
b
p
k
&
.
Of course, it is enough to prove that for each
k
≥
1, the term corresponding
to
k
in the first sum is greater than or equal to the term corresponding to
k
in the
second sum. With the substitution
x
=
a
p
k
,
y
=
b
p
k
, we have to prove that for any
nonnegative real numbers
x
,
y
we have
3
x
+
3
y
+
2
x
+
3
y
+
2
y
≥
2
x
+
3
y
+
x
+
2
y
+
x
+
y
+
x
+
2
y
.
This isn’t easy, but with another useful idea the inequality will become easy.
The idea is that
3
x
+
3
y
=
3
x
+
3
y
+
3
{
x
} +
3
{
y
}
,
and similar relations for the other terms of the inequality. After this operation, we
see that it suffices to prove the inequality only for 0
≤
x
,
y
<
1. Because we
can easily compute all terms, after splitting in some cases, it suffices to see when
2
{
x
}
,
3
{
y
}
,
2
{
y
}
are 0, 1, or 2.
Do'stlaringiz bilan baham: |
