Number Theory: Structures, Examples, and Problems

Proof of Theorem 10.2.1.
By property (7) (Part I, Section 10.1), the binomial
coefficients
p
k
, where 1
≤
k
≤
p
−
1, are divisible by
p
. Thus,
(
1
+
x
)
p
≡
1
+
x
p
(
mod
p
)
2
Franc¸ois Edouard Anatole Lucas (1842–1891), French mathematician best known for his results
in number theory. He studied the Fibonacci sequence and devised the test for Mersenne primes.
3
Ernst Eduard Kummer (1810–1893), German mathematician whose main achievement was the
extension of results about integers to other integral domains by introducing the concept of an ideal.

---

204
I Fundamentals, 10. Problems Involving Binomial Coefficients
and
(
1
+
x
)
p
2
= [
(
1
+
x
)
p
]
p
≡ [
1
+
x
p
]
p
≡
1
+
x
p
2
(
mod
p
),
and so on, so that for any positive integer
r
,
(
1
+
x
)
p
r
≡
1
+
x
p
r
(
mod
p
)
by induction.
We have
(
1
+
x
)
n
=
(
1
+
x
)
n
0
+
n
1
p
+···+
n
m
p
m
=
(
1
+
x
)
n
0
[
(
1
+
x
)
p
]
n
1
· · · [
(
1
+
x
)
p
m
]
n
m
≡
(
1
+
x
)
n
0
(
1
+
x
p
)
n
1
· · ·
(
1
+
x
p
m
)
n
m
(
mod
p
).
The coefficient of
x
i
in the expansion of
(
1
+
x
)
n
is
n
i
. On the other hand,
because
i
=
i
0
+
i
1
p
+ · · · +
i
m
p
m
, the coefficient of
x
i
is the coefficient of
x
i
0
(
x
p
)
i
1
· · ·
(
x
p
m
)
i
m
, which is equal to
n
0
i
0
n
1
i
1
· · ·
n
m
i
m
. Hence
n
i
≡
n
0
i
0
n
1
i
1
· · ·
n
m
i
m
(
mod
p
),
as desired.
Theorem 10.2.2.
(Kummer)
Let n and i be positive integers with i
≤
n, and let p
be a prime. Then p
t
divides
n
i
if and only if t is less than or equal to the number
of carries in the addition
(
n
−
i
)
+
i in base p.
Proof.
We will use the formula
e
p
(
n
)
=
n
−
S
p
(
n
)
p
−
1
,
(
2
)
where
e
p
is the Legendre function and
S
p
(
n
)
is the sum of the digits of
n
in base
p
(see Section 6.5). We actually prove that the largest nonnegative integer
t
such
that
p
t
divides
n
i
is exactly the number of carries in the addition
(
n
−
i
)
+
i
in
base
p
.
Let
n
=
a
m
a
m
−
1
· · ·
a
0
p
,
i
=
b
k
b
k
−
1
. . .
b
0
p
,
(
n
−
i
)
=
(
c
l
c
l
−
1
. . .
c
0
)
p
.
Because 1
≤
i
≤
n
, it follows that
k
,
l
≤
m
. Without loss of generality, we assume
that
k
≤
l
. Let
a
,
b
,
c
, and
t
be integers such that
p
a
n
!
,
p
b
i
!
,
p
c
(
n
−
i
)
!
,
and
p
t
n
i
. Then
t
=
a
−
b
−
c
.
From formula (2) we have
a
=
n
−
(
a
m
+
a
m
−
1
+ · · · +
a
0
)
p
−
1
,
b
=
i
−
(
b
k
+
b
k
−
1
+ · · · +
b
0
)
p
−
1
,
c
=
(
n
−
i
)
−
(
c
l
+
c
l
−
1
+ · · · +
c
0
)
p
−
1
.

---

10.2. Lucas’s and Kummer’s Theorems
205
Thus
t
=
−
(
a
m
+ · · · +
a
0
)
+
(
b
k
+ · · · +
b
0
)
+
(
c
l
+ · · · +
c
0
)
p
−
1
.
(
3
)
On the other hand, if we add
n
−
i
and
i
in base
p
, we have
b
k
b
k
−
1
. . .
b
1
b
0
c
l
c
l
−
1
. . .
c
k
c
k
−
1
. . .
c
1
c
0
a
m
a
m
−
1
. . .
a
l
a
l
−
1
. . .
a
k
a
k
−
1
. . .
a
1
a
0
Then we have either
b
0
+
c
0
=
a
0
(with no carry) or
b
0
+
c
0
=
a
0
+
p
(with
a carry of 1). More generally, we have
b
0
+
c
0
=
a
0
+
α
1
p
,
b
1
+
c
1
+
α
1
=
a
1
+
α
2
p
,
b
2
+
c
2
+
α
2
=
a
2
+
α
3
p
,
. . .
b
m
+
c
m
+
α
m
=
a
m
,
where
α
i
denotes the carry at the
(
i
−
1
)
th digit from the right. (Note also that
b
j
=
0 for
j
>
k
and that
c
j
=
0 for
j
>
l
.) Adding the above equations together
yields
(
b
0
+ · · · +
b
k
)
+
(
c
0
+ · · · +
c
l
)
=
(
a
0
+ · · · +
a
m
)
+
(
p
−
1
)(α
1
+ · · · +
α
m
).
Thus, equation (3) becomes
t
=
α
1
+ · · · +
α
m
,
as desired.
Problem 10.2.1.
Let n be a positive integer. Prove that the number of k
∈ {
0
,
1
,
. . .
, n
}
for which
n
k
is odd is a power of
2
.
Solution.
Let the base-2 expansion of
n
be 2
0
n
0
+
2
1
n
1
+ · · · +
2
a
n
a
, where
n
i
∈ {
0
,
1
}
for each
i
. Then for any
k
=
2
0
k
0
+
2
1
k
1
+ · · · +
2
a
k
a
, we have
n
k
≡
n
0
k
0
n
1
k
1
· · ·
n
a
k
a
(
mod 2
)
by Lucas’s theorem. Thus
n
k
is odd if and only if
k
i
≤
n
i
for each
i
. Let
m
be the
number of
n
i
’s equal to 1. Then the values of
k
∈ {
0
,
1,
. . .
, 2
a
+
1
−
1
}
for which
n
k
is odd are obtained by setting
k
i
=
0 or 1 for each of the
m
values of
i
such
that
n
i
=
1, and
k
i
=
0 for the other values of
i
. Thus there are 2
m
values of
k
in
{
0
,
1
, . . . ,
2
a
+
1
−
1
}
for which
n
k
is odd. Finally, note that for
k
>
n
,
n
k
=
0 is
never odd, so the number of
k
∈ {
0
,
1
, . . . ,
n
}
for which
n
k
is odd is 2
m
, a power
of 2.

---

206
I Fundamentals, 10. Problems Involving Binomial Coefficients
Problem 10.2.2.
Determine all positive integers n, n
≥
2
, such that
n
−
k
k
is even
for k
=
1
,
2
, . . . ,
n
2
.
(1999 Belarusian Mathematical Olympiad)
Solution.
Suppose that
p
=
2,
a
=
2
s
−
1, and
a
s
−
1
=
a
s
−
2
= · · · =
a
0
=
1.
For any
b
with 0
≤
b
≤
2
s
−
1, each term
a
i
b
i
in the above equation equals 1.
Therefore,
a
b
≡
1
(
mod 2
)
.
This implies that
n
+
1 is a power of two. Otherwise, let
s
= 
log
2
n
and let
k
=
n
−
(
2
s
−
1
)
=
n
−
2
s
+
1
−
2
2
≤
n
−
n
2
=
n
2
.
Then
n
−
k
k
=
2
s
−
1
k
is odd, a contradiction.
Conversely, suppose that
n
=
2
s
−
1 for some positive integer
s
. For
k
=
1
,
2
, . . . ,
n
2
, there is at least one 0 in the binary representation of
a
=
n
−
k
(not counting leading zeros, of course). Whenever there is a 0 in the binary rep-
resentation of
n
−
k
, there is a 1 in the corresponding digit of
b
=
k
. Then the
corresponding
a
i
b
i
equals 0, and by Lucas’s theorem,
n
−
k
k
is even.
Therefore,
n
=
2
s
−
1 for integers
s
≥
2.
Problem 10.2.3.
Prove that
2
n
k
, k
=
1
,
2
, . . . ,
2
n
−
1
, are all even and that
exactly one of them is not divisible by
4
.
Solution.
All these numbers are even, since
2
n
k
=
2
n
k
2
n
−
1
k
−
1
and 2
n
/
k
is different from 1 for all
k
=
1
,
2
, . . . ,
2
n
−
1.
From the same relation it follows that
2
n
k
is a multiple of 4 for all
k
different
from 2
n
−
1
. For
k
=
2
n
−
1
we have
2
n
2
n
−
1
=
2
2
n
−
1
2
n
−
1
−
1
.
But from Lucas’s theorem it follows that
2
n
−
1
2
n
−
1
−
1
is odd, since 2
n
−
1 contains
only 1’s in its binary representation and
1
k
=
1 if
k
=
0 or 1. This solves the
problem.
Additional Problems
Problem 10.2.4.
Let
p
be an odd prime. Find all positive integers
n
such that
n
1
,
n
2
, . . . ,
n
n
−
1
are all divisible by
p
.
Problem 10.2.5.
Let
p
be a prime. Prove that
p
does not divide any of
n
1
,
. . .
,
n
n
−
1
if and only if
n
=
sp
k
−
1 for some positive integer
k
and some integer
s
with 1
≤
s
≤
p
−
1.

---

11
Miscellaneous Problems
Problem 11.1.
Find all positive integers x
,
y
,
z that satisfy the conditions x
+
y
≥
2
z and x
2
+
y
2
−
2
z
2
=
8
.
(2003 “Alexandru Myller” Romanian Regional Contest)
First solution.
There are two possible cases:
Case I.
x
≥
y
≥
z
.
We set
x
−
z
=
a
≥
0,
y
−
z
=
b
≥
0,
a
≥
b
. We then obtain the equation
2
z
(
a
+
b
)
+
a
2
+
b
2
=
8. When
z
≥
3, there are no solutions. For
z
=
2, we get
(
a
+
2
)
2
+
(
b
+
2
)
2
=
16, which again has no solution. When
z
=
1 we obtain
solutions
(
x
,
y
,
z
)
=
(
3
,
1
,
1
)
and
(
x
,
y
,
z
)
=
(
1
,
3
,
1
)
. When
z
=
0,
a
2
+
b
2
=
8
and we get the solution
(
x
,
y
,
z
)
=
(
2
,
2
,
0
)
.
Case II.
x
≥
z
≥
y
.
Note again that
x
−
z
=
a
,
y
−
z
=
b
and obtain the solution
(
x
,
y
,
z
)
=
(
n
+
2
,
n
−
2
,
n
)
or
(
x
,
y
,
z
)
=
(
n
−
2
,
n
+
2
,
n
)
.
Second solution.
Let
x
=
z
+
a
≥
y
=
z
+
b
, where
a
+
b
≥
0 (
b
may be
negative). Then the equation becomes 2
(
a
+
b
)
z
+
a
2
+
b
2
=
8. Note that this
implies that
a
+
b
is even and
a
+
b
<
4. If
a
+
b
=
0, then we get
a
=
2 and
b
= −
2; hence
(
x
,
y
,
z
)
=
(
n
+
2
,
n
−
2
,
n
)
or
(
n
−
2
,
n
+
2
,
n
)
. If
a
+
b
=
2,
then
z
=
1,
a
=
2 and
b
=
0; hence
(
x
,
y
,
z
)
=
(
3
,
1
,
1
)
or
(
1
,
3
,
1
)
.
Problem 11.2.
Let n be a positive integer. Find all integers that can be written as
1
a
1
+
2
a
2
+ · · · +
n
a
n
,
for some positive integers a
1
,
a
2
, . . . ,
a
n
.
Solution.
First, observe that
k
=
1
a
1
+
2
a
2
+ · · · +
n
a
n
. Then
k
≤
1
+
2
+
3
+ · · · +
n
=
n
(
n
+
1
)
2
.
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica, 
Number Theory
,
 
DOI: 10.1007/b11856_11, 
207

---

208
I Fundamentals, 11. Miscellaneous Problems
We prove that any integer
k
∈
+
1
,
2
, . . . ,
n
(
n
+
1
)
2
,
can be written as requested.
For
k
=
1, put
a
1
=
a
2
= · · · =
a
n
=
n
(
n
+
1
)
2
.
For
k
=
n
, set
a
1
=
1,
a
2
=
2
, . . .
,
a
n
=
n
.
For 1
<
k
<
n
, let
a
k
−
1
=
1 and
a
i
=
n
(
n
+
1
)
2
−
k
+
1 for
i
=
k
−
1.
Thus
1
a
1
+
2
a
2
+ · · · +
n
a
n
=
k
−
1
1
+
i
=
1
i
=
k
−
1
i
a
i
=
k
−
1
+
n
(
n
+
1
)
2
−
k
+
1
n
(
n
+
1
)
2
−
k
+
1
=
k
.
For
n
<
k
<
n
(
n
+
1
)
2
, write
k
as
k
=
n
+
p
1
+
p
2
+ · · · +
p
i
,
with 1
≤
p
i
<
· · ·
<
p
2
<
p
1
≤
n
−
1.
Setting
a
p
1
+
1
=
a
p
2
+
1
= · · · =
a
p
i
+
1
=
1 and
a
j
=
j
otherwise, we are
done.
Problem 11.3.
Find all positive integers a
<
b
<
c
<
d with the property that
each of them divides the sum of the other three.
Solution.
Since
d
|
(
a
+
b
+
c
)
and
a
+
b
+
c
<
3
d
, it follows that
a
+
b
+
c
=
d
or
a
+
b
+
c
=
2
d
.
Case (i). If
a
+
b
+
c
=
d
, since
a
|
(
b
+
c
+
d
)
, we have
a
|
2
d
and similarly
b
|
2
d
,
c
|
2
d
.
Let 2
d
=
ax
=
by
=
cz
, where 2
<
z
<
y
<
x
. Thus
1
x
+
1
y
+
1
z
=
1
2
.
(a) If
z
=
3, then
1
x
+
1
y
=
1
6
. The solutions are
(
x
,
y
)
= {
(
42
,
7
), (
24
,
8
), (
18
,
9
), (
15
,
10
)
};
hence
(
a
,
b
,
c
,
d
)
∈
+
(
k
,
6
k
,
14
k
,
21
k
), (
k
,
3
k
,
8
k
,
12
k
),
(
k
,
2
k
,
6
k
,
9
k
), (
2
k
,
3
k
,
10
k
,
15
k
)
,
,
for
k
>
0.
(b) If
z
=
4, then
1
x
+
1
y
=
1
4
, and
(
x
,
y
)
= {
(
20
,
5
), (
12
,
6
)
}
.
The solutions are
(
a
,
b
,
c
,
d
)
=
(
k
,
4
k
,
5
k
,
10
k
)
and
(
a
,
b
,
c
,
d
)
=
(
k
,
2
k
,
3
k
,
6
k
),
for
k
>
0.

---

11. Miscellaneous Problems
209
(c) If
z
=
5, then
1
x
+
1
y
=
3
10
, and
(
3
x
−
10
)(
3
y
−
10
)
=
100.
Since 3
x
−
10
≡
2
(
mod 3
)
, it follows that 3
x
−
10
=
20 and 3
y
−
10
=
5.
Thus
y
=
5, false.
(d) If
z
≥
6 then
1
x
+
1
y
+
1
z
<
1
6
+
1
6
+
1
6
=
1
2
, so there are no solutions.
Case (ii). If
a
+
b
+
c
=
2
d
, we obtain
a
|
3
d
,
b
|
3
d
,
c
|
3
d
.
Then 3
d
=
ax
=
by
=
cz
, with
x
>
y
>
z
>
3 and
1
x
+
1
y
+
1
z
=
2
3
. Since
x
≥
4,
y
≥
5,
z
≥
6 we have
1
x
+
1
y
+
1
z
≤
1
6
+
1
5
+
1
4
=
37
60
<
2
3
, so there are no
solutions in this case.
Problem 11.4.
Find the greatest number that can be written as a product of some
positive integers whose sum is
1976
.
(18th International Mathematical Olympiad)
Solution.
Let
x
1
,
x
2
, . . . ,
x
n
be the numbers having the sum
x
1
+
x
2
+ · · · +
x
n
=
1976 and the maximum value of the product
x
1
·
x
2
· · ·
x
n
=
p
.
If one of the numbers, say
x
1
, is equal to 1, then
x
1
+
x
2
=
1
+
x
2
>
x
2
=
x
1
x
2
.
Hence the product
(
x
1
+
x
2
)
·
x
3
· · ·
x
n
is greater than
x
1
·
x
2
· · ·
x
n
=
p
, false.
Therefore
x
k
≥
2 for all
k
.
If one of the numbers is equal to 4, we can replace it with two numbers 2
without changing the sum or the product.
Suppose that
x
k
≥
5 for some
k
. Then
x
k
<
3
(
x
k
−
3
)
, so replacing the number
x
k
with the numbers 3 and
x
k
−
3, the sum remains constant while the product
increases, contradiction.
Therefore all the numbers are equal to 2 or 3. If there are more than three
numbers equal to 2, we can replace them by two numbers equal to 3, preserving
the sum and increasing the product (since 2
·
2
·
2
<
3
·
3). Hence at most two
terms equal to 2 are allowed. Since 1976
=
3
·
658
+
2, the maximum product is
equal to 2
·
3
658
.
Problem 11.5.
Prove that there exist infinitely many positive integers that cannot
be written in the form
x
3
1
+
x
5
2
+
x
7
3
+
x
9
4
+
x
11
5
for some positive integers x
1
,
x
2
,
x
3
,
x
4
,
x
5
.
(2002 Belarusian Mathematical Olympiad)
Solution.
For each integer
N
, we consider the number of integers in
[
1
,
N
]
that
can be written in the above form. Because
x
1
≤
N
1
3
, there are at most
N
1
3
ways
to choose
x
1
. A similar argument applies to the other
x
i
’s. Therefore, there are at
most
N
1
3
N
1
5
N
1
7
N
1
9
N
1
11
=
N
3043
3465
combinations. So there are at least
N
−
N
3043
3465
integers not covered. It is easy to see that this value can be arbitrarily large as
N
approaches infinity. Therefore, there exist infinitely many positive integers that
cannot be written in the form
x
3
1
+
x
5
2
+
x
7
3
+
x
9
4
+
x
11
5
.

---

210
I Fundamentals, 11. Miscellaneous Problems
Additional Problems
Problem 11.6.
Let
a
,
b
be positive integers. By integer division of
a
2
+
b
2
by
a
+
b
we obtain the quotient
q
and the remainder
r
. Find all pairs
(
a
,
b
)
such that
q
2
+
r
=
1977.
(19th International Mathematical Olympiad)
Problem 11.7.
Let
m
,
n
be positive integers. Show that 25
n
−
7
m
is divisible by
3 and find the least positive integer of the form
|
25
n
−
7
m
−
3
m
|
, where
m
,
n
run
over the set of positive integers.
(2004 Romanian Mathematical Regional Contest)
Problem 11.8.
Given an integer
d
, let
S
= {
m
2
+
dn
2
|
m
,
n
∈
Z
}
.
Let
p
,
q
∈
S
be such that
p
is a prime and
r
=
q
p
is an integer. Prove that
r
∈
S
.
(1999 Hungary–Israel Mathematical Competition)
Problem 11.9.
Prove that every positive rational number can be represented in the
form
a
3
+
b
3
c
3
+
d
3
,
where
a
,
b
,
c
,
d
are positive integers.
(1999 International Mathematical Olympiad Shortlist)
Problem 11.10.
Two positive integers are written on the board. The following
operation is repeated: if
a
<
b
are the numbers on the board, then
a
is erased and
ab
/(
b
−
a
)
is written in its place. At some point the numbers on the board are
equal. Prove that again they are positive integers.
(1998 Russian Mathematical Olympiad)
Problem 11.11.
Let
f
(
x
)
+
a
0
+
a
1
x
+ · · · +
a
m
x
m
, with
m
≥
2 and
a
m
=
0,
be a polynomial with integer coefficients. Let
n
be a positive integer, and suppose
that:
(i)
a
2
,
a
3
, . . . ,
a
m
are divisible by all the prime factors of
n
;
(ii)
a
1
and
n
are relatively prime.
Prove that for any positive integer
k
, there exists a positive integer
c
such that
f
(
c
)
is divisible by
n
k
.
(2001 Romanian International Mathematical Olympiad Team Selection Test)

---

11. Miscellaneous Problems
211
Problem 11.12.
Let
x
,
a
,
b
be positive integers such that
x
a
+
b
=
a
b
b
. Prove that
a
=
x
and
b
=
x
x
.
(1998 Iranian Mathematical Olympiad)
Problem 11.13.
Let
m
,
n
be integers with 1
≤
m
<
n
. In their decimal repre-
sentations, the last three digits of 1978
m
are equal, respectively, to the last three
digits of 1978
n
. Find
m
and
n
such that
m
+
n
is minimal.
(20th International Mathematical Olympiad)

---

---

II
Solutions to Additional Problems

---

---

1
Divisibility
1.1
Divisibility
Problem 1.1.10.
Show that for any natural number n, one can find three distinct
natural numbers a
,
b
,
c between n
2
and
(
n
+
1
)
2
such that a
2
+
b
2
is divisible
by c.
(1998 St. Petersburg City Mathematical Olympiad)
Solution.
(We must assume
n
>
1.) Take
a
=
n
2
+
2
,
b
=
n
2
+
n
+
1
,
c
=
n
2
+
1
.
Then
a
2
+
b
2
=
(
2
n
2
+
2
n
+
5
)
c
.
Problem 1.1.11.
Find all odd integers n greater than
1
such that for any relatively
prime divisors a and b of n, the number a
+
b
−
1
is also a divisor of n.
(2001 Russian Mathematical Olympiad)
Solution.
We will call a number “good” if it satisfies the given conditions. It is not
difficult to see that all prime powers are good. Suppose
n
is a good number that
has at least two distinct prime factors. Let
n
=
p
r
s
, where
p
is the smallest prime
dividing
n
, and
s
is not divisible by
p
. Because
n
is good,
p
+
s
−
1 must divide
n
.
For any prime
q
dividing
s
,
s
<
p
+
s
−
1
<
s
+
q
, so
q
does not divide
p
+
s
−
1.
Therefore, the only prime factor of
p
+
s
−
1 is
p
. Then
s
=
p
c
−
p
+
1 for some
c
>
1. Because
p
c
must also divide
n
,
p
c
+
s
−
1
=
2
p
c
−
p
divides
n
. Because
2
p
c
−
1
−
1 has no factors of
p
, it must divide
s
. Since every prime divisor of
s
is
larger than
p
, we must have either
s
>
p
(
2
p
c
−
1
−
1
)
or
s
=
2
p
c
−
1
−
1. In the first
case, rearranging gives 1
>
p
c
, a contradiction. In the second case, rearranging
gives
(
p
−
2
)(
p
c
−
1
−
1
)
=
0. Hence
p
=
2, contrary to the assumption that
n
is
odd.
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica, 
Number Theory
,
 
DOI: 10.1007/b11856_12, 
215

---

216
II Solutions, 1. Divisibility
Problem 1.1.12.
Find all positive integers n such that
3
n
−
1
+
5
n
−
1
divides
3
n
+
5
n
.
So only prime powers are good.
(1996 St. Petersburg City Mathematical Olympiad)
First solution.
This occurs only for
n
=
1. Let
s
n
=
3
n
+
5
n
and note that
s
n
=
(
3
+
5
)
s
n
−
1
−
3
·
5
·
s
n
−
2
,
so
s
n
−
1
must also divide 3
·
5
·
s
n
−
2
. If
n
>
1, then
s
n
−
1
is coprime to 3 and 5, so
s
n
−
1
must divide
s
n
−
2
, which is impossible since
s
n
−
1
>
s
n
−
2
.
Second solution.
Note that 1
<
3
n
+
5
n
3
n
−
1
+
5
n
−
1
<
5, so we can have only
3
n
+
5
n
3
n
−
1
+
5
n
−
1
∈
{
2
,
3
,
4
}
cases, which are easily checked.
Problem 1.1.13.
Find all positive integers n such that the set
{
n
,
n
+
1
,
n
+
2
,
n
+
3
,
n
+
4
,
n
+
5
}
can be split into two disjoint subsets such that the products of elements in these
subsets are the same.
(12th International Mathematical Olympiad)
Solution.
At least one of six consecutive numbers is divisible by 5. From the
given condition it follows that two numbers must be divisible by 5. These two
numbers are necessarily
n
and
n
+
5. Therefore
n
and
n
+
5 are in distinct subsets.
Since
n
(
n
+
1
) >
n
+
5 for
n
≥
3, it follows that a required partition cannot
be considered with subsets of different cardinality. Thus each subset must contain
three numbers. The following possibilities have to be considered:
(a)
{
n
,
n
+
2
,
n
+
4
} ∪ {
n
+
1
,
n
+
3
,
n
+
5
}
,
(b)
{
n
,
n
+
3
,
n
+
4
} ∪ {
n
+
1
,
n
+
2
,
n
+
5
}
.
In case (a),
n
<
n
+
1,
n
+
2
<
n
+
3, and
n
+
4
<
n
+
5.
In case (b), the condition of the problem gives
n
(
n
+
3
)(
n
+
4
)
=
(
n
+
1
)(
n
+
3
)(
n
+
5
).
We obtain
n
2
+
5
n
+
10
=
0, and this equation has no real solution.
Remark.
One can prove that if
p
is a prime of the form 4
k
+
3, then one cannot