|
1.2. Prime Numbers
13
Solution.
We have
n
5
+
n
4
+
1
=
n
5
+
n
4
+
n
3
−
n
3
−
n
2
−
n
+
n
2
+
n
+
1
=
n
3
(
n
2
+
n
+
1
)
−
n
(
n
2
+
n
+
1
)
+
(
n
2
+
n
+
1
)
=
(
n
2
+
n
+
1
)(
n
3
−
n
+
1
),
the product of two integers greater than 1. Hence
n
5
+
n
4
+
1 is not a prime.
Problem 1.2.2.
Find the positive integers n with exactly
12
divisors
1
=
d
1
<
d
2
<
· · ·
<
d
12
=
n such that the divisor with index d
4
−
1
(that is, d
d
4
−
1
) is
(
d
1
+
d
2
+
d
4
)
d
8
.
(1989 Russian Mathematical Olympiad)
Solution.
Of course, there is 1
≤
i
≤
12 such that
d
i
=
d
1
+
d
2
+
d
4
. Since
d
i
>
d
4
, we have
i
≥
5. Also, observe that
d
j
d
13
−
j
=
n
for all
j
and since
d
i
d
8
=
d
d
4
−
1
≤
n
, we must have
i
≤
5, thus
i
=
5 and
d
1
+
d
2
+
d
4
=
d
5
.
Also,
d
d
4
−
1
=
d
5
d
8
=
n
=
d
12
, thus
d
4
=
13 and
d
5
=
14
+
d
2
. Of course,
d
2
is the smallest prime divisor of
n
, and since
d
4
=
13, we can only have
d
2
∈
{
2
,
3
,
5
,
7
,
11
}
. Also, since
n
has 12 divisors, it has at most 3 prime divisors. If
d
2
=
2 then
d
5
=
16 and then 4 and 8 are divisors of
n
smaller than
d
4
=
13,
impossible. A similar argument shows that
d
2
=
3 and
d
5
=
17. Since
n
has 12
divisors and is a multiple of 3
·
13
·
17, the only possibilities are 9
·
13
·
17, 3
·
169
·
7
and 3
·
13
·
289. One can easily check that only 9
·
13
·
17
=
1989 is a solution.
Problem 1.2.3.
Find all positive integers a
,
b for which a
4
+
4
b
4
is a prime.
Solution.
Observe that
a
4
+
4
b
4
=
a
4
+
4
b
4
+
4
a
2
b
2
−
4
a
2
b
2
=
(
a
2
+
2
b
2
)
2
−
4
a
2
b
2
=
(
a
2
+
2
b
2
+
2
ab
)(
a
2
+
2
b
2
−
2
ab
)
= [
(
a
+
b
)
2
+
b
2
][
(
a
−
b
)
2
+
b
2
]
.
Since
(
a
+
b
)
2
+
b
2
>
1, then
a
4
+
4
b
4
can be a prime number only if
(
a
−
b
)
2
+
b
2
=
1. This implies
a
=
b
=
1, which is the only solution of the
problem.
Problem 1.2.4.
Let p
,
q be distinct primes. Prove that there are positive integers
a
,
b such that the arithmetic mean of all the divisors of the number n
=
p
a
·
q
b
is
also an integer.
(2002 Romanian Mathematical Olympiad)
Solution.
The sum of all divisors of
n
is given by the formula
(
1
+
p
+
p
2
+ · · · +
p
a
)(
1
+
q
+
q
2
+ · · · +
q
b
),
14
I Fundamentals, 1. Divisibility
as can easily be seen by expanding the parentheses. The number
n
has
(
a
+
1
)
×
(
b
+
1
)
positive divisors and their arithmetic mean is
M
=
(
1
+
p
+
p
2
+ · · · +
p
a
)(
1
+
q
+
q
2
+ · · · +
q
b
)
(
a
+
1
)(
b
+
1
)
.
If
p
and
q
are both odd numbers, we can take
a
=
p
and
b
=
q
, and it is easy
to see that
M
is an integer.
If
p
=
2 and
q
odd, choose again
b
=
q
and consider
a
+
1
=
1
+
q
+
q
2
+
· · · +
q
q
−
1
. Then
M
=
1
+
2
+
2
2
+ · · · +
2
a
, and it is an integer.
For
p
odd and
q
=
2, set
a
=
p
and
b
=
p
+
p
2
+
p
3
+ · · · +
p
p
−
1
. The
solution is complete.
Problem 1.2.5.
Find all primes p such that p
2
+
11
has exactly six different
divisors (including
1
and the number itself).
(1995 Russian Mathematical Olympiad)
Solution.
For
p
=
3, 3
|
p
2
−
1, and so 3
|
(
p
2
+
11
)
. Similarly, for
p
=
2,
4
|
p
2
−
1, and so 4
|
(
p
2
+
11
)
. Except in these two cases, then, 12
|
(
p
2
+
11
)
;
since 12 itself has six divisors (1, 2, 3, 4, 6, 12) and
p
2
+
11
>
12 for
p
>
1,
p
2
+
11 must have more than six divisors. The only cases to check are
p
=
2 and
p
=
3. If
p
=
2, then
p
2
+
11
=
15, which has only four divisors (1, 3, 5, 15),
while if
p
=
3, then
p
2
+
11
=
20, which indeed has six divisors (1, 2, 4, 5, 10,
20). Hence
p
=
3 is the only solution.
Problem 1.2.6.
Let a
,
b
,
c be nonzero integers, a
=
c, such that
a
c
=
a
2
+
b
2
c
2
+
b
2
.
Prove that a
2
+
b
2
+
c
2
cannot be a prime.
(1999 Romanian Mathematical Olympiad)
First solution.
The equality
a
c
=
a
2
+
b
2
c
2
+
b
2
is equivalent to
(
a
−
c
)(
b
2
−
ac
)
=
0.
Since
a
=
c
, it follows that
b
2
=
ac
and therefore:
a
2
+
b
2
+
c
2
=
a
2
+
ac
+
c
2
=
a
2
+
2
ac
+
c
2
−
b
2
=
(
a
+
c
)
2
−
b
2
=
(
a
+
c
−
b
)(
a
+
c
+
b
).
Now, clearly,
a
2
+
b
2
+
c
2
>
3, so, if
a
2
+
b
2
+
c
2
is a prime number, then
only four cases are possible:
(1)
a
+
c
−
b
=
1 and
a
+
c
−
b
=
a
2
+
b
2
+
c
2
;
(2)
a
+
c
+
b
=
1 and
a
+
c
+
b
=
a
2
+
b
2
+
c
2
;
1.2. Prime Numbers
15
(3)
a
+
c
−
b
= −
1 and
a
+
c
+
b
= −
(
a
2
+
b
2
+
c
2
)
;
(4)
a
+
c
+
b
= −
1 and
a
+
c
−
b
= −
(
a
2
+
b
2
+
c
2
)
.
In the first two cases we are led to
a
2
+
b
2
+
c
2
−
2
(
a
+
c
)
+
1
=
0, or
(
a
−
1
)
2
+
(
c
−
1
)
2
+
b
2
=
1; hence
a
=
c
=
1.
In other cases we obtain
(
a
+
1
)
2
+
(
c
+
1
)
2
+
b
2
=
1; hence
a
=
c
= −
1.
But
a
=
c
is a contradiction.
Second solution.
As in the previous solution we get
b
2
=
ac
, then observe that
this forces
a
and
c
to have the same sign. Hence replacing them with their neg-
atives if necessary we may assume
a
,
c
>
0. Similarly, we may assume
b
>
0.
Then continue with the given solution to get
a
2
+
b
2
+
c
2
=
(
a
+
c
−
b
)(
a
+
b
+
c
)
.
If this is a prime then the smaller factor
a
+
c
−
b
must be 1. But since
a
=
c
,
a
+
c
>
2
√
ac
=
2
b
so
a
+
c
−
b
>
b
≥
1, a contradiction.
Problem 1.2.7.
Show that each natural number can be written as the difference
of two natural numbers having the same number of prime factors.
(1999 Russian Mathematical Olympiad)
Solution.
If
n
is even, then we can write it as
(
2
n
)
−
(
n
)
. If
n
is odd, let
d
be the
smallest odd prime that does not divide
n
. Then write
n
=
(
dn
)
−
((
d
−
1
)
n
)
. The
number
dn
contains exactly one more prime factor than
n
. As for
(
d
−
1
)
n
, it is
divisible by 2 because
d
−
1 is even. Its odd factors are less than
d
, so they all
divide
n
. Therefore
(
d
−
1
)
n
also contains exactly one more prime factor than
n
,
and
dn
and
(
d
−
1
)
n
have the same number of prime factors.
Problem 1.2.8.
Let p be a prime number. Find all k
∈
Z
, k
=
0
, such that
k
2
−
pk is a positive integer.
(1997 Spanish Mathematical Olympiad)
Solution.
We will use the following simple but important property: If
ab
is a
square and
a
and
b
are coprime, then
a
and
b
are both squares.
The values are
k
=
(
p
+
1
)
2
/
4 for
p
odd (and none for
p
=
2).
We first rule out the case that
k
is divisible by
p
: if
k
=
np
, then
k
2
−
pk
=
p
2
n
(
n
−
1
)
. Since
n
and
n
−
1 are consecutive, they are coprime, and by the lemma
above they are both squares. However, the only consecutive squares are 0 and 1,
so this gives
k
=
p
and
k
2
−
pk
=
0, which is not positive.
We thus assume that
k
and
p
are coprime, in which case
k
and
k
−
p
are
coprime. Thus
k
2
−
pk
=
k
(
k
−
p
)
is a square if and only if
k
and
k
−
p
are
squares, say
k
=
m
2
and
k
−
p
=
n
2
. Then
p
=
m
2
−
n
2
=
(
m
+
n
)(
m
−
n
)
,
which implies
m
+
n
=
p
,
m
−
n
=
1 and hence
k
=
(
p
+
1
)
2
/
4. Since
k
must
be an integer, this forces
p
to be odd.
Problem 1.2.9.
Let p
>
5
be a prime number and
X
= {
p
−
n
2
|
n
∈
N
,
n
2
<
p
}
.
16
Do'stlaringiz bilan baham: |
