Number Theory: Structures, Examples, and Problems

Part I, Section 10.1).
We prove that the set of positive integers
k
for which the claim holds is exactly
the set of primes.
Suppose now that
k
is not a prime. Then consider two cases:
(a)
k
=
p
r
, where
p
is a prime and
r
>
1. We find a value of
i
for which
k
n
i
.
Suppose, to the contrary, that there is a positive integer
n
such that for all
1
≤
i
≤
n
−
1,
n
i
is divisible by
p
r
. Clearly,
n
is divisible by
p
r
, and we write
n
=
p
α
β
for some
β
with gcd
(β,
p
)
=
1. Take
i
=
p
α
−
1
. Then
n
i
=
p
α
−
1
−
1
j
=
0
β
p
α
−
j
p
α
−
1
−
j
.
If
j
=
0, then
β
p
α
−
j
p
α
−
1
−
j
=
β
p
. If gcd
(
j
,
p
)
=
1, then both the above numerator
and denominator are coprime to
p
. In all other cases, we write
j
=
δ
p
γ
for some
δ
coprime to
p
and
γ
≤
α
−
2. Thus,
β
p
α
−
j
p
α
−
1
−
j
=
β
p
α
−
δ
p
γ
p
α
−
1
−
δ
p
γ
=
p
γ
(β
p
α
−
γ
−
δ)
p
γ
(
p
α
−
γ
−
1
−
δ)
.

---

360
II Solutions, 10. Problems Involving Binomial Coefficients
Now, since
α
−
γ
−
1
≥
1, we have
β
p
α
−
γ
−
δ
and
p
α
−
γ
−
1
−
δ
coprime to
p
. In this case, the power of
p
in the above numerator and denominator is
γ
, and
the power of
p
in the above product of fractions, which is an integer, is 1. This
contradicts the assumption that
p
r
|
n
.
(b)
k
is divisible by at least two distinct primes
p
,
q
. Assume by contradiction
that there is a positive integer
n
as required. Then
n
is divisible by
pq
and we can
write
n
=
p
α
β
where gcd
(
p
, β)
=
1 and
β >
1 (since
q
divides
β
). Take
i
=
p
α
.
Then
n
i
=
p
α
−
1
j
=
0
β
p
α
−
j
p
α
−
j
.
When
j
=
0,
β
p
α
−
j
p
α
−
j
=
β
is coprime to
p
. In all other cases, both the numer-
ator and the denominator of
β
p
α
−
j
p
α
−
j
are either coprime to
p
or are divisible by the
same power of
p
, and therefore the product of those fractions is not divisible by
p
. But
p
divides
k
, and hence
n
i
is not divisible by
k
, contrary to our assumption.
Therefore the only positive integers
k
for which the claim holds are the primes.
10.2
Lucas’s and Kummer’s Theorems
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.
Solution.
Express
n
in base
p
:
n
=
n
0
+
n
1
p
+ · · · +
n
m
p
m
, where 0
≤
n
0
,
n
1
, . . . ,
n
m
≤
p
−
1 and
n
m
≤
0. We also write
k
=
k
0
+
k
1
p
+ · · · +
k
m
p
m
,
where 0
≤
k
0
,
k
1
, . . . ,
k
m
≤
p
−
1, where
k
m
can be zero. From Lucas’s theorem
we have
n
k
≡
m
j
=
0
n
j
k
j
(
mod
p
).
For
n
=
p
m
, the property clearly holds. Assume by way of contradiction that
n
=
p
m
. If
n
m
>
1, then letting
k
=
p
m
<
n
, we have
n
k
≡
n
m
·
1
·
1
·
1
· · ·
1
m
−
1 times
≡
n
m
≡
0
(
mod
p
),
a contradiction.
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
.

---

10.2. Lucas’s and Kummer’s Theorems
361
Solution.
If
n
is of the form
sp
k
−
1, then its representation in base
p
is
n
=
(
s
−
1
) (
p
−
1
)
· · ·
(
p
−
1
)
k
times
.
For 1
≤
i
≤
n
−
1,
i
=
i
0
+
i
1
p
+ · · · +
i
m
p
m
, where 0
≤
i
h
≤
p
−
1,
h
=
1
, . . . ,
m
−
1, and 0
≤
i
m
≤
s
−
1. Because
p
is a prime, it follows that
p
does not divide either
p
−
1
i
h
or
s
−
1
i
m
. Applying Lucas’s theorem, we obtain that
p
does not divide
n
i
, for all
i
=
1
, . . . ,
n
−
1.
Conversely, if
n
cannot be written in the form
sp
k
−
1, then
n
j
<
p
−
1 for
some 0
≤
j
≤
m
−
1, where
n
0
n
1
· · ·
n
m
is the representation of
n
in base
p
. For
i
=
(
p
−
1
)
0
. . .
0
j
−
1 times
in base
p
, applying again Lucas’s theorem, we have
n
i
≡
0
(
mod
p
).

---

---

11
Miscellaneous 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)
Solution.
There are finitely many possibilities to obtain 1977
=
q
2
+
r
. Since
1977 is not a perfect square, 0
<
r
<
a
+
b
. Also,
q
≤ 
√
1977
=
44. From
a
2
+
b
2
=
q
(
a
+
b
)
+
r
, we obtain
q
=
'
a
2
+
b
2
a
+
b
(
≥
a
2
+
b
2
a
+
b
−
1
≥
1
2
(
a
+
b
)
−
1
>
r
2
−
1
.
Suppose
q
≤
43. Then
r
=
1977
−
q
2
≥
1977
−
43
2
=
128 and 43
≥
q
>
r
2
−
1
≥
63, contradiction.
We have obtained
q
=
44 and
r
=
1977
−
44
2
=
41. To finish, we have to
solve in integers the equation
a
2
+
b
2
=
44
(
a
+
b
)
+
41
.
Write it in the form
(
a
−
22
)
2
+
(
b
−
22
)
2
=
1009
.
It is not difficult to find all pairs of perfect squares having the sum 1009. There
exists only the representation 1009
=
28
2
+
15
2
. Then the solutions are
a
=
50,
b
=
37 and
a
=
37,
b
=
50.
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)
© Birkhäuser Boston, a part of Springer Science + Business Media, LLC 2009
T. Andreescu and D. Andrica, 
Number Theory
,
 
DOI: 10.1007/b11856_22, 
363

---

364
II Solutions, 11. Miscellaneous Problems
Solution.
Because 25
≡
1
(
mod 3
)
and 7
≡
1
(
mod 3
)
, it follows that 25
n
−
7
m
≡
0
(
mod 3
)
.
For the second part of the problem, we first remark that if
m
is odd, then any
number
a
=
25
n
−
7
m
−
3
m
is divisible by 15. This follows from the first part
together with
7
m
+
3
m
≡
2
m
+
(
−
2
)
m
≡
0
(
mod 5
).
Moreover, for
m
=
n
=
1 one obtains 25
−
7
−
3
=
15.
Assume now that
m
is even, say
m
=
2
k
. Then
7
m
+
3
m
=
7
2
k
+
3
2
k
≡
((
−
3
)
2
k
+
3
2
k
) (
mod 10
)
≡
2
·
9
k
(
mod 10
)
≡ ±
2
(
mod 10
)
≡
2 or 8
(
mod 10
).
So, the last digit of the number 25
n
−
7
m
−
3
m
is either 3 or 7. Because the
number 25
n
−
7
m
−
3
m
is divisible by 3, the required number cannot be 7. The
situation
|
25
n
−
7
m
−
3
m
| =
3 also cannot occur, because 25
n
−
7
m
−
3
m
≡ −
1
(
mod 8
)
.
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)
Solution.
Note that
(
x
2
+
d y
2
)(
u
2
+
d
v
2
)
=
(
xu
±
d y
v)
2
+
d
(
x
v
∓
yu
)
2
.
Write
q
=
a
2
+
db
2
and
p
=
x
2
+
d y
2
for integers
a
,
b
,
x
,
y
. Reversing
the above construction yields the desired result. Indeed, solving for
u
and
v
after
setting
a
=
xu
+
d y
v
,
b
=
x
v
−
yu
, and
a
=
xu
−
d y
v
,
b
=
x
v
+
yu
gives
u
1
=
ax
−
dby
p
, v
1
=
ay
+
bx
p
,
u
2
=
ax
+
dby
p
, v
2
=
ay
−
bx
p
.
Note that
(
ay
+
bx
)(
ay
−
bx
)
=
(
a
2
+
db
2
)
y
2
−
(
x
2
+
d y
2
)
b
2
≡
0
(
mod
p
).
Hence
p
divides one of
ay
+
bx
,
ay
−
bx
so that one of
v
1
, v
2
is an integer.
Without loss of generality, assume that
v
1
is an integer. Because
r
=
u
2
1
+
d
v
2
1
is
an integer and
u
1
is rational,
u
1
is an integer as well and
r
∈
S
, as desired.

---

11. Miscellaneous Problems
365
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)
Solution.
We first claim that if
m
,
n
are positive integers such that the rational
number
r
=
m
n
belongs to the interval
(
1
,
2
)
, then
r
can be represented in the
form
a
3
+
b
3
c
3
+
d
3
.
This can be realized by taking
a
2
−
ab
+
b
2
=
a
2
−
ad
+
d
2
, i.e.,
b
+
d
=
a
and
a
+
b
=
3
m
,
a
+
d
=
2
a
−
b
=
3
n
; that is,
a
=
m
+
n
,
b
=
2
m
−
n
,
d
=
2
n
−
m
.
We will prove now the required conclusion. If
s
>
0 is a rational number, take
positive integers
p
,
q
such that 1
<
p
3
q
3
s
<
2. There exist positive integers
a
,
b
,
d
such that
p
3
q
3
s
=
a
3
+
b
3
a
3
+
d
3
, whence
s
=
(
aq
)
3
+
(
bq
)
3
(
ap
)
3
+
(
d p
)
3
.
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
are equal. Prove that again they are positive integers.
(1998 Russian Mathematical Olympiad)
Solution.
Call the original numbers
x
and
y
and let
L
=
lcm
(
x
,
y
)
. For each num-
ber
n
on the board consider the quotient
L
/
n
; during each operation, the quotients
L
/
b
and
L
/
a
become
L
/
b
and
L
/
a
−
L
/
b
. Thus in terms of the quotients
L
/
a
and
L
/
b
, the operation is subtracting the smaller quotient from the larger. This is
the Euclidean algorithm, so the quantity gcd
(
L
/
a
,
L
/
b
)
is unchanged. Hence the
two equal numbers on the board are
L
/
gcd
(
L
/
x
,
L
/
y
)
. But gcd
(
L
/
x
,
L
/
y
)
=
1,
because otherwise
x
and
y
would both divide
L
/
gcd
(
L
/
x
,
L
/
y
)
and
L
would not
be a least common multiple. So, the two equal numbers equal
L
=
lcm
(
x
,
y
)
, an
integer.
numbers eventually equal
N
. We prove by induction on the number of steps
k
before we obtain
(
N
,
N
)
that all previous numbers divide
N
in the sense that
N
/
c
is an integer. Specifically,
x
|
N
, so
N
must be an integer.
The claim is clear for
k
=
0. Now assume that
k
steps before we obtain
(
N
,
N
)
, the numbers on the board are
(
c
,
d
)
=
(
N
/
p
,
N
/
q
)
for some integers
p
<
q
. Then reversing the operation, the number erased in the
(
k
+
1
)
st step must
be
cd
/(
c
+
d
)
=
N
/(
p
+
q
)
, completing the inductive step.
Second solution.
Again, let
x
and
y
be the original numbers and suppose both
and ab
/(
b
−
a
)
is written in its place. At some point the numbers on the board

---

366
II Solutions, 11. Miscellaneous Problems
Problem 11.11.
Let f
(
x
)
+
a
0
+
a
1
x
+ · · · +
a
m
x
m
, with m
≥
2
and a
m
=
0
,
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 every 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)
Solution.
Consider any integers
c
1
,
c
2
such that
c
1
≡
c
2
(
mod
n
k
)
. Observe that
if
n
k
|
st
for some integers
s
,
t
where
t
is relatively prime to
n
, then
n
k
|
s
. In