Number Theory: Structures, Examples, and Problems

3.2. Floor Function and Integer Points
71
Then
N
1
=
N
2
; hence
n
(
N
1
)
=
n
(
N
2
)
and
a
≤
k
≤
b
(
f
(
k
)
+
1
)
=
n
(
N
1
)
+
n
(
N
3
),
c
≤
k
≤
d
(
f
−
1
(
k
)
+
1
)
=
n
(
N
2
)
+
n
(
N
4
),
n
(
N
3
)
=
(
b
+
1
− 
a
)
c
,
n
(
N
4
)
=
(
d
+
1
− 
c
)
a
.
It follows that
a
≤
k
≤
b
f
(
k
)
−
c
≤
k
≤
d
f
−
1
(
k
)
=
(
b
+
1
− 
a
)
c
−
1
−
(
d
+
1
− 
c
)
a
−
1
= 
b
c
−
1
− 
d
a
−
1
.
Remark.
Combining the result in Theorem 3.2.3 and the relation (3) for the func-
tion
f
: [
0
,
n
] → [
0
,
m
]
,
f
(
x
)
= −
m
n
x
+
m
,
m
≤
n
, yields, after some computa-
tion,
n
k
=
1
%
km
n
&
=
1
2
(
mn
+
m
−
n
+
gcd
(
m
,
n
)).
(
4
)
From the above relation we obtain
gcd
(
m
,
n
)
=
2
n
−
1
k
=
1
%
km
n
&
+
m
+
n
+
mn
,
the proof of which was a 1998 Taiwanese Mathematical Olympiad problem.
From here we get
n
−
1
k
=
1
km
n
=
n
−
1
k
=
1
km
n
−
n
−
1
k
=
1
%
km
n
&
=
m
n
·
(
n
−
1
)
n
2
−
1
2
(
mn
−
m
−
n
+
gcd
(
m
,
n
))
=
1
2
(
n
−
gcd
(
m
,
n
)),
which was a 1995 Japanese Mathematical Olympiad problem.
Problem 3.2.1.
Express
"
n
k
=
1
√
k
in terms of n and a
= 
√
n
.
(1997 Korean Mathematical Olympiad)

---

72
I Fundamentals, 3. Floor Function and Fractional Part
Solution.
We apply Theorem 3.2.1 for the function
f
: [
1
,
n
] → [
1
,
√
n
]
,
f
(
x
)
=
√
x
. Because
n
(
G
f
)
= 
√
n
, we have
n
k
=
1
√
k
+
√
n
k
=
1
k
2
− 
√
n
=
n
√
n
,
hence
n
k
=
1
√
k
=
(
n
+
1
)
a
−
a
(
a
+
1
)(
2
a
+
1
)
6
.
Problem 3.2.2.
Compute
S
n
=
n
(
n
+
1
)
2
k
=
1
−
1
+
√
1
+
8
k
2
.
Solution.
Consider the function
f
: [
1
,
n
] →
1
,
n
(
n
+
1
)
2
,
f
(
x
)
=
x
(
x
+
1
)
2
.
The function
f
is increasing and bijective. Note that
n
(
G
f
)
=
n
and
f
−
1
(
x
)
=
−
1
+
√
1
+
8
x
2
. Applying the formula in Theorem 3.2.1, we obtain
n
k
=
1
%
k
(
k
+
1
)
2
&
+
n
(
n
+
1
)
2
k
=
1
'
−
1
+
√
1
+
8
k
2
(
−
n
=
n
2
(
n
+
1
)
2
;
hence
n
(
n
+
1
)
2
k
=
1
−
1
+
√
1
+
8
k
2
=
n
2
(
n
+
1
)
2
+
n
−
1
2
n
k
=
1
k
(
k
+
1
)
=
n
2
(
n
+
1
)
2
+
n
−
n
(
n
+
1
)
4
−
n
(
n
+
1
)(
2
n
+
1
)
12
=
n
(
n
2
+
2
)
3
.
Additional Problems
Problem 3.2.3.
Prove that
n
k
=
1
'
n
2
k
2
(
=
n
2
k
=
1
%
n
√
k
&
for all integers
n
≥
1
.

---

3.3. A Useful Result
73
Problem 3.2.4.
Let
θ
be a positive irrational number. Then, for any positive inte-
ger
m
,
m
k
=
1
k
θ
+
m
θ
k
=
1
%
k
θ
&
=
m
m
θ
.
Problem 3.2.5.
Let
p
and
q
be relatively prime positive integers and let
m
be a
real number such that 1
≤
m
<
p
.
(1) If
s
=
#
mq
p
$
, then
m
k
=
1
%
kq
p
&
+
s
k
=
1
%
kp
q
&
= 
m
s
.
(2) (Landau
2
) If
p
and
q
are odd, then
p
−
1
2
k
=
1
%
kq
p
&
+
q
−
1
2
k
=
1
%
kp
q
&
=
(
p
−
1
)(
q
−
1
)
4
.
3.3
A Useful Result
The following theorem is also helpful in proving some relations involving the
floor function.
Theorem 3.3.1.
Let p be an odd prime and let q be an integer that is not divisible
by p. If f
:
Z
∗
+
→
R
is a function such that:
(i)
f
(
k
)
p
is not an integer, k
=
1
,
2
, . . . ,
p
−
1
;
(ii) f
(
k
)
+
f
(
p
−
k
)
is an integer divisible by p, k
=
1
,
2
, . . . ,
p
−
1
;
then
p
−
1
k
=
1
%
f
(
k
)
q
p
&
=
q
p
p
−
1
k
=
1
f
(
k
)
−
p
−
1
2
.
(
1
)
Proof.
From (ii) it follows that
q f
(
k
)
p
+
q f
(
p
−
k
)
p
∈
Z
,
(
2
)
2
Edmond Georg Hermann Landau (1877–1838), German mathematician who gave the first sys-
tematic presentation of analytic number theory and wrote an important work on the theory of analytic
functions of a single variable.

---

74
I Fundamentals, 3. Floor Function and Fractional Part
and from (i) we obtain that
q f
(
k
)
p
∈
Z
and
q f
(
p
−
k
)
p
∈
Z
,
k
=
1
, . . . ,
p
−
1; hence
0
<
)
q f
(
k
)
p
*
+
)
q f
(
p
−
k
)
p
*
<
2
.
But from (2),
+
q f
(
k
)
p
,
+
+
q f
(
p
−
k
)
p
,
∈
Z
; thus
)
q f
(
k
)
p
*
+
)
q f
(
p
−
k
)
p
*
=
1
,
k
=
1
, . . . ,
p
−
1
.
Summing up and dividing by 2 yields
p
−
1
k
=
1
)
q
p
f
(
k
)
*
=
p
−
1
2
.
It follows that
p
−
1
k
=
1
q
p
f
(
k
)
−
p
−
1
k
=
1
%
q
p
f
(
k
)
&
=
p
−
1
2
,
and the conclusion follows.
Problem 3.3.1.
Let p and q be two relatively prime integers. The following iden-
tity holds:
p
−
1
k
=
1
%
k
q
p
&
=
(
p
−
1
)(
q
−
1
)
2
(Gauss)
.
Solution.
The function
f
(
x
)
=
x
satisfies both (i) and (ii) in Theorem 3.3.1;
hence
p
−
1
k
=
1
%
k
q
p
&
=
q
p
(
p
−
1
)
p
2
−
p
−
1
2
,
and the desired relation follows.
Problem 3.3.2.
Let p be an odd prime. Prove that
p
−
1
k
=
1
'
k
3
p
(
=
(
p
−
2
)(
p
−
1
)(
p
+
1
)
4
.
(2002 German Mathematical Olympiad)
Solution.
The function
f
(
x
)
=
x
3
also satisfies conditions (i) and (ii); hence
p
−
1
k
=
1
%
k
3
q
p
&
=
q
p
·
(
p
−
1
)
2
p
2
4
−
p
−
1
2
=
(
p
−
1
)(
p
2
q
−
pq
−
2
)
4
.
For
q
=
1 the identity in our problem follows.

---