|
6.5. Exponent of a Prime and Legendre’s Formula
297
Remark.
A graphical solution to this problem is the following. The problem re-
duces (as in the text) to showing that
3
x
+
3
y
+
2
x
+
3
y
+
2
y
≥
2
x
+
3
y
+
x
+
2
y
+
x
+
y
+
x
+
2
y
.
Now observe that it suffices to show this for 0
≤
x
<
1 and 0
≤
y
<
1.
For this draw two copies of the unit square. On the first plot the regions on which
the left-hand side is constant and the corresponding value, and for the second do
the same thing for the right-hand side. Then one just compares and sees that the
left-hand side is always greater.
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)
Solution.
This time, the second formula for
e
p
(
n
)
is useful. Of course, there is no
reasonable estimation of this constant, so we should see what happens if
a
! ·
b
! |
n
!
. Then
e
2
(
a
)
+
e
2
(
b
)
≤
e
2
(
n
)
, which can be translated as
a
−
S
2
(
a
)
+
b
−
S
2
(
b
)
≤
n
−
S
2
(
n
) <
n
. So, we have found almost exactly what we needed:
a
+
b
<
n
+
S
2
(
a
)
+
S
2
(
b
)
. Now we need another observation: the sum of digits
of a number
A
when written in binary is at most the number of digits of
A
in
base 2, which is 1
+
log
2
A
(this follows from the fact that 2
k
−
1
≤
A
<
2
k
,
where
k
is the number of digits of
A
in base 2). So, we have the estimations
a
+
b
<
n
+
S
2
(
a
)
+
S
2
(
b
)
≤
n
+
2
+
log
2
ab
≤
n
+
2
+
2 log
2
n
(since we have
of course
a
,
b
≤
n
). And now the conclusion is immediate.
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)
Solution.
Suppose we have found a solution of the equation and let us consider
P
=
n
1
!
n
2
! · · ·
n
k
!
.
We have
10
n
(
n
1
+
1
)
· · ·
(
n
k
−
1
)
n
k
+ · · · +
(
n
k
−
1
+
1
)
· · ·
(
n
k
−
1
)
n
k
+
1
=
n
k
!
,
which shows that
n
k
divides 10
n
. Let us write
n
k
=
2
x
·
5
y
. First of all, suppose
that
x
,
y
are positive. Thus,
(
n
1
+
1
)
· · ·
(
n
k
−
1
)
n
k
+ · · · +
(
n
k
−
1
+
1
)
· · ·
(
n
k
−
1
)
n
k
+
1
298
II Solutions, 6. Arithmetic Functions
is relatively prime to 10, and it follows that
e
2
(
n
k
)
=
e
5
(
n
k
)
. This implies of
course that
n
k
2
j
=
n
k
5
j
for all
j
(because we clearly have
n
k
2
j
>
n
k
5
j
). Take
j
=
1, then from
n
k
2
≥
#
n
k
2
$
≥
#
n
k
5
$
≥
n
k
5
−
1
we get
n
k
≤
3. Checking by hand shows that the inequality does not hold for
n
k
=
2 or
n
k
=
3, so we get only
k
=
1, which is not possible, since
k
≥
2.
Next, suppose that
y
=
0. Then
(
n
1
+
1
)
· · ·
(
n
k
−
1
)
n
k
+ · · · +
(
n
k
−
1
+
1
)
· · ·
(
n
k
−
1
)
n
k
+
1
is odd and thus
e
2
(
n
k
)
=
n
≤
e
5
(
n
k
)
. Again this implies
e
2
(
n
k
)
=
e
5
(
n
k
)
, and we
have seen that this gives no solution. So, actually
x
=
0. A crucial observation is
that if
n
k
>
n
k
−
1
+
1, then
(
n
1
+
1
)
· · ·
(
n
k
−
1
)
n
k
+ · · · +
(
n
k
−
1
+
1
)
· · ·
(
n
k
−
1
)
n
k
+
1
is again odd, and thus we find again that
e
2
(
n
k
)
=
n
≤
e
5
(
n
k
)
, impossible. So,
n
k
=
n
k
−
1
+
1. But then, taking into account that
n
k
is a power of 5, we deduce
that
(
n
1
+
1
)
· · ·
(
n
k
−
1
)
n
k
+ · · · +
(
n
k
−
1
+
1
)
· · ·
(
n
k
−
1
)
n
k
+
1
is congruent to 2 modulo 4 and thus
e
2
(
n
k
)
=
n
+
1
≤
e
5
(
n
k
)
+
1. It follows that
n
k
2
≤
1
+
n
k
5
and thus
n
k
≤
6. Since
n
k
is a power of 5, we find that
n
k
=
5,
n
k
−
1
=
1, and a quick search of all possibilities shows that there are no solutions.
7
More on Divisibility
7.1
Congruences Modulo a Prime:
Fermat’s Little Theorem
Problem 7.1.11.
Let
3
n
−
2
n
be a power of a prime for some positive integer n.
Prove that n is a prime.
Solution.
Let 3
n
−
2
n
=
p
α
for some prime
p
and some
α
≥
1, and let
q
be
a prime divisor of
n
. Assume that
q
=
n
; then
n
=
kq
, where
k
>
1. Since
p
α
=
3
kq
−
2
kq
=
(
3
k
)
q
−
(
2
k
)
q
, we observe that
p
α
is divisible by 3
k
−
2
k
.
Hence 3
k
−
2
k
=
p
β
for some
β
≥
1. Now we have
p
α
=
(
2
k
+
p
β
)
q
−
2
kq
=
q
2
k
(
q
−
1
)
p
β
+
q
(
q
−
1
)
2
2
k
(
q
−
2
)
p
2
β
+ · · · +
p
q
β
.
Since
α > β
(because
p
β
=
3
k
−
2
k
is less than
p
α
=
3
kq
−
2
kq
), it follows that
p
α
is divisible by a power of
p
at least as great as
p
β
+
1
. Then the above equality
implies that
p
divides
q
2
k
(
q
−
1
)
. On the other hand,
p
is obviously odd, and hence
it divides
q
. Being a prime,
q
must then be equal to
p
. Therefore
n
=
kq
=
kp
,
and
p
α
=
(
3
p
)
k
−
(
2
p
)
k
is divisible by 3
p
−
2
p
, implying 3
p
−
2
p
=
p
γ
for
some
γ
≥
1. In particular, we infer that 3
p
≡
2
p
(
mod
p
)
. Now, observing that
p
=
2
,
3, we reach a contradiction to Fermat’s little theorem, by which
3
p
≡
3
(
mod
p
),
2
p
≡
2
(
mod
p
).
Problem 7.1.12.
Let f
(
x
1
, . . . ,
x
n
)
be a polynomial with integer coefficients of
total degree less than n. Show that the number of ordered n-tuples
(
x
1
, . . . ,
x
n
)
with
0
≤
x
i
≤
12
such that f
(
x
1
, . . . ,
x
n
)
≡
0
(
mod 13
)
is divisible by
13
.
(1998 Turkish Mathematical Olympiad)
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica,
Number Theory
,
DOI: 10.1007/b11856_18,
299
300
Do'stlaringiz bilan baham: |
