Exercises from Section 1.2.4

1. [00] What are

⌊ 1.1 ⌋

⌊ - 1.1 ⌋

⌈ - 1.1 ⌉

⌊ 0.99999 ⌋

, and

⌊ \lg 35 ⌋

We have:

\begin{array}{l} ⌊ 1.1 ⌋ & = 1 & 1 \leq 1.1 < 2 \\ ⌊ - 1.1 ⌋ & = - 2 & - 2 \leq - 1.1 < - 1 \\ ⌈ - 1.1 ⌉ & = - 1 & - 2 < - 1.1 \leq - 1 \\ ⌊ 0.99999 ⌋ & = 0 & 0 \leq 0.99999 < 1 \\ ⌊ \lg 35 ⌋ & = 5 & 5 = \lg 32 \leq \lg 35 < \lg 64 = 6 \end{array}

$⌈ ⌊ x ⌋ ⌉ = ⌊ x ⌋$ since $⌊ x ⌋$ is an integer and $⌊ x ⌋ - 1 < ⌊ x ⌋ \leq ⌊ x ⌋$ .

3. [M10] Let

n

be an integer, and let

x

be a real number. Prove that a)

⌊ x ⌋ < n

if and only if

x < n

; b)

n \leq ⌊ x ⌋

if and only if

n \leq x

; c)

⌈ x ⌉ \leq n

if and only if

x \leq n

; d)

n < ⌈ x ⌉

if and only if

n < x

; e)

⌊ x ⌋ = n

if and only if

x - 1 < n \leq x

, and if and only if

n \leq x < n + 1

; f)

⌈ x ⌉ = n

if and only if

x \leq n < x + 1

, and if and only if

n - 1 < x \leq n

[These formulas are the most important tools for proving facts about

⌊ x ⌋

and

⌈ x ⌉

We may prove the various propositions.

Proposition (A). $⌊ x ⌋ < n$ if and only if $x < n$ for all integers $n$ , real numbers $x$ .

Proof. Let $n$ be an integer and $x$ a real number. We must show that $⌊ x ⌋ < n$ if and only if $x < n$ .

If $⌊ x ⌋ < n$ :

\begin{array}{l} ⌊ x ⌋ \leq x < ⌊ x ⌋ + 1 \\ ⌊ x ⌋ < n \Rightarrow ⌊ x ⌋ + 1 \leq n \\ ∴ & x < n \end{array}

If $x < n$ :

\begin{array}{l} ⌊ x ⌋ \leq x < ⌊ x ⌋ + 1 \\ x < n \\ ∴ & ⌊ x ⌋ < n \end{array}

Therefore, $⌊ x ⌋ < n$ if and only if $x < n$ . □

Proposition (B). $n \leq ⌊ x ⌋$ if and only if $n \leq x$ for all integers $n$ , real numbers $x$ .

Proof. Let $n$ be an integer and $x$ a real number. We must show that $n \leq ⌊ x ⌋$ if and only if $n \leq x$ .

If $n \leq ⌊ x ⌋$ :

\begin{array}{l} ⌊ x ⌋ \leq x < ⌊ x ⌋ + 1 \\ n \leq ⌊ x ⌋ \\ ∴ & n \leq x \end{array}

If $n \leq x$ :

\begin{array}{l} ⌊ x ⌋ \leq x < ⌊ x ⌋ + 1 \Rightarrow ⌊ x ⌋ - 1 \leq x - 1 < ⌊ x ⌋ \\ n \leq x \\ ∴ & n < ⌊ x ⌋ + 1 \Rightarrow n \leq ⌊ x ⌋ \end{array}

Therefore, $n \leq ⌊ x ⌋$ if and only if $n \leq x$ . □

Proposition (C). $⌈ x ⌉ \leq n$ if and only if $x \leq n$ for all integers $n$ , real numbers $x$ .

Proof. Let $n$ be an integer and $x$ a real number. We must show that $⌈ x ⌉ \leq n$ if and only if $x \leq n$ .

If $⌈ x ⌉ \leq n$ :

\begin{array}{l} ⌈ x ⌉ - 1 < x \leq ⌈ x ⌉ \\ ⌈ x ⌉ \leq n \\ ∴ & x \leq n \end{array}

If $x \leq n$ :

\begin{array}{l} ⌈ x ⌉ - 1 < x \leq ⌈ x ⌉ \\ x \leq n \\ ∴ & ⌈ x ⌉ - 1 < n \Rightarrow ⌈ x ⌉ \leq n \end{array}

Therefore, $⌈ x ⌉ \leq n$ if and only if $x \leq n$ . □

Proposition (D). $n < ⌈ x ⌉$ if and only if $n < x$ for all integers $n$ , real numbers $x$ .

Proof. Let $n$ be an integer and $x$ a real number. We must show that $n < ⌈ x ⌉$ if and only if $n < x$ .

If $n < ⌈ x ⌉$ :

\begin{array}{l} ⌈ x ⌉ - 1 < x \leq ⌈ x ⌉ \\ n < ⌈ x ⌉ \Rightarrow n \leq ⌈ x ⌉ - 1 \\ ∴ & n < x \end{array}

If $n < x$ :

\begin{array}{l} ⌈ x ⌉ - 1 < x \leq ⌈ x ⌉ \\ n < x \\ ∴ & n < ⌈ x ⌉ \end{array}

Therefore, $n < ⌈ x ⌉$ if and only if $n < x$ . □

Proposition (E). $⌊ x ⌋ = n$ if and only if $x - 1 < n \leq x$ , and if and only if $n \leq x < n + 1$ for all integers $n$ , real numbers $x$ .

Proof. Let $n$ be an integer and $x$ a real number. We must show that $⌊ x ⌋ = n$ if and only if $x - 1 < n \leq x$ , and if and only if $n \leq x < n + 1$ .

If $⌊ x ⌋ = n$ :

\begin{array}{l} ⌊ x ⌋ = n \Rightarrow n \leq ⌊ x ⌋ \Rightarrow n \leq x & from (b) \\ ⌊ x ⌋ = n \Rightarrow ⌊ x ⌋ \leq n \Rightarrow ⌊ x ⌋ < n + 1 \Rightarrow x < n + 1 \equiv x - 1 < n & from (a) \\ ∴ & x - 1 < n \leq x \land n \leq x < n + 1 \end{array}

If $x - 1 < n \leq x$ :

\begin{array}{l} x - 1 < n \leq x \Rightarrow n \leq ⌊ x ⌋ & from (b) \\ x - 1 < n \leq x \Rightarrow x < n + 1 \Rightarrow ⌊ x ⌋ < n + 1 \Rightarrow ⌊ x ⌋ \leq n & from (a) \\ ∴ & n \leq ⌊ x ⌋ \land ⌊ x ⌋ \leq n \Rightarrow ⌊ x ⌋ = n \end{array}

If $n \leq x < n + 1$ :

\begin{array}{l} n \leq x < n + 1 \Rightarrow n \leq ⌊ x ⌋ & from (b) \\ n \leq x < n + 1 \Rightarrow x < n + 1 \Rightarrow ⌊ x ⌋ < n + 1 \Rightarrow ⌊ x ⌋ \leq n & from (a) \\ ∴ & n \leq ⌊ x ⌋ \land ⌊ x ⌋ \leq n \Rightarrow ⌊ x ⌋ = n \end{array}

Therefore, $⌊ x ⌋ = n$ if and only if $x - 1 < n \leq x$ , and if and only if $n \leq x < n + 1$ . □

Proposition (F). $⌈ x ⌉ = n$ if and only if $x \leq n < x + 1$ , and if and only if $n - 1 < x \leq n$ for all integers $n$ , real numbers $x$ .

Proof. Let $n$ be an integer and $x$ a real number. We must show that $⌈ x ⌉ = n$ if and only if $x \leq n < x + 1$ , and if and only if $n - 1 < x \leq n$ .

If $⌈ x ⌉ = n$ :

\begin{array}{l} ⌈ x ⌉ = n \Rightarrow ⌈ x ⌉ \leq n \Rightarrow x \leq n & from (c) \\ ⌈ x ⌉ = n \Rightarrow n \leq ⌈ x ⌉ \Rightarrow n - 1 < ⌈ x ⌉ \Rightarrow n - 1 < x \equiv n < x + 1 & from (d) \\ ∴ & x \leq n < x + 1 \land n - 1 < x \leq n \end{array}

If $x \leq n < x + 1$ :

\begin{array}{l} x \leq n < x + 1 \Rightarrow x \leq n \Rightarrow ⌈ x ⌉ \leq n & from (c) \\ x \leq n < x + 1 \Rightarrow n - 1 < x \Rightarrow n - 1 < ⌈ x ⌉ \Rightarrow n \leq ⌈ x ⌉ & from (d) \\ ∴ & ⌈ x ⌉ \leq n \land n \leq ⌈ x ⌉ \Rightarrow ⌈ x ⌉ = n \end{array}

If $n - 1 < x \leq n$ :

\begin{array}{l} n - 1 < x \leq n \Rightarrow x \leq n \Rightarrow ⌈ x ⌉ \leq n & from (c) \\ n - 1 < x \leq n \Rightarrow n - 1 < x \Rightarrow n - 1 < ⌈ x ⌉ \Rightarrow n \leq ⌈ x ⌉ & from (d) \\ ∴ & ⌈ x ⌉ \leq n \land n \leq ⌈ x ⌉ \Rightarrow ⌈ x ⌉ = n \end{array}

Therefore, $⌈ x ⌉ = n$ if and only if $x \leq n < x + 1$ , and if and only if $n - 1 < x \leq n$ . □

▸

4. [M10] Using the previous exercise, prove that

⌊ - x ⌋ = - ⌈ x ⌉

Proposition. $⌊ - x ⌋ = - ⌈ x ⌉$ for any real number $x$ .

Proof. Let $x$ be an arbitrary real number. We must show that $⌊ - x ⌋ = - ⌈ x ⌉$ .

Given

\begin{array}{l} ⌈ x ⌉ - 1 < x \leq ⌈ x ⌉ & \Rightarrow - ⌈ x ⌉ + 1 > - x \geq - ⌈ x ⌉ \\ \Rightarrow - ⌈ x ⌉ \leq - x < - ⌈ x ⌉ + 1 \end{array}

and

\begin{array}{l} ⌈ x ⌉ - 1 < x \leq ⌈ x ⌉ & \Rightarrow x \leq ⌈ x ⌉ < x + 1 \\ \Rightarrow - x \geq - ⌈ x ⌉ > - x - 1 \\ \Rightarrow - x - 1 < - ⌈ x ⌉ \leq - x, \end{array}

by the previous exercise, we have

⌊ - x ⌋ = - ⌈ x ⌉

as we needed to show. □

5. [16] Given that

x

is a positive real number, state a simple formula that expresses

x

rounded to the nearest integer. The desired rounding rule is to produce

⌊ x ⌋

when

x mod 1 < \frac{1}{2}

, and to produce

⌈ x ⌉

when

x mod 1 \geq \frac{1}{2}

. Your answer should be a single formula that covers both cases. Discuss the rounding that would be obtained by your formula when

x

is negative.

A simple formula to express $x$ rounded to the nearest integer could be given as

round (x) = ⌊x + \frac{1}{2}⌋ .

Note that it satisﬁes the requirements, as

\begin{array}{l} round (x) & = ⌊x + \frac{1}{2}⌋ \\ = ⌊x + \frac{1}{2} + ⌊ x ⌋ - ⌊ x ⌋⌋ \\ = ⌊⌊ x ⌋ + x - ⌊ x ⌋ + \frac{1}{2}⌋ \\ = ⌊⌊ x ⌋ + x mod 1 + \frac{1}{2}⌋ \\ = ⌊ x ⌋ + ⌊x mod 1 + \frac{1}{2}⌋ \\ = \{\begin{matrix} ⌊ x ⌋ + 0 = ⌊ x ⌋ & if x mod 1 < \frac{1}{2} \\ ⌊ x ⌋ + 1 = ⌈ x ⌉ & if x mod 1 \geq \frac{1}{2} . \end{matrix} \end{array}

(Note that $x mod 1 \geq \frac{1}{2}$ implies $x$ is not an integer, otherwise $x mod 1 = 0$ .)

For negative values of $x$ , we ﬁnd that (in general), $round (- x) = - round (x)$ except when $x mod 1 = \frac{1}{2}$ , in which case $x$ is rounded away from zero if positive, towards zero if negative.

▸

6. [20] Which of the following equations are true for all positive real numbers

x

? (a)

⌊\sqrt{⌊ x ⌋}⌋ = ⌊\sqrt{x}⌋

; (b)

⌈\sqrt{⌈ x ⌉}⌉ = ⌈\sqrt{x}⌉

; (c)

⌈\sqrt{⌊ x ⌋}⌉ = ⌈\sqrt{x}⌉

Some, but not all, of the equations are true.

(a)

⌊\sqrt{⌊ x ⌋}⌋ = ⌊\sqrt{x}⌋

is true, since for an arbitrary integer

n

\begin{array}{l} ⌊\sqrt{x}⌋ = n & \Rightarrow n \leq \sqrt{x} < n + 1 \\ \Rightarrow n^{2} \leq x < {(n + 1)}^{2} \\ \Rightarrow n^{2} \leq ⌊ x ⌋ < {(n + 1)}^{2} \\ \Rightarrow n \leq \sqrt{⌊ x ⌋} < n + 1 \\ \Rightarrow ⌊\sqrt{⌊ x ⌋}⌋ = n . \end{array}

(b)

⌈\sqrt{⌈ x ⌉}⌉ = ⌈\sqrt{x}⌉

is true, since for an arbitrary integer

n

\begin{array}{l} ⌈\sqrt{x}⌉ = n & \Rightarrow n < \sqrt{x} \leq n + 1 \\ \Rightarrow n^{2} < x \leq {(n + 1)}^{2} \\ \Rightarrow n^{2} < ⌈ x ⌉ \leq {(n + 1)}^{2} \\ \Rightarrow n \leq \sqrt{⌈ x ⌉} < n + 1 \\ \Rightarrow ⌈\sqrt{⌈ x ⌉}⌉ = n . \end{array}

(c)

⌈\sqrt{⌊ x ⌋}⌉ = ⌈\sqrt{x}⌉

is not true, as can be demonstrated by counterexample. Consider

x = \frac{9}{4}

. Then

⌈\sqrt{⌊\frac{9}{4}⌋}⌉ = ⌈\sqrt{1}⌉ = ⌈1⌉ = 1

but

⌈\sqrt{\frac{9}{4}}⌉ = ⌈\frac{3}{2}⌉ = 2 .

7. [M15] Show that

⌊ x ⌋ + ⌊ y ⌋ \leq ⌊ x + y ⌋

and that equality holds if and only if

x mod 1 + y mod 1 < 1

. Does a smiliar formula hold for ceilings?

We may prove the proposition.

Proposition. $⌊ x ⌋ + ⌊ y ⌋ \leq ⌊ x + y ⌋$ and equality holds if and only if $x mod 1 + y mod 1 < 1$ .

Proof. Let $x$ and $y$ be arbitrary real numbers. We must show that

⌊ x ⌋ + ⌊ y ⌋ \leq ⌊ x + y ⌋

and that equality holds if and only if $x mod 1 + y mod 1 < 1$ .

But

\begin{array}{l} ⌊ x + y ⌋ & = ⌊⌊ x ⌋ + x mod 1 + ⌊ y ⌋ + y mod 1⌋ \\ = ⌊ x ⌋ + ⌊ y ⌋ + ⌊ x mod 1 + y mod 1 ⌋ \\ = \{\begin{matrix} ⌊ x ⌋ + ⌊ y ⌋ & if x mod 1 + y mod 1 < 1 \\ ⌊ x ⌋ + ⌊ y ⌋ + 1 & otherwise. \end{matrix} \end{array}

That is, $⌊ x ⌋ + ⌊ y ⌋ \leq ⌊ x + y ⌋$ and equality holds if and only if $x mod 1 + y mod 1 < 1$ , as we needed to show. □

A similar formula holds for ceilings. In particular

⌈ x + y ⌉ \leq ⌈ x ⌉ + ⌈ y ⌉

with equality if and only if $(- x) mod 1 + (- y) mod 1 < 1$ since

\begin{array}{l} ⌈ x + y ⌉ & = - ⌊ - x - y ⌋ \\ = - ⌊⌊ - x ⌋ + (- x) mod 1 + ⌊ - y ⌋ + (- y) mod 1⌋ \\ = - ⌊- x ⌋ - ⌊ - y ⌋ - ⌊ (- x) mod 1 + (- y) mod 1⌋ \\ = \{\begin{matrix} ⌈ x ⌉ + ⌈ y ⌉ & if (- x) mod 1 + (- y) mod 1 < 1 \\ ⌈ x ⌉ + ⌈ y ⌉ - 1 & otherwise. \end{matrix} \end{array}

Note that if $x$ and $y$ are not integers,

\begin{array}{l} (- x) mod 1 + (- y) mod 1 < 1 & \Leftrightarrow - x - ⌊ - x ⌋ + - y - ⌊ - y ⌋ < 1 \\ \Leftrightarrow - x + ⌈ x ⌉ + - y + ⌈ y ⌉ < 1 \\ \Leftrightarrow - x + ⌊ x ⌋ + 1 + - y + ⌊ y ⌋ + 1 < 1 \\ \Leftrightarrow x + - ⌊ x ⌋ - 1 + y - ⌊ y ⌋ - 1 > - 1 \\ \Leftrightarrow x mod 1 + y mod 1 - 2 > - 1 \\ \Leftrightarrow x mod 1 + y mod 1 > 1 . \end{array}

We have:

\begin{array}{l} 100 mod 3 & = 1 & since 1 = 100 - 33 (3) \\ 100 mod 7 & = 2 & since 2 = 100 - 14 (7) \\ - 100 mod 7 & = 5 & since 5 = - 100 - 7 ⌊ - 100 ∕ 7 ⌋ = - 100 + 7 (15) \\ - 100 mod 0 & = - 100 . \end{array}

We have:

\begin{array}{l} 5 mod - 3 & = - 1 & since - 1 = 5 - (- 3) ⌊ - 5 ∕ 3 ⌋ = 5 - 3 (2) \\ 18 mod - 3 & = 0 & since 0 = 18 - (- 3) ⌊ - 18 ∕ 3 ⌋ = 18 - 3 (6) \\ - 2 mod - 3 & = - 2 & since - 2 = - 2 - (- 3) ⌊ 2 ∕ 3 ⌋ = - 2 + 3 (0) . \end{array}

We have:

\begin{array}{l} 1.1 mod 1 & = 0.1 & since 0.1 = 1.1 - 1 ⌊ 1.1 ∕ 1 ⌋ \\ 0.11 mod 0.1 & = 0.01 & since 0.01 = 0.11 - 0.1 ⌊ 0.11 ∕ 0.1 ⌋ \\ 0.11 mod - 0.1 & = - 0.09 & since 0.09 = 0.11 + 0.1 ⌊ - 0.11 ∕ 0.1 ⌋ = 0.11 - 0.1 (2) . \end{array}

“ $x \equiv y (\mod 0)$ ” means $x = y$ , since $x \equiv y (\mod 0)$ is equivalent to asserting $x mod 0 = x = y = y mod 0$ .

All integers are relatively prime to $1$ since for any integer $n$ , $\gcd (n, 1) = 1$ .

13. [M00] By convention, we say that the greatest common divisor of

0

and

n

| n |

. What integers are relatively prime to

0

Given that $\gcd (0, n) = | n |$ for any integer $n$ , then only $- 1$ and $1$ are relatively prime to $0$ .

We have:

\begin{array}{l} x \equiv 2 (\mod 3) \land x \equiv 3 (\mod 5) \\ \Leftrightarrow 5 x \equiv 10 (\mod 15) \land 3 x \equiv 9 (\mod 15) & by Law C \\ \Leftrightarrow (5 - 3) x \equiv (10 - 9) (\mod 15) & by Law A \\ \Leftrightarrow (3 - 2) x \equiv (9 - 1) (\mod 15) & by Law A \\ \Leftrightarrow x \equiv 8 (\mod 15) . \end{array}

15. [10] Prove that

z (x mod y) = (z x) mod (z y)

. [Law C is an immediate consequence of this distributive law.]

Proposition. $z (x mod y) = (z x) mod (z y)$ , $z \neq 0$ .

Proof. Let $x$ , $y$ , and $z$ be arbitrary real numbers, $z \neq 0$ . We must show that

z (x mod y) = (z x) mod (z y) .

But

x mod y = x - y ⌊\frac{x}{y}⌋

if and only if

\begin{array}{l} z (x mod y) & = z (x - y ⌊\frac{x}{y}⌋) \\ = z x - z y ⌊\frac{x}{y}⌋ \\ = z x - z y ⌊\frac{z x}{z y}⌋ \\ = (z x) mod (z y) \end{array}

as we needed to show. □

16. [M10] Assume that

y > 0

. Show that if

(x - z) ∕ y

is an integer and if

0 \leq z < y

, then

z = x mod y

Proposition. if $y | (x - z)$ and $0 \leq z < y$ , then $z = x mod y$ .

Proof. Let $x$ , $y$ , and $z$ be arbitrary integers such that $y | (x - z)$ and $0 \leq z < y$ . We must show that $z = x mod y$ .

But

\begin{array}{l} x mod y & = x - y ⌊\frac{x}{y}⌋ \\ = x - y ⌊\frac{x + z - z}{y}⌋ \\ = x - y ⌊\frac{x - z}{y} + \frac{z}{y}⌋ \\ = x - y (\frac{x - z}{y} + ⌊\frac{z}{y}⌋) & since y | (x - z) \\ = x - y (\frac{x - z}{y} + 0) & since 0 \leq z < y \\ = x - y \frac{x - z}{y} \\ = x - x + z \\ = z \end{array}

as we needed to show. □

17. [M15] Prove Law A directly from the deﬁnition of congruence, and also prove half of Law D: If

a \equiv b (modulo r s)

, then

a \equiv b (modulo r)

and

a \equiv b (modulo s)

. (Here

r

and

s

are arbitrary integers.)

We may prove Law A.

Proposition. If $a \equiv b$ and $x \equiv y$ , then $a \pm x \equiv b \pm y$ and $a x \equiv b y (\mod m)$ .

Proof. Let $a$ , $b$ , $x$ , $y$ , and $m$ be arbitrary integers so that $a \equiv b$ and $x \equiv y$ . We must show that $a \pm x \equiv b \pm y$ and $a x \equiv b y (\mod m)$ .

For some integer $r$ and $s$ , we have

a = b + m r \land x = y + m s .

In the case of addition, $a + x \equiv b + y (\mod m)$ since

\begin{array}{l} a + x & = b + m r + y + m s \\ = b + y + m (r + s) \end{array}

for some integer $r + s$ .

Similarly, in the case of subtraction, $a - x \equiv b - y (\mod m)$ since

\begin{array}{l} a - x & = b + m r - y - m s \\ = b - y + m (r - s) \end{array}

for some integer $r - s$ .

In the case of multiplication, $a x \equiv b y (\mod m)$ since

\begin{array}{l} a x & = (b + m r) (y - m s) \\ = b y + y m r - b m s - m^{2} r s \\ = b y + m (y r - b s - m r s) \end{array}

for some integer $y r - b s - m r s$ .

Therefore, if $a \equiv b$ and $x \equiv y$ , then $a \pm x \equiv b \pm y$ and $a x \equiv b y (\mod m)$ as we needed to show. □

We may also prove half of Law D, which doesn’t require the assumption that $r ⊥ s$ .

Proposition. If $a \equiv b (\mod r s)$ , then $a \equiv b (\mod r)$ and $a \equiv b (\mod s)$ .

Proof. Let $a$ , $b$ , $r$ , and $s$ be arbitrary integers so that $a \equiv b (\mod r s)$ . We must show that $a \equiv b (\mod r)$ and $a \equiv b (\mod s)$ .

But

a = b + r s t

for some integer $t$ , in which case we have that $a = b + r u$ and $a = b + s v$ for integers $u = s t$ and $v = r t$ .

Therefore, if $a \equiv b (\mod r s)$ , then $a \equiv b (\mod r)$ and $a \equiv b (\mod s)$ . □

18. [M15] Using Law B, prove the other half of Law D: If

a \equiv b (modulo r)

and

a \equiv b (modulo s)

, then

a \equiv b (modulo r s)

, provided that

r ⊥ s

Proposition. If $a \equiv b (\mod r)$ and $a \equiv b (\mod s)$ , then $a \equiv b (\mod r s)$ , provided $r ⊥ s$ .

Proof. Let $a$ , $b$ , $r$ , and $s$ be arbitrary integers so that $a \equiv b (\mod r)$ and $a \equiv b (\mod s)$ , with $r ⊥ s$ . We must show that $a \equiv b (\mod r s)$ .

But

a \equiv b (\mod r),

or equivalently, $a = b + r u$ for some integer $u$ . We also necessarily have that $r u = s v = 0 + s v$ for some integer $v$ , or equivalently, that

r u \equiv 0 (\mod s)

since

\begin{array}{l} a = b + r u \land a = b + s v & \Leftrightarrow a - a = (b + r u) - (b - s v) \\ \Leftrightarrow 0 = r u - s v \\ \Leftrightarrow r u = s v . \end{array}

By Law B, since $r ⊥ s$ ,

u \equiv 0 (\mod s),

or equivalently, $u = 0 + s v^{'} = s v^{'}$ for some integer $v^{'}$ . Substituting $s v^{'}$ for $u$ gives us that $a = b + r s v^{'}$ , or equivalently, that

a \equiv b (\mod r s) .

Therefore, if $a \equiv b (\mod r)$ and $a \equiv b (\mod s)$ , then $a \equiv b (\mod r s)$ , provided $r ⊥ s$ . □

▸

19. [M10] (Law of inverses.) If

n ⊥ m

, there is an integer

n^{'}

such that

n n^{'} \equiv 1 (modulo m)

. Prove this, using the extension of Euclid’s algorithm (Algorithm 1.2.1E).

Proposition. If $n ⊥ m$ , there is an integer $n^{'}$ such that $n n^{'} \equiv 1 (\mod m)$ .

Proof. Let $n$ and $m$ be arbitrary integers such that $n ⊥ m$ . We must show that there exists an integer $n^{'}$ such that $n n^{'} \equiv 1 (\mod m)$ .

Let $d$ be the greatest common divisor of $m$ and $n$ as computed by Algorithm 1.2.1E. Then there exists two other integers $m^{'}$ and $n^{'}$ such that

m^{'} m + n^{'} n = d .

Since $n ⊥ m$ , we must have that $d = 1$ , and so, $n n^{'} = 1 + m (- m^{'})$ , or equivalently,

n n^{'} \equiv 1 (\mod m)

as we needed to show. □

Proposition. If $a x \equiv b y$ and $a \equiv b$ , and if $a ⊥ m$ , then $x \equiv y (\mod m)$ .

Proof. Let $a$ , $b$ , $x$ , $y$ , and $m$ be arbitrary integers such that $a x \equiv b y$ , $a \equiv b$ , and $a ⊥ m$ $(\mod m)$ . We must show that $x \equiv y (\mod m)$ .

Since $a ⊥ m$ , by the law of inverses we know there exists an integer $a^{'}$ such that

a a^{'} \equiv 1 (\mod m) .

Since $a \equiv b$ , from Law A

a a^{'} \equiv b a^{'} \equiv 1 (\mod m) .

Finally, since $a x \equiv b y (\mod m)$ , by Law A again, multiplying the congrunce by $a^{'}$ yields

\begin{array}{l} a^{'} a x \equiv a^{'} b y & \Rightarrow x \equiv y (\mod m) \end{array}

as we needed to show. □

21. [M22] (Fundamental theorem of arithmetic.) Use Law B and exercise 1.2.1-5 to prove that every integer

n > 1

has a unique representation as a product of primes (except for the order of the factors). In other words, show that there is exactly one way to write

n = p_{1} p_{2} \dots p_{k}

where each

p_{j}

is prime and

p_{1} \leq p_{2} \leq \dots \leq p_{k}

Proposition. Every integer $n > 1$ has a unique representation as a product of primes (except for the order of the factors).

Proof. Let $n$ be an arbitrary integer such that $n > 1$ . We must show that $n$ has a unique representation as a product of primes (except for the order of the factors).

By exercise 1.2.1-5, we have that $n = \prod_{1 \leq i \leq r} p_{i}$ for some arbitrary set of primes $p_{i}$ , $1 \leq i \leq r$ . We must show that if $n = \prod_{1 \leq j \leq s} q_{j}$ for some other arbitrary set of primes $q_{j}$ , $1 \leq j \leq s$ , that in fact, $r = s$ and $p_{i} = q_{σ (i)}$ for some permutation $σ (i) = j$ .

Let us assume, however, they are not. That is, let us assume that for all $1 \leq j \leq s$ , $q_{j} \neq p_{1}$ . Since $\prod_{1 \leq i \leq r} p_{i} = \prod_{1 \leq j \leq s} q_{j}$ , we have that

\prod_{1 \leq i \leq r} p_{i} \equiv 0 (mod p_{1}) \Leftrightarrow \prod_{1 \leq j \leq s} q_{j} \equiv 0 (mod p_{1}) .

As all $p_{i}$ and $q_{j}$ are each a set of primes and $q_{j} \neq p_{1}$ , we have that $q_{j} ⊥ p_{1}$ , allowing us to apply Law B (since $q_{j} \equiv q_{j} (\mod p_{1})$ ) successively until we obtain

1 \equiv 0 (\mod p_{1}) .

But this requires $p_{1} = 1$ , and since $p_{1}$ is a prime, a condradiction. Hence, there exists a $q_{j^{'}}$ such that $q_{j^{'}} = p_{1}$ . We may factor this prime out of our equation as

n ∕ p_{1} = \prod_{2 \leq i \leq r} p_{i} = \prod_{\begin{array}{c} 1 \leq j \leq s \\ j \neq j^{'} \end{array}} q_{j} = \frac{\prod_{1 \leq j \leq s} q_{j}}{p_{1}} .

If $n$ was prime, then clearly $n = p_{1}$ and we have proven there is a unique representation for this trivial case $r = s = 1$ . Otherwise, we may prove by induction on $k = r = s$ that this is so. That is, if we assume that

n_{k} = \prod_{1 \leq i \leq k} p_{i} = \prod_{1 \leq i \leq k} q_{σ (i)}

is a unique factorization, we must show that

n_{k + 1} = \prod_{1 \leq i \leq k + 1} p_{i} = \prod_{1 \leq j \leq s^{'}} q_{j} = \prod_{1 \leq i \leq k + 1} q_{σ^{'} (i)}

is too for some integer $s^{'} = k + 1$ . But we can make a similar proof by contradiction, assuming that for all $1 \leq j \leq s$ , $q_{j} \neq p_{k + 1}$ . Since $\prod_{1 \leq i \leq r} p_{i} = \prod_{1 \leq j \leq s} q_{j}$ , we have that

\prod_{1 \leq i \leq r} p_{i} \equiv 0 (mod p_{k + 1}) \Leftrightarrow \prod_{1 \leq j \leq s} q_{j} \equiv 0 (mod p_{k + 1}) .

As all $p_{i}$ and $q_{j}$ are each a set of primes and $q_{j} \neq p_{k + 1}$ , we have that $q_{j} ⊥ p_{k + 1}$ , allowing us to apply Law B (since $q_{j} \equiv q_{j} (\mod p_{k + 1})$ ) successively until we obtain

1 \equiv 0 (\mod p_{k + 1}) .

But this requires $p_{k + 1} = 1$ , and since $p_{k + 1}$ is a prime, a condradiction. Hence, there exists a $q_{j^{'}}$ such that $q_{j^{'}} = p_{k + 1}$ . Then

\begin{array}{l} n_{k + 1} & = \prod_{1 \leq i \leq k + 1} p_{i} \\ = p_{k + 1} \prod_{1 \leq i \leq k} p_{i} \\ = p_{k + 1} \prod_{1 \leq i \leq k} q_{σ (i)} \\ = q_{j^{'}} \prod_{1 \leq i \leq k} q_{σ (i)} \\ = \prod_{1 \leq i \leq k + 1} q_{σ^{'} (i)} . \end{array}

for

σ^{'} (i) = \{\begin{matrix} σ (i) & if 1 \leq i \leq k \\ j^{'} & if i = k + 1 . \end{matrix}

We necessarily have $s^{'} = k + 1$ , as both $p_{k + 1}$ and $q_{j}^{'}$ are primes and may not be further factored (leading to the inequalities $s^{'} < k + 1$ and $s^{'} > k + 1$ , respectively, if they were not). Hence the result as we needed to show. □

▸

22. [M10] Give an example to show that Law B is not always true if

a

is not relatively prime to

m

An example to show that Law B is not always true if $a$ is not relatively prime to $m$ is for $a = 2$ , $b = 0$ , $x = 1$ , $y = 0$ , and $m = 2$ so that $a = 2 ⊥̸ 2 = m$ . Then

\begin{matrix} 2 (1) \equiv 0 (0) (\mod 2), \\ 2 \equiv 0 (\mod 2) \end{matrix}

but

1 ≢ 0 (\mod 2) .

23. [M10] Give an example to show that Law D is not always true if

r

is not relatively prime to

s

An example to show that Law D is not always true if $r$ is not relatively prime to $s$ is for $a = r = s = 2$ and $b = 0$ so that $r = 2 ⊥̸ 2 = s$ . Then

\begin{matrix} 2 \equiv 0 (\mod 2), \\ 2 \equiv 0 (\mod 2) \end{matrix}

but

2 ≢ 0 (\mod 2 (2)) .

▸

24. [M20] To what extent can Laws A, B, C, and D be generalized to apply to arbitrary real numbers instead of integers?

We have that Law A for addition and subtraction hold, as well as Law C.

We may prove Law A.

Proposition. If $a \equiv b$ and $x \equiv y$ , then $a \pm x \equiv b \pm y$ and $a x \equiv b y (\mod m)$ .

Proof. Let $a$ , $b$ , $x$ , $y$ , and $m$ be arbitrary real numbers so that $a \equiv b$ and $x \equiv y$ . We must show that $a \pm x \equiv b \pm y$ .

For some integer $r$ and $s$ , we have

a = b + m r \land x = y + m s .

In the case of addition, $a + x \equiv b + y (\mod m)$ since

\begin{array}{l} a + x & = b + m r + y + m s \\ = b + y + m (r + s) \end{array}

for some integer $r + s$ .

Similarly, in the case of subtraction, $a - x \equiv b - y (\mod m)$ since

\begin{array}{l} a - x & = b + m r - y - m s \\ = b - y + m (r - s) \end{array}

for some integer $r - s$ .

Therefore, if $a \equiv b$ and $x \equiv y$ , then $a \pm x \equiv b \pm y$ and $a x \equiv b y (\mod m)$ as we needed to show. □

To see why Law A for multiplication does not hold for the real numbers, consider as an example $a = \frac{2}{3}$ , $b = - \frac{1}{3}$ , $x = \frac{3}{5}$ , $y = - \frac{2}{5}$ , and $m = 1$ . Then

\begin{matrix} \frac{2}{3} \equiv - \frac{1}{3} (\mod 1), \\ \frac{3}{5} \equiv - \frac{2}{5} (\mod 1) \end{matrix}

but

\frac{2}{5} ≢ \frac{2}{15} (\mod 1) .

To see why Law B does not hold for the real numbers, consider as an example $a = \frac{2}{3}$ , $b = - \frac{1}{3}$ , $x = \frac{3}{5}$ , $y = \frac{9}{5}$ , and $m = 1$ . Then

\begin{matrix} \frac{6}{15} \equiv - \frac{9}{15} (\mod 1), \\ \frac{2}{3} \equiv - \frac{1}{3} (\mod 1) \end{matrix}

but

\frac{3}{5} ≢ \frac{9}{5} (\mod 1) .

(Note that even the more general relation $x \equiv y (\mod \frac{m}{\gcd (a, m)}) \Leftrightarrow \frac{3}{5} \equiv \frac{9}{5} (\mod 3)$ doesn’t hold, assuming Thomae’s function so that $\gcd (\frac{2}{3}, 1) = \frac{1}{3}$ .)

We may prove Law C.

Proposition. $a \equiv b (\mod m)$ if and only if $a n \equiv b n (\mod m n)$ , when $n \neq 0$ .

Proof. Let $a$ , $b$ , $m$ , and $n$ be arbitrary real numbers such that $n \neq 0$ . We must show that $a \equiv b (\mod m)$ if and only if $a n \equiv b n (\mod m n)$ .

By exercise 15, we have that

\begin{array}{l} a \equiv b (\mod m) & \Leftrightarrow a mod m = b mod m \\ \Leftrightarrow n (a mod m) = n (b mod m) \\ \Leftrightarrow a n mod m n = b n mod m n \\ \Leftrightarrow a n \equiv b n (\mod m n) \end{array}

as we needed to show. □

To see why Law D does not hold for the real numbers, consider as an example $a = \frac{1}{2}$ , $b = - 1$ , and $r = s = \frac{3}{2}$ . Then

\begin{matrix} \frac{1}{2} \equiv - 1 (\mod \frac{3}{2}), \\ \frac{1}{2} \equiv - 1 (\mod \frac{3}{2}) \end{matrix}

but

\frac{1}{2} ≢ - 1 (\mod \frac{9}{4}) .

25. [M02] Show that, according to Theorem F,

a^{p - 1} mod p = [a is not a multiple of p]

, whenever

p

is a prime number.

Proposition. $a^{p - 1} mod p = [a ⊥ p]$ whenever $p$ is a prime number.

Proof. Let $a$ and $p$ be arbitrary integers such that $p$ is prime. We must show that $a^{p - 1} mod p = [a ⊥ p]$ .

By Theorem F, we have that $a^{p} \equiv a (\mod p)$ . In the case $a ⊥ p$ , we may apply Law B to deduce that $a^{p - 1} \equiv 1 (\mod p)$ , or equivalently, that

a^{p - 1} mod p = 1 mod p = 1 = [a ⊥ p]

since $p > 1$ .

In the case that $a ⊥̸ p$ , $a ∣ p$ , and since $p > 1$ , we have that

a^{p - 1} mod p = 0 = 0 mod p = [a ⊥ p] .

Therefore, in either case,

a^{p - 1} mod p = [a ⊥ p]

as we needed to show. □

26. [M15] Let

p

be an odd prime number, let

a

be any integer, and let

b = a^{(p - 1) ∕ 2}

. Show that

b mod p

is either

0

1

p - 1

. [Hint: Consider

(b + 1) (b - 1)

Proposition. $a^{(p - 1) ∕ 2} mod p$ is either $0$ , $1$ , or $p - 1$ .

Proof. Let $a$ and $p$ be arbitrary integers such that $p$ is prime and let $b = a^{(p - 1) ∕ 2}$ . We must show that $b mod p$ is either $0$ , $1$ , or $p - 1$ .
If $b ⊥̸ p$ , then clearly $b mod p = 0$ . Otherwise, we need only examine the case $b ⊥ p$ . By Theorem F, we have that $a^{p} \equiv a (\mod p)$ . We may apply Law B to deduce that $a^{p - 1} \equiv 1 (\mod p)$ , or equivalently by Law A, that

a^{p - 1} - 1 \equiv 0 (\mod p) .

But

\begin{array}{l} a^{p - 1} - 1 & = b^{2} - 1 \\ = (b + 1) (b - 1) \end{array}

so that

(b + 1) (b - 1) \equiv 0 (\mod p) .

By canceling out each factor, we obtain

\begin{array}{l} b + 1 \equiv 0 (\mod p) & \Leftrightarrow b \equiv - 1 (\mod p) \\ \Leftrightarrow b \equiv p - 1 (\mod p) \end{array}

and

\begin{array}{l} b - 1 \equiv 0 (\mod p) & \Leftrightarrow b \equiv 1 (\mod p) . \end{array}

Therefore, $b mod p$ is either $0$ , $1$ , or $p - 1$ as we needed to show. □

27. [M15] Given that

n

is a positive integer, let

φ (n)

be the number of values among

{0, 1, \dots, n - 1}

that are relatively prime to

n

. Thus

φ (1) = 1

φ (2) = 1

φ (3) = 2

φ (4) = 2

, etc. Show that

φ (p) = p - 1

p

is a prime number; and evaluate

φ (p^{e})

when

e

is a positive integer.

We may prove a propery of Euler’s totient function, deﬁned as

φ (n) = | {k : 1 \leq k \leq n \land k ⊥ n} | .

Proposition. $φ (p) = p - 1$ if $p$ is a prime number.

Proof. Let $p$ be an arbitrary prime number. We must show that $φ (p) = p - 1$ .

Since $p$ is a prime number, its only divisors are $1$ and $p$ . That is, $k ⊥ p$ for $1 \leq k < p$ but not for $k = p$ . And so

\begin{array}{l} φ (p) & = | {k : 1 \leq k \leq p \land k ⊥ p} | \\ = | {k : 1 \leq k \leq p - 1 \land k ⊥ p} | + | {k : k = p \land k ⊥ p} | \\ = (p - 1) + (0) \\ = p - 1 \end{array}

as we needed to show. □

We may evaluate $φ (p^{e})$ when $e$ is a positive integer by noting there are $p^{e}$ numbers in total, and of those, $p^{e - 1}$ are multiples of $p$ such that $k ⊥̸ p^{e}$ , $1 \leq k \leq p^{e}$ . (Intuitively, these are $k \in {p, 2 p, 3 p, \dots, (p^{e - 1}) p}$ .) This yields

\begin{array}{l} φ (p^{e}) & = | {k : 1 \leq k \leq p^{e} \land k ⊥ p^{e}} | \\ = | {k : 1 \leq k \leq p^{e}} | - | {k : 1 \leq k \leq p^{e} \land k ⊥̸ p^{e}} | \\ = p^{e} - p^{e - 1} \\ = p^{e - 1} (p - 1) \\ = p^{e} (1 - \frac{1}{p}) . \end{array}

▸

28. [M25] Show that the method used to prove Theorem F can be used to prove the following extension, called Euler’s theorem:

a^{φ (m)} \equiv 1 (modulo m)

, for any positive integer

m

, when

a ⊥ m

. (In particular, the number

n^{'}

in exercise 19 may be taken to be

n^{φ (m) - 1} mod m

Proposition (Euler’s theorem). $a^{φ (m)} \equiv 1 (\mod m)$ , for any integer $m > 0$ , when $a ⊥ m$ .

Proof. Let $a$ and $m$ be arbitrary integers such that $m > 0$ and $a ⊥ m$ . We must show that $a^{φ (m)} \equiv 1 (\mod m)$ .

Since $a ⊥ m$ , we have that

a \equiv 1 (\mod m) .

Let $x_{1}, x_{2}, \dots, x_{φ (m)}$ be the $φ (m)$ integers such that $x_{i} ⊥ p$ , $1 \leq i \leq φ (m)$ . For each, we have that

x_{i} \equiv x_{i} (\mod m)

and by Law A, we can multiply each to obtain

a x_{i} \equiv x_{i} (\mod m) .

Similarly, we may multiply for $1 \leq i \leq φ (m)$ to obtain

\prod_{1 \leq i \leq φ (m)} a x_{i} \equiv \prod_{1 \leq i \leq φ (m)} x_{i} (mod m)

or equivalently

a^{φ (m)} \prod_{1 \leq i \leq φ (m)} x_{i} \equiv \prod_{1 \leq i \leq φ (m)} x_{i} (mod m) .

Finally, as each $x_{i} ⊥ m$ , we may cancel out the products to obtain

a^{φ (m)} \equiv 1 (\mod m)

as we needed to show. □

29. [M22] A function

f (n)

of positive integers

n

is called multiplicative if

f (r s) = f (r) f (s)

whenever

r ⊥ s

. Show that each of the following functions is multiplicative: (a)

f (n) = n^{c}

, where

c

is any constant; (b)

f (n) = [n is not divisible by k^{2} for any integer k > 1]

; (c)

f (n) = c^{k}

, where

k

is the number of distinct primes that divide

n

; (d) the product of any two multiplicative functions.

We may prove that the various functions are multiplicative.

Proposition (A). The function $f (n) = n^{c}$ , where $c$ is any constant, is multiplicative.

Proof. Let $f$ be a function such that $f (n) = n^{c}$ , where $c$ is an arbitrary constant; and let $r$ and $s$ be arbitrary integers such that $r ⊥ s$ . We must show that $f$ is multiplicative; that is, that $f (r s) = f (r) f (s)$ . But

\begin{array}{l} f (r s) & = {(r s)}^{c} \\ = r^{c} s^{c} \\ = f (r) f (s) \end{array}

as we needed to show. □

Proposition (B). The function $f (n) = [k^{2} ∤ n]$ for any integer $k > 1$ , is multiplicative.

Proof. Let $f$ be a function such that $f (n) = [k^{2} ∤ n]$ for any integer $k > 1$ ; and let $r$ and $s$ be arbitrary integers such that $r ⊥ s$ . We must show that $f$ is multiplicative; that is, that $f (r s) = f (r) f (s)$ .

First, we have that $k^{2} ∤ n$ for any integer $k > 1$ . But we also have that $n ∤ k^{2}$ , since $k^{2}$ being a multiple of $n$ would require $n$ to be a square, a possibility precluded by the fact that $k^{2} ∤ n$ for any integer $k > 1$ . Therefore, we have the stronger condition that $n ⊥ k^{2}$ .

Then

\begin{array}{l} f (r s) & = [r s ⊥ k^{2}] \\ = [k^{2} \equiv 1 (\mod r s)] \\ = [k^{2} \equiv 1 (\mod r) \land k^{2} \equiv 1 (\mod s)] & by Law D \\ = [k^{2} \equiv 1 (\mod r)] [k^{2} \equiv 1 (\mod s)] \\ = [r ⊥ k^{2}] [s ⊥ k^{2}] \\ = f (r) f (s) \end{array}

as we needed to show. □

Proposition (C). The function $f (n) = c^{k}$ , where $c$ is any constant and $k$ is the number of distinct primes that divide $n$ , is multiplicative.

Proof. Let $f$ be a function such that $f (n) = c^{k}$ , where $c$ is any constant and $k$ is the number of distinct primes that divide $n$ ; and let $r$ and $s$ be arbitrary integers such that $r ⊥ s$ . We must show that $f$ is multiplicative; that is, that $f (r s) = f (r) f (s)$ .

Let $k_{n}$ denote the number of distinct primes that divide $n$ . Since $r ⊥ s$ , the prime factors of $r$ must be distinct from the prime factors of $s$ , and so we must that have $k_{r s} = k_{r} + k_{s}$ .

Then,

\begin{array}{l} f (r s) & = c_{r s}^{k} \\ = c^{k_{r} + k_{s}} \\ = c^{k_{r}} c^{k_{s}} \\ = f (r) f (s) \end{array}

as we needed to show. □

Proposition (D). The function $f (n) = g (n) h (n)$ , where $g$ and $h$ are multiplicative functions, is multiplicative.

Proof. Let $f$ be a function such that $f (n) = g (n) h (n)$ , where $g$ and $h$ are multiplicative functions; and let $r$ and $s$ be arbitrary integers such that $r ⊥ s$ . We must show that $f$ is multiplicative; that is, that $f (r s) = f (r) f (s)$ . But

\begin{array}{l} f (r s) & = g (r s) h (r s) \\ = g (r) g (s) h (r) h (s) \\ = g (r) h (r) g (s) h (s) \\ = f (r) f (s) \end{array}

as we needed to show. □

30. [M30] Prove that the function

φ (n)

of exercise 27 is multiplicative. Using this fact, evaluate

φ (1000000)

, and give a method for evaluating

φ (n)

in a simple way once

n

has been factored into primes.

We may prove that Euler’s totient function $φ (n)$ is multiplicative.

Proposition. Euler’s totient function $φ (n)$ is multiplicative.

Proof. Let

φ (n) = | {k : 1 \leq k \leq n \land k ⊥ n} |

be Euler’s totient function; and $r$ and $s$ arbtrary integers such that $r ⊥ s$ . We must show that $φ (r s) = φ (r) φ (s)$ .

Let $R = {r_{1}, r_{2}, \dots, r_{φ (r)}}$ be those integers such that $r_{k} ⊥ r$ , $1 \leq k \leq r$ ; and $S = {s_{1}, s_{2}, \dots, s_{φ (s)}}$ be those integers such that $s_{k} ⊥ s$ , $1 \leq k \leq s$ ; and deﬁne

T = {t_{i} = r s^{'} + s r^{'} : r^{'} \in R \land s^{'} \in S} .

$T$ has the following properties:

1.: $t_{i} ⊥ r s$ . Suppose not. That is, suppose that $\gcd (r s^{'} + s r^{'}, r s) > 1$ had a prime divisor $p$ . Then, without loss of generality, $p$ divides both $r$ and not $s$ (since $r ⊥ s$ ) and $r^{'}$ . But $r^{'} ⊥ r$ , so $p = 1$ , which is a contradiction, similarly for the case $p$ divides $s$ and not $r$ , and so, $t_{i} ⊥ r s$ .
2.: $t_{i} ≢ t_{j} (\mod r s)$ . Suppose $r s^{'} + s r^{'} \equiv r s^{″} + s r^{″} (\mod r s)$ . Then $r s$ divides $r (s^{'} - s^{″}) + s (r^{'} - r^{″})$ and $s$ divides $r (s^{'} - s^{″})$ . But $r ⊥ s$ , so $s$ divides $s^{'} - s^{″}$ , or equivalently, $s^{'} \equiv s^{″} (\mod s)$ . As $s^{'}$ and $s^{″}$ are both relatively prime and less than $s$ , $s^{'} = s^{″}$ . Similarly for $r s$ dividing $s (r^{'} - r^{″})$ to discover $r^{'} = r^{″}$ . And so, no two $t_{i} ≢ t_{j} (\mod r s)$ .
3.: $(\forall n ⊥ r s) (\exists t_{i}) (n \equiv t_{i} (\mod r s))$ . Suppose $n ⊥ r s$ . Since $r ⊥ s$ , $n$ can be expressed as $n = r v + s u$ for arbitrary integers $u$ and $v$ . We have $u ⊥̸ r$ and $v ⊥̸ s$ since $r v + s u ⊥ r s$ and $r ⊥ s$ . Expressing $u$ as $u = r^{'} + r a$ and $v$ as $v = s^{'} + s b$ for arbitrary integers $a$ and $b$ , we have $n = r v + s u = r (s^{'} + s b) + s (r^{'} + r a) = r s^{'} + r s b + s r^{'} + s r a = r s^{'} + s r^{'} + r s (a + b)$ , or equivalently, $n \equiv t_{i} (\mod r s)$ .

Since each $t_{i} ⊥ r s$ , no two $t_{i} ≢ t_{j} (\mod r s)$ , and for any integer $n ⊥ r s$ there is a $t_{i}$ such that $n \equiv t_{i} (\mod r s)$ , $i \neq j$ ; we have that $T = {t_{1}, t_{2}, \dots, t_{φ (r s)}}$ , those integers such that $t_{k} ⊥ r s$ , $1 \leq k \leq r s$ ; and that $φ (r s) = | R | | S | = φ (r) φ (s)$ .

Then

\begin{array}{l} φ (r s) & = φ (r) φ (s) \end{array}

as we needed to show. □

We can use this fact and the result of exercise 27, that $φ (p^{e}) = p^{e} - p^{e - 1}$ for any prime $p$ , to evaluate $φ (1000000)$ as

\begin{array}{l} φ (1000000) & = φ ((2^{6}) (5^{6})) \\ = φ (2^{6}) φ (5^{6}) \\ = (2^{6} - 2^{5}) (5^{6} - 5^{5}) \\ = (32) (12500) \\ = 400000 . \end{array}

A method for evaluating $φ (z)$ in a simple way once $z$ has been factored into $n$ primes $p_{i}$ raised to powers $w_{i}$ as $\prod_{1 \leq i \leq n} p_{i}^{w_{i}}$ is

\begin{array}{l} φ (z) & = \prod_{1 \leq i \leq n} φ (p_{i}^{w_{i}}) \\ = \prod_{1 \leq i \leq n} p_{i}^{w_{i}} - p_{i}^{w_{i} - 1} \\ = (\prod_{1 \leq i \leq n} p_{i}^{w_{i}}) (\prod_{1 \leq i \leq n} 1 - \frac{1}{p_{i}}) \\ = z \prod_{\begin{array}{c} p | z \\ p prime \end{array}} 1 - \frac{1}{p} . \end{array}

31. [M22] Prove that if

f (n)

is multiplicative, so is

g (n) = \sum_{d ∖ n} f (d)

Proposition. If $f (n)$ is multiplicative, so is $g (n) = \sum_{d ∖ n} f (d)$ .

Proof. Let $f (n)$ be a multiplicative function; $g (n) = \sum_{d | n} f (d)$ ; and $r$ and $s$ arbitrary integers such that $r ⊥ s$ . We must show that $g (r s) = g (r) g (s)$ . But since $r ⊥ s$ , the divisors $d$ of $r s$ may be partitioned into those that divide $r$ and those that divide $s$ ; let these be denoted $a$ and $b$ such that $a | r$ and $b | s$ . Then, as $a ⊥ b$ since $\gcd (r, s) = \gcd (a, s) = \gcd (a, b) = 1$ ,

\begin{array}{l} g (r s) & = \sum_{d | r s} f (d) \\ = \sum_{\begin{array}{c} a | r \\ b | s \end{array}} f (a b) \\ = \sum_{\begin{array}{c} a | r \\ b | s \end{array}} f (a) f (b) \\ = (\sum_{a | r} f (a)) (\sum_{b | s} f (b)) \\ = g (r) g (s) . \end{array}

□

Proposition. $\sum_{d | n} \sum_{c | d} f (c, d) = \sum_{c | n} \sum_{d | (n ∕ c)} f (c, c d)$ .

Proof. Let $f (a, b)$ be an arbitrary function. We must show that

\sum_{d | n} \sum_{c | d} f (c, d) = \sum_{c | n} \sum_{d | (n ∕ c)} f (c, c d) .

But, since $n = c d^{'} k$ if and only if $n = c k^{'} \land n ∕ c = d^{'} k$ for arbitrary integers $k$ and $k^{'}$ ,

\begin{array}{l} \sum_{d | n} \sum_{c | d} f (c, d) & = \sum_{d | n \land c | d} f (c, d) \\ = \sum_{c d^{'} | n \land c | c d^{'}} f (c, c d^{'}) & let d = c d^{'} \\ = \sum_{c d^{'} | n} f (c, c d^{'}) \\ = \sum_{c d^{'} | n \land c d^{'} | n} f (c, c d^{'}) \\ = \sum_{c | n \land d^{'} | (n ∕ c)} f (c, c d^{'}) \\ = \sum_{c | n} \sum_{d^{'} | (n ∕ c)} f (c, c d^{'}) \\ = \sum_{c | n} \sum_{d | (n ∕ c)} f (c, c d) \end{array}

as we needed to show. □

33. [M18] Given that

m

and

n

are integers, evaluate (a)

⌊ \frac{1}{2} (n + m) ⌋ + ⌊ \frac{1}{2} (n - m + 1) ⌋

; (b)

⌈ \frac{1}{2} (n + m) ⌉ + ⌈ \frac{1}{2} (n - m + 1) ⌉

. (The special case

m = 0

is worth noting.)

We may evaluate the equations.

(a)

We want to evalute

⌊\frac{1}{2} (n + m)⌋ + ⌊\frac{1}{2} (n - m + 1)⌋ .

We consider two cases, depending on whether $n \pm m$ is odd or even.

Case 1. [ $n \pm m$ odd] In the case that $n \pm m$ is odd,

\begin{array}{l} ⌊\frac{1}{2} (n + m)⌋ + ⌊\frac{1}{2} (n - m + 1)⌋ & = \frac{n + m - 1}{2} + \frac{n - m + 1}{2} \\ = \frac{n + m - 1 + n - m + 1}{2} \\ = \frac{2 n}{2} \\ = n . \end{array}

Case 2. [ $n \pm m$ even] In the case that $n \pm m$ is even,

\begin{array}{l} ⌊\frac{1}{2} (n + m)⌋ + ⌊\frac{1}{2} (n - m + 1)⌋ & = \frac{n + m}{2} + \frac{n - m}{2} \\ = \frac{n + m + n - m}{2} \\ = \frac{2 n}{2} \\ = n . \end{array}

In either case, we have

⌊\frac{1}{2} (n + m)⌋ + ⌊\frac{1}{2} (n - m + 1)⌋ = n .

(b)

We want to evaluate

⌈\frac{1}{2} (n + m)⌉ + ⌈\frac{1}{2} (n - m + 1)⌉ .

We consider two cases, depending on whether $n \pm m$ is odd or even.

Case 1. [ $n \pm m$ odd] In the case that $n \pm m$ is odd,

\begin{array}{l} ⌈\frac{1}{2} (n + m)⌉ + ⌈\frac{1}{2} (n - m + 1)⌉ & = \frac{n + m + 1}{2} + \frac{n - m + 1}{2} \\ = \frac{n + m + 1 + n - m + 1}{2} \\ = \frac{2 n + 2}{2} \\ = n + 1 . \end{array}

Case 2. [ $n \pm m$ even] In the case that $n \pm m$ is even,

\begin{array}{l} ⌈\frac{1}{2} (n + m)⌉ + ⌈\frac{1}{2} (n - m + 1)⌉ & = \frac{n + m}{2} + \frac{n - m + 2}{2} \\ = \frac{n + m + n - m + 2}{2} \\ = \frac{2 n + 2}{2} \\ = n + 1 . \end{array}

In either case, we have

⌈\frac{1}{2} (n + m)⌉ + ⌈\frac{1}{2} (n - m + 1)⌉ = n + 1 .

The special case $m = 0$ yields

⌊\frac{n}{2}⌋ + ⌊\frac{n + 1}{2}⌋ = n

and

⌈\frac{n}{2}⌉ + ⌈\frac{n + 1}{2}⌉ = n + 1 .

▸

34. [M21] What conditions on the real number

b > 1

are necessary and suﬃcient to guarantee that

⌊ \log_{b} x ⌋ = ⌊ \log_{b} ⌊ x ⌋ ⌋

for all real

x \geq 1

For real numbers $x \geq 1$ and $b > 1$ we have for some arbitrary integer $n$ that

\begin{array}{l} ⌊\log_{b} x⌋ = n & \Leftrightarrow n \leq \log_{b} x < n + 1 \\ \Leftrightarrow b^{n} \leq x < b^{n + 1} \\ \Leftrightarrow b^{n} \leq ⌊x⌋ < b^{n + 1} & b \in ℤ \\ \Leftrightarrow n \leq \log_{b} ⌊x⌋ < n + 1 \\ \Leftrightarrow ⌊\log_{b} ⌊x⌋⌋ = n . \end{array}

That is, $b$ an integer such that $b \geq 2$ are necessary and suﬃcient conditions to guarantee that

⌊ \log_{b} x ⌋ = ⌊ \log_{b} ⌊ x ⌋ ⌋

for all real $x \geq 1$ .

Note that we have the same conditions for ceilings, as

\begin{array}{l} ⌈\log_{b} x⌉ = n & \Leftrightarrow n < \log_{b} x \leq n + 1 \\ \Leftrightarrow b^{n} < x \leq b^{n + 1} \\ \Leftrightarrow b^{n} < ⌈x⌉ \leq b^{n + 1} & b \in ℤ \\ \Leftrightarrow n < \log_{b} ⌈x⌉ \leq n + 1 \\ \Leftrightarrow ⌈\log_{b} ⌈x⌉⌉ = n . \end{array}

for all real

x

. (When

m = 0

, we have an important special case.) Does an analogous result hold for the ceiling function?

We may prove the result for ﬂoors.

Proposition. $⌊ (x + m) ∕ n ⌋ = ⌊ (⌊ x ⌋ + m) ∕ n ⌋$ for integers $m$ , $n$ , $n > 0$ and real $x$ .

Proof. Let $m$ and $n$ be arbitrary integers such that $n > 0$ , and $x$ an arbitrary real number. We must show that

⌊ (x + m) ∕ n ⌋ = ⌊ (⌊ x ⌋ + m) ∕ n ⌋ .

But for an arbitary integer $z$

\begin{array}{l} ⌊ (x + m) ∕ n ⌋ = z & \Leftrightarrow z \leq (x + m) ∕ n < z + 1 \\ \Leftrightarrow n z \leq (x + m) < n (z + 1) \\ \Leftrightarrow n z - m \leq x < n (z + 1) - m \\ \Leftrightarrow n z - m \leq ⌊ x ⌋ < n (z + 1) - m \\ \Leftrightarrow n z \leq ⌊ x ⌋ + m < n (z + 1) \\ \Leftrightarrow z \leq (⌊ x ⌋ + m) ∕ n < z + 1 \\ \Leftrightarrow ⌊(⌊ x ⌋ + m) ∕ n⌋ = z \end{array}

as we needed to show. □

Note the important special case for $m = 0$ ,

⌊ x ∕ n ⌋ = ⌊ ⌊ x ⌋ ∕ n ⌋ .

An analogous result holds for ceilings.

Proposition. $⌈ (x + m) ∕ n ⌉ = ⌈ (⌈ x ⌉ + m) ∕ n ⌉$ for integers $m$ , $n$ , $n > 0$ and real $x$ .

Proof. Let $m$ and $n$ be arbitrary integers such that $n > 0$ , and $x$ an arbitrary real number. We must show that

⌈ (x + m) ∕ n ⌉ = ⌈ (⌈ x ⌉ + m) ∕ n ⌉ .

But for an arbitary integer $z$

\begin{array}{l} ⌈ (x + m) ∕ n ⌉ = z & \Leftrightarrow z < (x + m) ∕ n \leq z + 1 \\ \Leftrightarrow n z < (x + m) \leq n (z + 1) \\ \Leftrightarrow n z - m < x \leq n (z + 1) - m \\ \Leftrightarrow n z - m < ⌈ x ⌉ \leq n (z + 1) - m \\ \Leftrightarrow n z < ⌈ x ⌉ + m \leq n (z + 1) \\ \Leftrightarrow z < (⌈ x ⌉ + m) ∕ n \leq z + 1 \\ \Leftrightarrow ⌈(⌈ x ⌉ + m) ∕ n⌉ = z \end{array}

as we needed to show. □

36. [M23] Prove that

\sum_{k = 1}^{n} ⌊ k ∕ 2 ⌋ = ⌊ n^{2} ∕ 4 ⌋

; also evaulate

\sum_{k = 1}^{n} ⌈ k ∕ 2 ⌉

We may prove the sum for ﬂoors.

Proposition. $\sum_{1 \leq k \leq n} ⌊\frac{k}{2}⌋ = ⌊\frac{n^{2}}{4}⌋$ .

Proof. Let $n$ be an arbitary positive integer. We must show that

\sum_{1 \leq k \leq n} ⌊\frac{k}{2}⌋ = ⌊\frac{n^{2}}{4}⌋ .

We consider two cases, depending on whether $n = 2 m$ is even or $n = 2 m + 1$ is odd for an arbitrary integer $m$ . We also will utilize the equality

\sum_{1 \leq k \leq n} ⌊\frac{k}{2}⌋ = \sum_{1 \leq k \leq n} ⌊\frac{n + 1 - k}{2}⌋ .

Case 1. [ $n = 2 m$ ] We have the equality

⌊\frac{k}{2}⌋ + ⌊\frac{n + 1 - k}{2}⌋ = m

since for an arbitrary integer $q$ , if $k = 2 q$ is even

⌊\frac{k}{2}⌋ + ⌊\frac{n + 1 - k}{2}⌋ = ⌊\frac{2 q}{2}⌋ + ⌊\frac{2 m + 1 - 2 q}{2}⌋ = m + ⌊\frac{1}{2}⌋ = m;

and if $k = 2 q + 1$ is odd

⌊\frac{k}{2}⌋ + ⌊\frac{n + 1 - k}{2}⌋ = ⌊\frac{2 q + 1}{2}⌋ + ⌊\frac{2 m + 1 - 2 q - 1}{2}⌋ = ⌊\frac{1}{2}⌋ + m = m .

In this case then

\begin{array}{l} \sum_{1 \leq k \leq n} ⌊\frac{k}{2}⌋ & = \frac{1}{2} \sum_{1 \leq k \leq n} (⌊\frac{k}{2}⌋ + ⌊\frac{n + 1 - k}{2}⌋) \\ = \frac{1}{2} \sum_{1 \leq k \leq n} m \\ = \frac{n m}{2} \\ = \frac{n^{2}}{4} . \end{array}

Case 2. [ $n = 2 m + 1$ ] In this case,

\begin{array}{l} \sum_{1 \leq k \leq n} ⌊\frac{k}{2}⌋ & = (\sum_{1 \leq k \leq 2 m} ⌊\frac{k}{2}⌋) + ⌊\frac{n}{2}⌋ \\ = \frac{{(2 m)}^{2}}{4} + m \\ = m^{2} + m \\ \frac{n^{2}}{4} - \frac{1}{4} . \end{array}

And so, in either case,

\frac{{(n - 1)}^{2}}{4} < \frac{n^{2}}{4} - \frac{1}{4} \leq \sum_{1 \leq k \leq n} ⌊\frac{k}{2}⌋ \leq \frac{n^{2}}{4}

or equivalently,

\sum_{1 \leq k \leq n} ⌊\frac{k}{2}⌋ = ⌊\frac{n^{2}}{4}⌋

as we needed to show. □

For the second sum, we may prove another result.

Proposition. $\sum_{1 \leq k \leq n} ⌈\frac{k}{2}⌉ = ⌈\frac{n (n + 2)}{4}⌉$ .

Proof. Let $n$ be an arbitary positive integer. We must show that

\sum_{1 \leq k \leq n} ⌈\frac{k}{2}⌉ = ⌈\frac{n (n + 2)}{4}⌉ .

We consider two cases, depending on whether $n = 2 m$ is even or $n = 2 m + 1$ is odd for an arbitrary integer $m$ . We also will utilize the equality

\sum_{1 \leq k \leq n} ⌈\frac{k}{2}⌉ = \sum_{1 \leq k \leq n} ⌈\frac{n + 1 - k}{2}⌉ .

Case 1. [ $n = 2 m$ ] We have the equality

⌈\frac{k}{2}⌉ + ⌈\frac{n + 1 - k}{2}⌉ = m + 1

since for an arbitrary integer $q$ , if $k = 2 q$ is even

⌈\frac{k}{2}⌉ + ⌈\frac{n + 1 - k}{2}⌉ = ⌈\frac{2 q}{2}⌉ + ⌈\frac{2 m + 1 - 2 q}{2}⌉ = m + 1;

and if $k = 2 q + 1$ is odd

⌈\frac{k}{2}⌉ + ⌈\frac{n + 1 - k}{2}⌉ = ⌈\frac{2 q + 1}{2}⌉ + ⌈\frac{2 m + 1 - 2 q - 1}{2}⌉ = m + 1 .

In this case

\begin{array}{l} \sum_{1 \leq k \leq n} ⌈\frac{k}{2}⌉ & = \frac{1}{2} \sum_{1 \leq k \leq n} (⌈\frac{k}{2}⌉ + ⌈\frac{n + 1 - k}{2}⌉) \\ = \frac{1}{2} \sum_{1 \leq k \leq n} m + 1 \\ = \frac{n (m + 1)}{2} \\ = \frac{n ((n ∕ 2) + 1)}{2} \\ = \frac{n (n + 2)}{4} . \end{array}

Case 2. [ $n = 2 m + 1$ ] In this case

\begin{array}{l} \sum_{1 \leq k \leq n} ⌈\frac{k}{2}⌉ & = (\sum_{1 \leq k \leq 2 m} ⌈\frac{k}{2}⌉) + ⌈\frac{n}{2}⌉ \\ = \frac{2 m (2 m + 2)}{4} + m + 1 \\ = {(m + 1)}^{2} \\ \frac{{(n + 1)}^{2}}{4} . \end{array}

And so, in either case,

\frac{n (n + 2)}{4} \leq \sum_{1 \leq k \leq n} ⌈\frac{k}{2}⌉ \leq \frac{{(n + 1)}^{2}}{4} < \frac{(n + 1) (n + 3)}{4}

or equivalently,

\sum_{1 \leq k \leq n} ⌈\frac{k}{2}⌉ = ⌈\frac{n (n + 2)}{4}⌉

as we needed to show. □

where

d

is the greatest common divisor of

m

and

n

, and

x

is any real number.

We may prove the result for ﬂoors.

Proposition. $\sum_{0 \leq k < n} ⌊\frac{m k + x}{n}⌋ = \frac{(m - 1) (n - 1)}{2} + \frac{d - 1}{2} + d ⌊ x ∕ d ⌋$ for $d = \gcd (m, n)$ .

Proof. Let $m$ , $n$ , and $d$ be arbitrary integers such that $d = \gcd (m, n)$ and $x$ an arbitrary real number. We must show that

\sum_{0 \leq k < n} ⌊\frac{m k + x}{n}⌋ = \frac{(m - 1) (n - 1)}{2} + \frac{d - 1}{2} + d ⌊\frac{x}{d}⌋ .

But since for an arbitrary real $z$ , $z = ⌊ x ⌋ + x mod 1 = ⌊ x ⌋ + {x}$ ,

\begin{array}{l} \sum_{0 \leq k < n} ⌊\frac{m k + x}{n}⌋ & = \sum_{0 \leq k < n} \frac{m k + x}{n} - \sum_{0 \leq k < n} \{\frac{m k + x}{n}\} . \end{array}

We have that

\begin{array}{l} \sum_{0 \leq k < n} \frac{m k + x}{n} & = \frac{m}{n} (\sum_{0 \leq k < n} k) + \frac{1}{n} (\sum_{0 \leq k < n} x) \\ = \frac{m}{n} \frac{(n - 1) n}{2} + \frac{1}{n} n x \\ = \frac{m (n - 1)}{2} + x . \end{array}

And so

\begin{array}{l} \sum_{0 \leq k < n} ⌊\frac{m k + x}{n}⌋ & = \frac{m (n - 1)}{2} + x - \sum_{0 \leq k < n} \{\frac{m k + x}{n}\} . \end{array}

Then, for $n^{'} = n ∕ d$ and $m^{'} = m ∕ d$ , we have

\begin{array}{l} \sum_{0 \leq k < n} \{\frac{m k + x}{n}\} & = \sum_{0 \leq k < n} \{\frac{m^{'} k}{n^{'}} + \frac{x}{n}\} \\ = \sum_{0 \leq i < d} \sum_{n^{'} i \leq j < n^{'} (i + 1)} \{\frac{m^{'} j}{n^{'}} + \frac{x}{n}\} \\ = \sum_{0 \leq i < d} \sum_{0 \leq j < n^{'}} \{\frac{m^{'} (j + n^{'} i)}{n^{'}} + \frac{x}{n}\} \\ = \sum_{0 \leq i < d} \sum_{0 \leq j < n^{'}} \{\frac{m^{'} j}{n^{'}} + m^{'} i + \frac{x}{n}\} \\ = \sum_{0 \leq i < d} \sum_{0 \leq j < n^{'}} \{\frac{m^{'} j}{n^{'}} + \frac{x}{n}\} & since m^{'} i \equiv 0 (\mod 1) \\ = d \sum_{0 \leq j < n^{'}} \{\frac{m^{'} j}{n^{'}} + \frac{x}{n}\} \\ = d \sum_{0 \leq j < n^{'}} \{\frac{m^{'} j}{n^{'}} + \frac{x ∕ d}{n^{'}}\} \\ = d \sum_{0 \leq j < n^{'}} \{\frac{m^{'} j + x ∕ d}{n^{'}}\} \\ = d \sum_{0 \leq j < n^{'}} \{\frac{m^{'} j + ⌊ x ∕ d ⌋ + {x ∕ d}}{n^{'}}\} \\ = d \sum_{0 \leq j < n^{'}} \{\frac{m^{'} j}{n^{'}} + \frac{⌊ x ∕ d ⌋}{n^{'}} + \frac{{x ∕ d}}{n^{'}}\} \\ = d \sum_{0 \leq j < n^{'}} \{\frac{j}{n^{'}} + \frac{⌊ x ∕ d ⌋}{n^{'}} + \frac{{x ∕ d}}{n^{'}}\} & since m^{'} j ∕ n^{'} \equiv j ∕ n^{'} (\mod 1) \\ = d \sum_{0 \leq j < n^{'}} \{\frac{j + ⌊ x ∕ d ⌋}{n^{'}} + \frac{{x ∕ d}}{n^{'}}\} \\ = d ((\sum_{0 \leq j < n^{'}} \{\frac{j}{n^{'}} + \frac{{x ∕ d}}{n^{'}}\}) + (\sum_{0 \leq j < n^{'}} \{\frac{⌊ x ∕ d ⌋}{n^{'}}\})) \\ = d ((\sum_{0 \leq j < n^{'}} \{\frac{j}{n^{'}} + \frac{{x ∕ d}}{n^{'}}\}) + n^{'} \{\frac{⌊ x ∕ d ⌋}{n^{'}}\}) \\ = d ((\sum_{0 \leq j < n^{'}} \{\frac{j}{n^{'}} + \frac{{x ∕ d}}{n^{'}}\}) + \{⌊ x ∕ d ⌋\}) \\ = d ((\sum_{0 \leq j < n^{'}} \{\frac{j}{n^{'}} + \frac{{x ∕ d}}{n^{'}}\}) + 0) & since ⌊ x ∕ d ⌋ \equiv 0 (\mod 1) \\ = d \sum_{0 \leq j < n^{'}} \{\frac{j}{n^{'}} + \frac{{x ∕ d}}{n^{'}}\} \\ = d \sum_{0 \leq j < n^{'}} \frac{j}{n^{'}} + \frac{{x ∕ d}}{n^{'}} & since 0 \leq j + {x ∕ d} < n^{'} \\ = d \sum_{0 \leq j < n^{'}} \frac{j + {x ∕ d}}{n^{'}} \\ = d \frac{(n^{'} - 1) n^{'}}{2 n^{'}} + \frac{d n^{'}}{n^{'}} {x ∕ d} \\ = \frac{n - d}{2} + \frac{d n^{'}}{n^{'}} (x ∕ d - ⌊ x ∕ d ⌋) \\ = \frac{n - d}{2} + x - d ⌊ x ∕ d ⌋ . \end{array}

For justiﬁcations of certain steps, note that

\begin{array}{l} m^{'} \equiv 0 (\mod 1) \land i \equiv 0 (\mod 1) & \Leftrightarrow m^{'} i \equiv 0 (\mod 1); \end{array}

\begin{array}{l} m \equiv \gcd (m, n) (\mod n) & \Leftrightarrow m \equiv d (\mod n) \\ \Leftrightarrow m^{'} d \equiv d (\mod n^{'} d) \\ \Leftrightarrow m^{'} \equiv 1 (\mod n^{'}) \\ \Leftrightarrow m^{'} j \equiv j (\mod n^{'}) \\ \Leftrightarrow m^{'} j ∕ n^{'} \equiv j ∕ n^{'} (\mod 1); \end{array}

and

\begin{array}{l} 0 \leq j \leq n^{'} - 1 \land {x ∕ d} < 1 & \Leftrightarrow 0 \leq j + {x ∕ d} < n^{'} . \end{array}

And so

\begin{array}{l} \sum_{0 \leq k < n} ⌊\frac{m k + x}{n}⌋ & = \frac{m (n - 1)}{2} + x - \frac{n - d}{2} - x + d ⌊ x ∕ d ⌋ \\ = \frac{m n - m - n + d}{2} + d ⌊ x ∕ d ⌋ \\ = \frac{(m - 1) (n - 1)}{2} + \frac{d - 1}{2} + d ⌊ x ∕ d ⌋ \end{array}

as we needed to show. □

For ceilings, note that by negating both sides of the equality yields

\begin{array}{l} - \sum_{0 \leq k < n} ⌊\frac{m k + x}{n}⌋ & = \sum_{0 \leq k < n} - ⌊\frac{m k + x}{n}⌋ \\ = \sum_{0 \leq k < n} ⌈\frac{- m k - x}{n}⌉ \end{array}

and

\begin{array}{l} - (\frac{(m - 1) (n - 1)}{2} + \frac{d - 1}{2} + d ⌊ x ∕ d ⌋) & = \frac{(- m + 1) (n - 1)}{2} - \frac{d - 1}{2} - d ⌊ x ∕ d ⌋ \\ = \frac{(- m + 1) (n - 1)}{2} - \frac{d - 1}{2} + d ⌈ - x ∕ d ⌉ \end{array}

or equivalently since $x$ and $m$ are arbitrary

\sum_{0 \leq k < n} ⌈\frac{m k + x}{n}⌉ = \frac{(m + 1) (n - 1)}{2} - \frac{d - 1}{2} + d ⌈ x ∕ d ⌉ .

38. [M26] (E. Busche, 1909.) Prove that, for all real

x

and

y

with

y > 0

In particular, when

y

is a positive integer

n

, we have the important formula

Proposition. $\sum_{0 \leq k < y} ⌊x + \frac{k}{y}⌋ = ⌊ x y + ⌊ x + 1 ⌋ (⌈ y ⌉ - y) ⌋$ .

Proof. Let $x$ and $y$ be artbitrary real numbers such that $y > 0$ . We must show that

\sum_{0 \leq k < y} ⌊x + \frac{k}{y}⌋ = ⌊ x y + ⌊ x + 1 ⌋ (⌈ y ⌉ - y) ⌋ .

Let $n$ be that unique integer such that $n = ⌈ (1 - {x}) y ⌉$ so that

\begin{array}{l} n - 1 < (1 - {x}) y \leq n & \Leftrightarrow \frac{n - 1}{y} < 1 - {x} \leq \frac{n}{y} \\ \Leftrightarrow \frac{n - 1}{y} < 1 + ⌊ x ⌋ - x \leq \frac{n}{y} \\ \Leftrightarrow x + \frac{n - 1}{y} < 1 + ⌊ x ⌋ \leq x + \frac{n}{y} \\ \Leftrightarrow x + \frac{n - 1}{y} < ⌊ x + 1 ⌋ \leq x + \frac{n}{y} \\ \Leftrightarrow \frac{n - 1}{y} < ⌊ x + 1 ⌋ - x \leq \frac{n}{y} \\ \Leftrightarrow n - 1 < (⌊ x + 1 ⌋ - x) y \leq n \\ \Leftrightarrow n - 1 < ⌊ x + 1 ⌋ y - x y \leq n \end{array}

or equivalently

n = ⌈ ⌊ x + 1 ⌋ y - x y ⌉ .

Note that for $0 \leq k \leq n - 1 < n$

⌊ x ⌋ \leq x + \frac{k}{y} < ⌊ x + 1 ⌋ \Leftrightarrow ⌊x + \frac{k}{y}⌋ = ⌊ x ⌋

and that for $n \leq k \leq ⌈ y ⌉ - 1 < y$

⌊ x + 1 ⌋ \leq x + \frac{k}{y} < ⌊ x + 2 ⌋ \Leftrightarrow ⌊x + \frac{k}{y}⌋ = ⌊ x + 1 ⌋ .

Then

\begin{array}{l} \sum_{0 \leq k < y} ⌊x + \frac{k}{y}⌋ & = \sum_{0 \leq k \leq ⌈ y ⌉ - 1} ⌊x + \frac{k}{y}⌋ \\ = \sum_{0 \leq k \leq n - 1} ⌊x + \frac{k}{y}⌋ + \sum_{n \leq k \leq ⌈ y ⌉ - 1} ⌊x + \frac{k}{y}⌋ \\ = n ⌊ x ⌋ + ((⌈ y ⌉ - 1) - n + 1) ⌊ x + 1 ⌋ \\ = n ⌊ x ⌋ + (⌈ y ⌉ - n) ⌊ x + 1 ⌋ \\ = n ⌊ x ⌋ + ⌈ y ⌉ ⌊ x + 1 ⌋ - n ⌊ x + 1 ⌋ \\ = ⌈ y ⌉ ⌊ x + 1 ⌋ - n \\ = ⌊ x + 1 ⌋ ⌈ y ⌉ - ⌈ ⌊ x + 1 ⌋ y - x y ⌉ \\ = ⌊ x + 1 ⌋ ⌈ y ⌉ + ⌊ - ⌊ x + 1 ⌋ y + x y ⌋ \\ = ⌊ x y + ⌊ x + 1 ⌋ ⌈ y ⌉ - ⌊ x + 1 ⌋ y ⌋ \\ = ⌊ x y + ⌊ x + 1 ⌋ (⌈ y ⌉ - y) ⌋ \end{array}

as we needed to show. □

______________________________________________________________________________________________________________________________

[Crelle 136 (1909), 42; the case $y = n$ is due to C. Hermite, Acta Math. 5 (1884), 315.]

39. [HM35] A function

f

for which

f (x) + f (x + \frac{1}{n}) + \dots + f (x + \frac{n - 1}{n}) = f (n x)

, whenever

n

is a positive integer, is called a replicative function. The previous exercise establishes the fact that

⌊ x ⌋

is replicative. Show that the following functions are replicative:

a): $f (x) = x - \frac{1}{2}$ ;
b): $f (x) = [x is an integer]$ ;
c): $f (x) = [x is a positive integer]$ ;
d): $f (x) = [there exists a rational number r and an integer m such that x = r π + m]$ ;
e): three other functions like the one in (d), with $r$ and/or $m$ restricted to positive values;
f): $f (x) = \log | 2 \sin π x |$ , if the value $f (x) = - \infty$ is allowed;
g): the sum of any two replicative functions;
h): a constant multiple of a replicative function;
i): the function $g (x) = f (x - ⌊ x ⌋)$ , where $f (x)$ is replicative.

We may prove that numerous functions are replicative.

Proposition (A). $f (x) = x - \frac{1}{2}$ is replicative.

Proof. Let $f$ be a function deﬁned as

f (x) = x - \frac{1}{2}

and let $n$ be an arbitrary positive integer. We must show that

\sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) = f (n x) .

But

\begin{array}{l} \sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) & = \sum_{0 \leq k \leq n - 1} x + \frac{k}{n} - \frac{1}{2} \\ = \frac{1}{x} \sum_{0 \leq k \leq n - 1} 1 + \frac{1}{n} \sum_{0 \leq k \leq n - 1} k - \frac{1}{2} \sum_{0 \leq k \leq n - 1} 1 \\ = \frac{n}{x} + \frac{(n - 1) n}{2 n} - \frac{n}{2} \\ = \frac{n}{x} + \frac{n - 1}{2} - \frac{n}{2} \\ = \frac{n}{x} + \frac{n - 1 - n}{2} \\ = \frac{n}{x} - \frac{1}{2} \\ = f (n x) \end{array}

as we needed to show. □

Proposition (B). $f (x) = [x mod 1 = 0]$ is replicative.

Proof. Let $f$ be a function deﬁned as

f (x) = [x mod 1 = 0]

and let $n$ be an arbitrary positive integer. We must show that

\sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) = f (n x) .

But for some $k^{'} = n - n x mod n - 1$ , $0 \leq k^{'} \leq n - 1$ , we have

\begin{array}{l} x & = ⌊ x ⌋ + x mod 1 \\ = ⌊\frac{n x}{n}⌋ + \frac{n x mod n}{n} \\ = ⌊\frac{n x}{n}⌋ + \frac{n - k^{'} - 1}{n} \end{array}

if and only if $x - \frac{n - k^{'} - 1}{n}$ is an integer, or equivalently, if and only if $(x + \frac{k^{'}}{n}) mod 1 = 0$ . In the case that such a $k^{'}$ exists, then clearly $n ∣ x$ and $n x$ is an integer, or equivalently, $n x mod 1 = 0$ , and

\begin{array}{l} \sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) & = \sum_{0 \leq k \leq n - 1} [(x + \frac{k}{n}) mod 1 = 0] \\ \begin{aligned} = \sum_{\begin{array}{c} 0 \leq k \leq n - 1 \\ k \neq k^{'} \end{array}} [(x + \frac{k}{n}) mod 1 = 0] \\ + \sum_{\begin{array}{c} 0 \leq k \leq n - 1 \\ k = k^{'} \end{array}} [(x + \frac{k}{n}) mod 1 = 0] \end{aligned} \\ = 0 + 1 \\ = 1 \\ = [n x mod 1 = 0] \\ = f (n x) . \end{array}

In the case that such a $k^{'}$ does not exist, then clearly $n ∤ x$ and $n x$ is not an integer, or equivalently, $n x mod 1 \neq 0$ , and

\begin{array}{l} \sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) & = \sum_{0 \leq k \leq n - 1} [(x + \frac{k}{n}) mod 1 = 0] \\ = 0 \\ = [n x mod 1 = 0] \\ = f (n x) . \end{array}

In either case, we ﬁnd that

\sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) = f (n x)

as we needed to show. □

Proposition (C). $f (x) = [x mod 1 = 0 \land x > 0]$ is replicative.

Proof. Let $f$ be a function deﬁned as

f (x) = [x mod 1 = 0 \land x > 0] = [x > 0] [x mod 1 = 0]

and let $n$ be an arbitrary positive integer. We must show that

\sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) = f (n x) .

But similar to Proposition B, for some $k^{'} = n - n x mod n - 1$ , $0 \leq k^{'} \leq n - 1$ , we have

\begin{array}{l} x & = ⌊ x ⌋ + x mod 1 \\ = ⌊\frac{n x}{n}⌋ + \frac{n x mod n}{n} \\ = ⌊\frac{n x}{n}⌋ + \frac{n - k^{'} - 1}{n} \end{array}

\begin{array}{l} \sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) & = \sum_{0 \leq k \leq n - 1} [x + \frac{k}{n} > 0] [(x + \frac{k}{n}) mod 1 = 0] \\ \begin{aligned} = \sum_{\begin{array}{c} 0 \leq k \leq n - 1 \\ k \neq k^{'} \end{array}} [x + \frac{k}{n} > 0] [(x + \frac{k}{n}) mod 1 = 0] \\ + \sum_{\begin{array}{c} 0 \leq k \leq n - 1 \\ k = k^{'} \end{array}} [x + \frac{k}{n} > 0] [(x + \frac{k}{n}) mod 1 = 0] \end{aligned} \\ \begin{aligned} = \sum_{\begin{array}{c} 0 \leq k \leq n - 1 \\ k \neq k^{'} \end{array}} [x + \frac{k}{n} > 0] (0) \\ + [x + \frac{k^{'}}{n} > 0 \land (x + \frac{k}{n}) mod 1 = 0] [(x + \frac{k}{n}) mod 1 = 0] \end{aligned} \\ = 0 + [x + \frac{k^{'}}{n} > 0] [(x + \frac{k^{'}}{n}) mod 1 = 0] \\ = [x + \frac{k^{'}}{n} > 0 \land (x + \frac{k^{'}}{n}) mod 1 = 0] \\ = [x + \frac{k^{'}}{n} \geq 1 \land (x + \frac{k^{'}}{n}) mod 1 = 0] \\ = [x > 0 \land (x + \frac{k^{'}}{n}) mod 1 = 0] \\ = [n x > 0 \land (x + \frac{k^{'}}{n}) mod 1 = 0] \\ = [n x > 0] [(x + \frac{k^{'}}{n}) mod 1 = 0] \\ = [n x > 0] (1) \\ = [n x > 0] [n x mod 1 = 0] \\ = f (n x) \end{array}

since $x \leq 0$ if and only if $x + \frac{k^{'}}{n} < 1$ , and so neither it nor any multiple a positive integer such as $n x$ .

In the case that such a $k^{'}$ does not exist, then clearly $n ∤ x$ and $n x$ is not an integer, or equivalently, $n x mod 1 \neq 0$ , and

\begin{array}{l} \sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) & = \sum_{0 \leq k \leq n - 1} [x + \frac{k}{n} > 0] [(x + \frac{k}{n}) mod 1 = 0] \\ = \sum_{0 \leq k \leq n - 1} [x + \frac{k}{n} > 0] (0) \\ = 0 \\ = [n x > 0] (0) \\ = [n x > 0] [n x mod 1 = 0] \\ = f (n x) . \end{array}

In either case, we ﬁnd that

\sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) = f (n x)

as we needed to show. □

Proposition (D). $f (x) = [\exists r \in ℚ, m \in ℤ : x = r π + m]$ is replicative.

Proof. Let $f$ be a function deﬁned as

f (x) = [\exists r \in ℚ, m \in ℤ : x = r π + m]

and let $n$ be an arbitrary positive integer. We must show that

\sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) = f (n x) .

In the case that we may ﬁnd an integer $k^{'}$ such that

x + \frac{k^{'}}{n} = r π + m

it must be unique since if we found an integer $k^{″}$ such that $x + \frac{k^{″}}{n} = r^{'} π + m^{'}$ , $(r - r^{'}) π$ can only be an integer if $r = r^{'}$ and $(m - m^{'})$ can only be a rational if $m = m^{'}$ , and so $k^{'} = k^{″}$ . Then,

\begin{array}{l} x + \frac{k^{'}}{n} = r π + m & \Leftrightarrow n x + k^{'} = n r π + n m \\ \Leftrightarrow n x = n r π + n m - k^{'} \\ \Leftrightarrow n x = r^{'} π + m^{'} \end{array}

for a rational $r^{'} = n r$ and an integer $m^{'} = n m - k^{'}$ . Hence

\begin{array}{l} \sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) & = \sum_{0 \leq k \leq n - 1} [\exists r \in ℚ, m \in ℤ : x + \frac{k}{n} = r π + m] \\ \begin{aligned} = \sum_{\begin{array}{c} 0 \leq k \leq n - 1 \\ k \neq k^{'} \end{array}} [\exists r \in ℚ, m \in ℤ : x + \frac{k}{n} = r π + m] \\ + \sum_{\begin{array}{c} 0 \leq k \leq n - 1 \\ k = k^{″} \end{array}} [\exists r \in ℚ, m \in ℤ : x + \frac{k}{n} = r π + m] \end{aligned} \\ = \sum_{\begin{array}{c} 0 \leq k \leq n - 1 \\ k \neq k^{'} \end{array}} (0) + [\exists r \in ℚ, m \in ℤ : x + \frac{k^{'}}{n} = r π + m] \\ = 0 + 1 \\ = 1 \\ = [\exists r \in ℚ, m \in ℤ : n x = r π + m] \\ = f (n x) . \end{array}

In the case that we may not ﬁnd such an integer $k^{'}$ , even $k^{'} = 0$ , then clearly $x \neq r π + m$ if and only if $n x \neq r^{'} π + m^{'}$ for $r^{'} = n r$ and $m^{'} = n m$ , and in such a case

\begin{array}{l} \sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) & = \sum_{0 \leq k \leq n - 1} [\exists r \in ℚ, m \in ℤ : x + \frac{k}{n} = r π + m] \\ = \sum_{0 \leq k \leq n - 1} (0) \\ = 0 \\ = [\exists r \in ℚ, m \in ℤ : n x = r π + m] \\ = f (n x) . \end{array}

In either case, we ﬁnd that

\sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) = f (n x)

as we needed to show. □

Proposition (E1). $f (x) = [\exists r \in ℚ^{+}, m \in ℤ : x = r π + m]$ is replicative.

Proof. Let $f$ be a function deﬁned as

f (x) = [\exists r \in ℚ^{+}, m \in ℤ : x = r π + m]

and let $n$ be an arbitrary positive integer. We must show that

\sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) = f (n x) .

But we may rely on the proof of Proposition D, and speciﬁcally, the determination of the rational $r^{'}$ such that $r^{'} = n r$ . $r > 0$ if and only if $n r > 0$ , since $n > 0$ . Hence the result. □

Proposition (E2). $f (x) = [\exists r \in ℚ, m \in ℤ^{+} : x = r π + m]$ is replicative.

Proof. Let $f$ be a function deﬁned as

f (x) = [\exists r \in ℚ, m \in ℤ^{+} : x = r π + m]

and let $n$ be an arbitrary positive integer. We must show that

\sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) = f (n x) .

But we may rely on the proof of Proposition D, and speciﬁcally, the determination of the integer $m^{'}$ such that $m^{'} = n m - k^{'}$ . $m > 0$ if and only if $n r > 0$ , since $n > k^{'} \geq 0$ . Hence the result. □

Proposition (E3). $f (x) = [(\exists r \in ℚ^{+}, m \in ℤ^{+} : x = r π + m]$ is replicative.

Proof. Let $f$ be a function deﬁned as

f (x) = [\exists r \in ℚ^{+}, m \in ℤ^{+} : x = r π + m]

and let $n$ be an arbitrary positive integer. We must show that

\sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) = f (n x) .

But we may rely on the proofs of Proposition E1 and Proposition E2, and speciﬁcally, the determination of both the rational $r^{'}$ such that $r^{'} = n r$ and the integer $m^{'}$ such that $m^{'} = n m - k^{'}$ simultaneously. Hence the result. □

Proposition (F). $f (x) = \log | 2 \sin π x |$ is replicative, if the value $f (x) = - \infty$ is allowed.

Proof. Let $f$ be a function deﬁned as

f (x) = \log | 2 \sin π x |

and let $n$ be an arbitrary positive integer. We must show that

\sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) = f (n x)

allowing for $f (x) = - \infty$ .

Note that we have the equalities

2 \sin 𝜃 = (e^{i 𝜃} - e^{- i 𝜃}) ∕ i = (1 - e^{- 2 i 𝜃}) e^{i 𝜃 - i π ∕ 2},

\prod_{0 \leq k \leq n - 1} (1 - e^{- 2 i π (x + k ∕ n)}) = 1 - e^{- 2 i π n x},

and

\prod_{0 \leq k \leq n - 1} e^{i π (x - (1 ∕ 2) + (k ∕ n))} = e^{i π (n x - 1 ∕ 2)} .

Then

\begin{array}{l} \sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) & = \sum_{0 \leq k \leq n - 1} \log |2 \sin π (x + \frac{k}{n})| \\ = \log |\prod_{0 \leq k \leq n - 1} 2 \sin π (x + \frac{k}{n})| \\ = \log |\prod_{0 \leq k \leq n - 1} (e^{i π (x + \frac{k}{n})} - e^{- i π (x + \frac{k}{n})}) ∕ i| \\ = \log |\prod_{0 \leq k \leq n - 1} (1 - e^{- 2 i π (x + \frac{k}{n})}) e^{i π (x + \frac{k}{n}) - i π ∕ 2}| \\ = \log |(\prod_{0 \leq k \leq n - 1} 1 - e^{- 2 i π (x + \frac{k}{n})}) (\prod_{0 \leq k \leq n - 1} e^{i π (x + \frac{k}{n}) - i π ∕ 2})| \\ = \log |(1 - e^{- 2 i π n x}) (e^{i π (n x - 1 ∕ 2)})| \\ = \log |(e^{i π n x} - e^{- i π n x}) ∕ i| \\ = \log |2 \sin π n x| \end{array}

as we needed to show. □

Proposition (G). The sum of any two replicative functions is replicative.

Proof. Let $f$ and $g$ be replicative functions, $h$ a function deﬁned as

h (x) = f (x) + g (x),

and let $n$ be an arbitrary positive integer. We must show that

\sum_{0 \leq k \leq n - 1} h (x + \frac{k}{n}) = h (n x) .

But

\begin{array}{l} \sum_{0 \leq k \leq n - 1} h (x + \frac{k}{n}) & = \sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) + g (x + \frac{k}{n}) \\ = \sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) + \sum_{0 \leq k \leq n - 1} g (x + \frac{k}{n}) \\ = f (x n) + g (x n) \\ = h (x n) \end{array}

as we needed to show. □

Proposition (H). A constant multiple of a replicative function is replicative.

Proof. Let $f$ be a replicative function, $c$ an arbitrary real number, $g$ a function deﬁned as

g (x) = c f (x),

and let $n$ be an arbitrary positive integer. We must show that

\sum_{0 \leq k \leq n - 1} g (x + \frac{k}{n}) = g (n x) .

But

\begin{array}{l} \sum_{0 \leq k \leq n - 1} g (x + \frac{k}{n}) & = \sum_{0 \leq k \leq n - 1} c f (x + \frac{k}{n}) \\ = c \sum_{0 \leq k \leq n - 1} f (x + \frac{k}{n}) \\ = c f (x n) \\ = g (x n) \end{array}

as we needed to show. □

Proposition (I). The function $g (x) = f (x - ⌊ x ⌋)$ , where $f (x)$ is replicative is itself replicative.

Proof. Let $f$ be a replicative function, $g$ a function deﬁned as

g (x) = f (x - ⌊ x ⌋),

and let $n$ be an arbitrary positive integer. We must show that

\sum_{0 \leq k \leq n - 1} g (x + \frac{k}{n}) = g (n x) .

Let $k^{'}$ be the unique integer such that

{x} + \frac{k^{'} - 1}{n} < 1 \leq {x} + \frac{k^{'}}{n}

so that $k^{'} = ⌈ n (1 - {x}) ⌉$ . Then

\begin{array}{l} \sum_{0 \leq k \leq n - 1} g (x + \frac{k}{n}) & = \sum_{0 \leq k \leq n - 1} f (\{x + \frac{k}{n}\}) \\ = \sum_{0 \leq k \leq k^{'} - 1} f (\{x + \frac{k}{n}\}) + \sum_{k^{'} \leq k \leq n - 1} f (\{x + \frac{k}{n}\}) \\ = \sum_{0 \leq k \leq k^{'} - 1} f ({x} + \frac{k}{n}) + \sum_{k^{'} \leq k \leq n - 1} f ({x} + \frac{k}{n} - 1) \\ = \sum_{0 \leq k \leq k^{'} - 1} f ({x} + \frac{k}{n}) + \sum_{k^{'} \leq k \leq n - 1} f ({x} + \frac{k - n}{n}) \\ = \sum_{n - k^{'} \leq k \leq n - 1} f ({x} + \frac{k^{'} - n + k}{n}) + \sum_{0 \leq k \leq n - k^{'} - 1} f ({x} + \frac{k^{'} - n + k}{n}) \\ = \sum_{0 \leq k \leq n - 1} f ({x} + \frac{k^{'} - n}{n} + \frac{k}{n}) \\ = f (n ({x} + \frac{k^{'} - n}{n})) \\ = f (n {x} + k^{'} - n) \\ = f (n {x} + ⌈ n (1 - {x}) ⌉ - n) \\ = f (n {x} + ⌈ n - n {x} - n ⌉) \\ = f (n {x} + ⌈ - n {x} ⌉) \\ = f (n {x} - ⌊ n {x} ⌋) \\ = f ({n {x}}) \\ = f ({n x - n ⌊ x ⌋}) \\ = f ({n x - ⌊ n x ⌋}) \\ = f ({n x}) \\ = f (n x - ⌊ n x ⌋) \\ = g (n x) \end{array}

as we needed to show. □

40. [HM46] Study the class of replicative functions; determine all replicative functions of a special type. For example, is the function in (a) of exercise 39 the only continuous replicative function? It may be interesting to study also the more general class of functions for which

Here

a_{n}

and

b_{n}

are numbers that depend on

n

but not on

x

. Derivatives and (if

b_{n} = 0

) integrals of these functions are of the same type. If we require that

b_{n} = 0

, we have, for example, the Bernoulli polynomials, the trigonometric functions

\cot π x

and

\csc^{2} π x

, as well as Hurwitz’s generalized zeta function

ζ (s, x) = \sum_{k \geq 0} 1 ∕ {(k + x)}^{s}

for ﬁxed

s

. With

b_{n} \neq 0

we have still other well-known functions, such as the psi function.

n.a.

________________________________________________________________________________

$\dots$ For further results see L. J. Mordell, J. London Math. Soc. 33 (1958), 371–375.; M. F. Yoder, Æquationes Mathematcæ 13 (1975), 251–261.

41. [M23] Let

a_{1}, a_{2}, a_{3}, \dots

be the sequence

1, 2, 2, 3, 3, 3, 4, 4, 4, 4, \dots

; ﬁnd an expression for

a_{n}

in terms of

n

, using the ﬂoor and/or ceiling function.

We want to ﬁnd a kind of inverse of the sum of the ﬁrst $n$ integers. That is, we want to know $a_{n} = k$ such that

\sum_{1 \leq i \leq k - 1} i = \frac{(k - 1) k}{2} < n \leq \frac{k (k + 1)}{2} = \sum_{1 \leq i \leq k} i .

Solving for $k$ yields

k - 1 < \frac{\sqrt{8 n + 1} - 1}{2} \leq k

or equivalently

k = a_{n} = ⌈\frac{\sqrt{8 n + 1} - 1}{2}⌉ .

(b) The preceding formula is useful for evaluating certain sums involving the ﬂoor function. Prove that, if

b

is an integer

\geq 2

Proposition (A). $\sum_{1 \leq k \leq n} a_{k} = n a_{n} - \sum_{1 \leq k \leq n - 1} k (a_{k + 1} - a_{k})$ if $n > 0$ .

Proof. Let $n$ be an arbitrary integer such that $n > 0$ . We must show that

\sum_{1 \leq k \leq n} a_{k} = n a_{n} - \sum_{1 \leq k \leq n - 1} k (a_{k + 1} - a_{k}) .

But

\begin{array}{l} \sum_{1 \leq k \leq n} a_{k} & = \sum_{1 \leq k \leq n} (1) a_{k} \\ = \sum_{1 \leq k \leq n} (k - k + 1) a_{k} \\ = \sum_{1 \leq k \leq n} k a_{k} - (k - 1) a_{k} \\ = - \sum_{1 \leq k \leq n} (k - 1) a_{k} + \sum_{1 \leq k \leq n} k a_{k} \\ = (0) a_{1} - \sum_{2 \leq k \leq n} (k - 1) a_{k} + \sum_{1 \leq k \leq n} k a_{k} \\ = - \sum_{2 \leq k \leq n} (k - 1) a_{k} + \sum_{1 \leq k \leq n} k a_{k} \\ = n a_{n} - \sum_{2 \leq k \leq n} (k - 1) a_{k} + \sum_{1 \leq k \leq n - 1} k a_{k} \\ = n a_{n} - \sum_{1 \leq k \leq n - 1} k a_{k + 1} + \sum_{1 \leq k \leq n - 1} k a_{k} \\ = n a_{n} - \sum_{1 \leq k \leq n - 1} k a_{k + 1} - k a_{k} \\ = n a_{n} - \sum_{1 \leq k \leq n - 1} k (a_{k + 1} - a_{k}) \end{array}

as we needed to show. □

Proposition (B). $\sum_{1 \leq k \leq n} ⌊ \log_{b} k ⌋ = (n + 1) ⌊ \log_{b} n ⌋ - (b^{⌊ \log_{b} n ⌋ + 1} - b) ∕ (b - 1)$ if $b \geq 2$ .

Proof. Let $b$ be an arbitrary integer such that $b \geq 2$ . We must show that

\sum_{1 \leq k \leq n} ⌊ \log_{b} k ⌋ = (n + 1) ⌊ \log_{b} n ⌋ - (b^{⌊ \log_{b} n ⌋ + 1} - b) ∕ (b - 1) .

But from Proposition A, we have

\begin{array}{l} \sum_{1 \leq k \leq n} ⌊ \log_{b} k ⌋ & = \sum_{1 \leq k \leq n - 1} ⌊ \log_{b} k ⌋ + \sum_{n \leq k \leq n} ⌊ \log_{b} k ⌋ \\ = \sum_{1 \leq k \leq n - 1} ⌊ \log_{b} k ⌋ + \sum_{b^{⌊ \log_{b} n ⌋} \leq k \leq n} ⌊ \log_{b} k ⌋ \\ = \sum_{b^{0} \leq k < b^{⌊ \log_{b} n ⌋}} ⌊ \log_{b} k ⌋ + \sum_{b^{⌊ \log_{b} n ⌋} \leq k \leq n} ⌊ \log_{b} k ⌋ \\ = \sum_{0 \leq j < ⌊ \log_{b} n ⌋} \sum_{b^{j} \leq k < b^{j + 1}} ⌊ \log_{b} k ⌋ + \sum_{b^{⌊ \log_{b} n ⌋} \leq k \leq n} ⌊ \log_{b} k ⌋ \\ = \sum_{0 \leq j < ⌊ \log_{b} n ⌋} j (b^{j + 1} - b^{j}) + \sum_{b^{⌊ \log_{b} n ⌋} \leq k \leq n} ⌊ \log_{b} k ⌋ \\ = (\sum_{0 \leq j < ⌊ \log_{b} n ⌋} j (b^{j + 1} - b^{j})) + (n - b^{⌊ \log_{b} n ⌋} + 1) ⌊ \log_{b} n ⌋ \\ = - (⌊ \log_{b} n ⌋ b^{⌊ \log_{b} n ⌋} - \sum_{0 \leq j \leq ⌊ \log_{b} n ⌋ - 1} j (b^{j + 1} - b^{j})) + (n + 1) ⌊ \log_{b} n ⌋ \\ = - (\sum_{0 \leq j \leq ⌊ \log_{b} n ⌋ - 1} b^{j + 1}) + (n + 1) ⌊ \log_{b} n ⌋ \\ = (n + 1) ⌊ \log_{b} n ⌋ - \sum_{1 \leq j \leq ⌊ \log_{b} n ⌋} b^{j} \\ = (n + 1) ⌊ \log_{b} n ⌋ - (b^{⌊ \log_{b} n ⌋ + 1} - b) ∕ (b - 1) \end{array}

as we needed to show. □

We have by exercise 42

\begin{array}{l} \sum_{1 \leq k \leq n} ⌊ \sqrt{k} ⌋ & = \sum_{1 \leq k \leq n - 1} ⌊ \sqrt{k} ⌋ + \sum_{n \leq k \leq n} ⌊ \sqrt{k} ⌋ \\ = \sum_{1^{2} \leq k < {⌊ n ⌋}^{2}} ⌊ \sqrt{k} ⌋ + \sum_{{⌊ \sqrt{n} ⌋}^{2} \leq k \leq n} ⌊ \sqrt{k} ⌋ \\ = \sum_{1 \leq j < ⌊ n ⌋} \sum_{j^{2} \leq k < {(j + 1)}^{2}} ⌊ \sqrt{k} ⌋ + \sum_{{⌊ \sqrt{n} ⌋}^{2} \leq k \leq n} ⌊ \sqrt{k} ⌋ \\ = \sum_{1 \leq j < ⌊ n ⌋} j ({(j + 1)}^{2} - j^{2}) + \sum_{{⌊ \sqrt{n} ⌋}^{2} \leq k \leq n} ⌊ \sqrt{k} ⌋ \\ = (\sum_{1 \leq j < ⌊ n ⌋} j ({(j + 1)}^{2} - j^{2})) + (n - {⌊ \sqrt{n} ⌋}^{2} + 1) ⌊ \sqrt{n} ⌋ \\ = (n - {⌊ \sqrt{n} ⌋}^{2} + 1) ⌊ \sqrt{n} ⌋ + (\sum_{1 \leq j < ⌊ n ⌋} j ({(j + 1)}^{2} - j^{2})) \\ = (n + 1) ⌊ \sqrt{n} ⌋ - (⌊ \sqrt{n} ⌋ {⌊ \sqrt{n} ⌋}^{2} - (\sum_{1 \leq j < ⌊ n ⌋} j ({(j + 1)}^{2} - j^{2}))) \\ = (n + 1) ⌊ \sqrt{n} ⌋ - \sum_{1 \leq k \leq ⌊ \sqrt{n} ⌋} k^{2} \\ = (n + 1) ⌊ \sqrt{n} ⌋ - \frac{⌊ \sqrt{n} ⌋ (⌊ \sqrt{n} ⌋ + 1) (2 ⌊ \sqrt{n} ⌋ + 1)}{6} \\ = ⌊ \sqrt{n} ⌋ ((n + 1) - \frac{(⌊ \sqrt{n} ⌋ + 1) (2 ⌊ \sqrt{n} ⌋ + 1)}{6}) \\ = ⌊ \sqrt{n} ⌋ (n - \frac{(⌊ \sqrt{n} ⌋ + 1) (2 ⌊ \sqrt{n} ⌋ + 1) - 6}{6}) \\ = ⌊ \sqrt{n} ⌋ (n - \frac{(2 ⌊ \sqrt{n} ⌋ + 5) (⌊ \sqrt{n} ⌋ - 1)}{6}) . \end{array}

44. [M24] Show that

\sum_{k \geq 0} \sum_{1 \leq j < b} ⌊ (n + j b^{k}) ∕ b^{k + 1} ⌋ = n

, if

b

and

n

are integers,

n \geq 0

, and

b \geq 2

. What is the value of this sum when

n < 0

We may prove the equality for nonnegative $n$ .

Proposition. $\sum_{k \geq 0} \sum_{1 \leq j < b} ⌊\frac{n + j b^{k}}{b^{k + 1}}⌋ = n$ if $b$ and $n$ are integers, $n \geq 0$ , and $b \geq 2$ .

Proof. Let $b$ and $n$ be arbitrary integers such that $n \geq 0$ and $b \geq 2$ . We must show that

\sum_{k \geq 0} \sum_{1 \leq j < b} ⌊\frac{n + j b^{k}}{b^{k + 1}}⌋ = n .

By exercise 38 with $x = \frac{n}{b^{k + 1}}$ and $y = b$ we have

\begin{array}{l} \sum_{1 \leq j < b} ⌊\frac{n + j b^{k}}{b^{k + 1}}⌋ & = (\sum_{0 \leq j < b} ⌊ \frac{n + j b^{k}}{b^{k + 1}} ⌋) - ⌊\frac{n}{b^{k + 1}}⌋ \\ = (\sum_{0 \leq j < b} ⌊\frac{n}{b^{k + 1}} + \frac{j}{b}⌋) - ⌊\frac{n}{b^{k + 1}}⌋ \\ = ⌊\frac{n b}{b^{k + 1}} + ⌊\frac{n}{b^{k + 1}} + 1⌋ (⌈ b ⌉ - b)⌋ - ⌊\frac{n}{b^{k + 1}}⌋ \\ = ⌊\frac{n b}{b^{k + 1}}⌋ - ⌊\frac{n}{b^{k + 1}}⌋ \\ = ⌊\frac{n}{b^{k}}⌋ - ⌊\frac{n}{b^{k + 1}}⌋ . \end{array}

In the case that $n > 0$ , for some arbitrary $k$

\begin{array}{l} ⌊\frac{n}{b^{k}}⌋ = 0 & \Leftrightarrow 0 \leq \frac{n}{b^{k}} < 1 \\ \Rightarrow n < b^{k} \\ \Leftrightarrow \log_{b} n < \log_{b} b^{k} \\ \Leftrightarrow \log_{b} n < k \\ \Leftrightarrow k \geq ⌊ \log_{b} n ⌋ + 1 . \end{array}

Then

\begin{array}{l} \sum_{k \geq 0} \sum_{1 \leq j < b} ⌊\frac{n + j b^{k}}{b^{k + 1}}⌋ & = \sum_{k \geq 0} ⌊\frac{n}{b^{k}}⌋ - ⌊\frac{n}{b^{k + 1}}⌋ \\ = (\sum_{0 \leq k \leq ⌊ \log_{b} n ⌋} ⌊\frac{n}{b^{k}}⌋ - ⌊\frac{n}{b^{k + 1}}⌋) + (\sum_{k \geq ⌊ \log_{b} n ⌋ + 1} ⌊\frac{n}{b^{k}}⌋ - ⌊\frac{n}{b^{k + 1}}⌋) \\ = (\sum_{0 \leq k \leq ⌊ \log_{b} n ⌋} ⌊\frac{n}{b^{k}}⌋ - ⌊\frac{n}{b^{k + 1}}⌋) + 0 \\ = \sum_{0 \leq k \leq ⌊ \log_{b} n ⌋} ⌊\frac{n}{b^{k}}⌋ - \sum_{0 \leq k \leq ⌊ \log_{b} n ⌋} ⌊\frac{n}{b^{k + 1}}⌋ \\ = ⌊\frac{n}{b^{0}}⌋ + \sum_{1 \leq k \leq ⌊ \log_{b} n ⌋} ⌊\frac{n}{b^{k}}⌋ - \sum_{1 \leq k \leq ⌊ \log_{b} n ⌋ + 1} ⌊\frac{n}{b^{k}}⌋ \\ = ⌊\frac{n}{b^{0}}⌋ + \sum_{1 \leq k \leq ⌊ \log_{b} n ⌋} ⌊\frac{n}{b^{k}}⌋ - (\sum_{1 \leq k \leq ⌊ \log_{b} n ⌋} ⌊\frac{n}{b^{k}}⌋) - ⌊\frac{n}{b^{⌊ \log_{b} n ⌋ + 1}}⌋ \\ = ⌊\frac{n}{b^{0}}⌋ + 0 - ⌊\frac{n}{b^{⌊ \log_{b} n ⌋ + 1}}⌋ \\ = n - 0 \\ = n . \end{array}

In the case that $n = 0$ , then clearly

\sum_{k \geq 0} \sum_{1 \leq j < b} ⌊\frac{0 + j b^{k}}{b^{k + 1}}⌋ = \sum_{k \geq 0} ⌊\frac{0}{b^{k}}⌋ - ⌊\frac{0}{b^{k + 1}}⌋ = 0 = n .

Hence, in either case

\sum_{k \geq 0} \sum_{1 \leq j < b} ⌊\frac{n + j b^{k}}{b^{k + 1}}⌋ = n

as we needed to show. □

When $n < 0$ , we may ﬁnd an arbitrary $k$ such that

\begin{array}{l} ⌊\frac{n}{b^{k}}⌋ = - 1 & \Leftrightarrow - 1 \leq \frac{n}{b^{k}} < 0 \\ \Leftrightarrow 0 < \frac{- n}{b^{k}} \leq 1 \\ \Rightarrow - n \leq b^{k} \\ \Leftrightarrow \log_{b} - n \leq \log_{b} b^{k} \\ \Leftrightarrow \log_{b} - n \leq k \\ \Leftrightarrow k \geq ⌊ \log_{b} - n ⌋ . \end{array}

Then

\begin{array}{l} \sum_{k \geq 0} \sum_{1 \leq j < b} ⌊\frac{n + j b^{k}}{b^{k + 1}}⌋ & = \sum_{k \geq 0} ⌊\frac{n}{b^{k}}⌋ - ⌊\frac{n}{b^{k + 1}}⌋ \\ = (\sum_{0 \leq k \leq ⌊ \log_{b} - n ⌋ - 1} ⌊\frac{n}{b^{k}}⌋ - ⌊\frac{n}{b^{k + 1}}⌋) + (\sum_{k \geq ⌊ \log_{b} - n ⌋} ⌊\frac{n}{b^{k}}⌋ - ⌊\frac{n}{b^{k + 1}}⌋) \\ = (\sum_{0 \leq k \leq ⌊ \log_{b} - n ⌋ - 1} ⌊\frac{n}{b^{k}}⌋ - ⌊\frac{n}{b^{k + 1}}⌋) + (\sum_{k \geq ⌊ \log_{b} - n ⌋} - 1 + 1) \\ = (\sum_{0 \leq k \leq ⌊ \log_{b} - n ⌋ - 1} ⌊\frac{n}{b^{k}}⌋ - ⌊\frac{n}{b^{k + 1}}⌋) + 0 \\ = \sum_{0 \leq k \leq ⌊ \log_{b} - n ⌋ - 1} ⌊\frac{n}{b^{k}}⌋ - \sum_{0 \leq k \leq ⌊ \log_{b} - n ⌋ - 1} ⌊\frac{n}{b^{k + 1}}⌋ \\ = ⌊\frac{n}{b^{0}}⌋ + \sum_{1 \leq k \leq ⌊ \log_{b} - n ⌋ - 1} ⌊\frac{n}{b^{k}}⌋ - \sum_{1 \leq k \leq ⌊ \log_{b} - n ⌋} ⌊\frac{n}{b^{k}}⌋ \\ = ⌊\frac{n}{b^{0}}⌋ + \sum_{1 \leq k \leq ⌊ \log_{b} - n ⌋ - 1} ⌊\frac{n}{b^{k}}⌋ - (\sum_{1 \leq k \leq ⌊ \log_{b} - n ⌋ - 1} ⌊\frac{n}{b^{k}}⌋) - ⌊\frac{n}{b^{⌊ \log_{b} - n ⌋}}⌋ \\ = ⌊\frac{n}{b^{0}}⌋ + 0 - ⌊\frac{n}{b^{⌊ \log_{b} - n ⌋}}⌋ \\ = n + 1 . \end{array}

▸

45. [M28] The result of exercise 37 is somewhat surprising, since it implies that when

m

and

n

are positive integers

This “reciprocity relationship” is one of many similar formulas (see Section 3.3.3). Show that for any function

f

, we have

[Hint: Consider the change of variable

r = ⌊ m j ∕ n ⌋

. Binomial coeﬃcients

(\binom{m}{k})

are discussed in Section 1.2.6.]

Proposition. $\sum_{0 \leq j < n} f (⌊\frac{m j}{n}⌋) = n f (m - 1) + \sum_{0 \leq r < m} ⌈\frac{r n}{m}⌉ (f (r - 1) - f (r))$ for any function $f$ and positive integers $m$ and $n$ .

Proof. Let $f$ be any function and $m$ and $n$ arbitrary positive integers. We must show that

\sum_{0 \leq j < n} f (⌊\frac{m j}{n}⌋) = n f (m - 1) + \sum_{0 \leq r < m} ⌈\frac{r n}{m}⌉ (f (r - 1) - f (r)) .

Note that

\begin{array}{l} ⌊\frac{m j}{n}⌋ = r & \Leftrightarrow r \leq \frac{m j}{n} < r + 1 \\ \Leftrightarrow n r \leq m j < n (r + 1) \\ \Leftrightarrow \frac{n r}{m} \leq j < \frac{n (r + 1)}{m} \\ \Leftrightarrow \frac{n r}{m} \leq j < \frac{n (r + 1)}{m} . \\ \Leftrightarrow ⌈\frac{n r}{m}⌉ \leq j < ⌈\frac{n (r + 1)}{m}⌉ . \end{array}

Then

\begin{array}{l} \sum_{0 \leq j < n} f (⌊\frac{m j}{n}⌋) & = \sum_{0 \leq r < m} \sum_{⌈\frac{n r}{m}⌉ \leq j < ⌈\frac{n (r + 1)}{m}⌉} f (⌊\frac{m j}{n}⌋) \\ = \sum_{0 \leq r < m} \sum_{⌈\frac{n r}{m}⌉ \leq j < ⌈\frac{n (r + 1)}{m}⌉} f (r) \\ = \sum_{0 \leq r < m} (⌈\frac{n (r + 1)}{m}⌉ - ⌈\frac{n r}{m}⌉) f (r) \\ = \sum_{0 \leq r < m} ⌈\frac{n (r + 1)}{m}⌉ f (r) - ⌈\frac{n r}{m}⌉ f (r) \\ = \sum_{0 \leq r < m} ⌈\frac{n (r + 1)}{m}⌉ f (r) - \sum_{0 \leq r < m} ⌈\frac{n r}{m}⌉ f (r) \\ = \sum_{1 \leq r < m + 1} ⌈\frac{n r}{m}⌉ f (r - 1) - \sum_{0 \leq r < m} ⌈\frac{n r}{m}⌉ f (r) \\ = ⌈\frac{n m}{m}⌉ f (m - 1) + ⌈\frac{n (0)}{m}⌉ f (0 - 1) + \sum_{1 \leq r < m} ⌈\frac{n r}{m}⌉ f (r - 1) - \sum_{0 \leq r < m} ⌈\frac{n r}{m}⌉ f (r) \\ = n f (m - 1) + \sum_{0 \leq r < m} ⌈\frac{n r}{m}⌉ f (r - 1) - \sum_{0 \leq r < m} ⌈\frac{n r}{m}⌉ f (r) \\ = n f (m - 1) + \sum_{0 \leq r < m} ⌈\frac{n r}{m}⌉ (f (r - 1) - f (r)) \end{array}

as we needed to show. □

Proposition. $\sum_{0 \leq j < n} (\binom{⌊ m j ∕ n ⌋ + 1}{k}) + \sum_{0 \leq j < m} ⌈\frac{j n}{m}⌉ (\binom{j}{k - 1}) = n (\binom{m}{k})$ for any function $f$ and positive integers $k$ , $m$ , and $n$ .

Proof. Let $f$ be any function and $k$ , $m$ , and $n$ arbitrary positive integers. We must show that

\sum_{0 \leq j < n} (\binom{⌊ m j ∕ n ⌋ + 1}{k}) + \sum_{0 \leq j < m} ⌈\frac{j n}{m}⌉ (\binom{j}{k - 1}) = n (\binom{m}{k}) .

But by the preceding proposition for

f (x) = (\binom{x + 1}{k})

we have that

\sum_{0 \leq j < n} (\binom{⌊m j ∕ n⌋ + 1}{k}) = n (\binom{m}{k}) + \sum_{0 \leq r < m} ⌈\frac{r n}{m}⌉ ((\binom{r}{k}) - (\binom{r + 1}{k}));

and

\begin{array}{l} (\binom{r + 1}{k}) = (\binom{r}{k}) + (\binom{r}{k - 1}) & \Leftrightarrow (\binom{r}{k}) - (\binom{r + 1}{k}) = - (\binom{r}{k - 1}); \end{array}

\begin{array}{l} \sum_{0 \leq j < n} (\binom{⌊m j ∕ n⌋ + 1}{k}) & = n (\binom{m}{k}) + \sum_{0 \leq r < m} ⌈\frac{r n}{m}⌉ ((\binom{r}{k}) - (\binom{r + 1}{k})) \\ = n (\binom{m}{k}) - \sum_{0 \leq r < m} ⌈\frac{r n}{m}⌉ (\binom{r}{k - 1}) \\ = n (\binom{m}{k}) - \sum_{0 \leq j < m} ⌈\frac{j n}{m}⌉ (\binom{j}{k - 1}) . \end{array}

Hence

\sum_{0 \leq j < n} (\binom{⌊ m j ∕ n ⌋ + 1}{k}) + \sum_{0 \leq j < m} ⌈\frac{j n}{m}⌉ (\binom{j}{k - 1}) = n (\binom{m}{k})

as we needed to show. □

46. [M29] (General reciprocity law.) Extend the formula of exercise 45 to obtain an expression for

\sum_{0 \leq j < α n} f (⌊ m j ∕ n ⌋)

, where

α

is any positive real number.

For any positive real number $α$ , since by the ﬁrst proposition of exercise 45

\begin{array}{l} ⌊\frac{m j}{n}⌋ = r & \Leftrightarrow ⌈\frac{r n}{m}⌉ \leq j < ⌈\frac{(r + 1) n}{m}⌉, \end{array}

we have

\begin{array}{l} \sum_{0 \leq j < α n} f (⌊\frac{m j}{n}⌋) & = \sum_{0 \leq r < α m} \sum_{⌈\frac{r n}{m}⌉ \leq j < ⌈\frac{(r + 1) n}{m}⌉} f (⌊\frac{m j}{n}⌋) \\ = \sum_{0 \leq r < α m} \sum_{⌈\frac{r n}{m}⌉ \leq j < ⌈\frac{(r + 1) n}{m}⌉} f (r) \\ = \sum_{0 \leq r < α m} (⌈\frac{(r + 1) n}{m}⌉ - ⌈\frac{r n}{m}⌉) f (r) \\ = \sum_{0 \leq r < α m} ⌈\frac{(r + 1) n}{m}⌉ f (r) - ⌈\frac{r n}{m}⌉ f (r) \\ = \sum_{0 \leq r < α m} ⌈\frac{(r + 1) n}{m}⌉ f (r) - \sum_{0 \leq r < α m} ⌈\frac{r n}{m}⌉ f (r) \\ = \sum_{1 \leq r < α m + 1} ⌈\frac{r n}{m}⌉ f (r - 1) - \sum_{0 \leq r < α m} ⌈\frac{r n}{m}⌉ f (r) \\ = ⌈ \frac{α n m}{m} ⌉ f (⌈ α m ⌉ - 1) + ⌈\frac{(0) n}{m}⌉ f (0 - 1) + \sum_{1 \leq r < α m} ⌈\frac{r n}{m}⌉ f (r - 1) - \sum_{0 \leq r < α m} ⌈\frac{r n}{m}⌉ f (r) \\ = ⌈ α n ⌉ f (⌈ α m ⌉ - 1) + \sum_{0 \leq r < α m} ⌈\frac{r n}{m}⌉ f (r - 1) - \sum_{0 \leq r < α m} ⌈\frac{r n}{m}⌉ f (r) \\ = ⌈ α n ⌉ f (⌈ α m ⌉ - 1) + \sum_{0 \leq r < α m} ⌈\frac{r n}{m}⌉ (f (r - 1) - f (r)) . \end{array}

▸

47. [M31] When

p

is an odd prime number, the Legendre symbol

(\frac{q}{p})

is deﬁned to be

+ 1

0

, or

- 1

, depending on whether

q^{(p - 1) ∕ 2} mod p

1

0

, or

p - 1

. (Exercise 26 proves that these are the only possible values.)

a)

Given that

q

is not a multiple of

p

, show that the numbers

{(- 1)}^{⌊ 2 k q ∕ p ⌋} (2 k q mod p), 0 < k < p ∕ 2,

are congruent in some order to the numbers $2, 4, \dots, p - 1 (modulo p)$ . Hence $(\frac{q}{p}) = {(- 1)}^{σ}$ where $σ = \sum_{0 \leq k < p ∕ 2} ⌊ 2 k q ∕ p ⌋$ .

b)

Use the result of (a) to calculate

(\frac{2}{p})

c)

Given that

q

is odd, show that

\sum_{0 \leq k < p ∕ 2} ⌊ 2 k q ∕ p ⌋ \equiv \sum_{0 \leq k < p ∕ 2} ⌊ k q ∕ p ⌋ (modulo 2)

unless

q

is a multiple of

p

. [Hint: Consider the quantity

⌊ (p - 1 - 2 k) q ∕ p ⌋

d)

Use the general reciprocity formula of exercise 46 to obtain the law of quadratic reciprocity,

(\frac{q}{p}) (\frac{p}{q}) = {(- 1)}^{(p - 1) (q - 1) ∕ 4}

, given that

p

and

q

are distinct odd primes.

Answers to exercise 47 follow below.

(a)

We may prove the congruence relation in order to deduce that

(\frac{q}{p}) = {(- 1)}^{\sum_{0 \leq k < p ∕ 2} ⌊ 2 k q ∕ p ⌋}

p ⊥̸ q

p

an odd prime.

Proposition (A). $\prod_{0 < k < p ∕ 2} {(- 1)}^{⌊ 2 k q ∕ p ⌋} (2 k q mod p) \equiv \prod_{0 < k < p ∕ 2} 2 k (\mod p)$ if $p ⊥̸ q$ , $p$ an odd prime.

Proof. Let $p$ and $q$ be arbitrary integers such that $p ⊥̸ q$ and $p$ an odd prime. We must show that

\prod_{0 < k < p ∕ 2} {(- 1)}^{⌊ 2 k q ∕ p ⌋} (2 k q mod p) \equiv \prod_{0 < k < p ∕ 2} 2 k (mod p) .

Let $k$ be an arbitrary integer such that $0 < k < p ∕ 2$ . Then

2 k q = p ⌊\frac{2 k q}{p}⌋ + (2 k q) mod p

or equivalently

(2 k q mod p) \equiv 2 k q (\mod p) .

Since $p ⊥̸ q$ , $q \equiv 1 (\mod p)$ , and so

(2 k q mod p) \equiv 2 k (\mod p) .

Also, in the case that $⌊\frac{2 k q}{p}⌋$ is even, then so is $2 k q mod p$ , and

\begin{array}{l} {(- 1)}^{⌊ 2 k q ∕ p ⌋} (2 k q mod p) \equiv 2 k q mod p (\mod p) \\ \Rightarrow {(- 1)}^{⌊ 2 k q ∕ p ⌋} (2 k q mod p) \equiv 2 k q (\mod p); \end{array}

in the case that $⌊\frac{2 k q}{p}⌋$ is odd, then so is $2 k q mod p$ since $p$ is an odd prime, and

\begin{array}{l} {(- 1)}^{⌊ 2 k q ∕ p ⌋} (2 k q mod p) \equiv 2 k q - p (\mod p) \\ \Rightarrow {(- 1)}^{⌊ 2 k q ∕ p ⌋} (2 k q mod p) \equiv 2 k q (\mod p); \end{array}

and in either case

{(- 1)}^{⌊ 2 k q ∕ p ⌋} (2 k q mod p) \equiv 2 k (\mod p) .

Hence,

\prod_{0 < k < p ∕ 2} {(- 1)}^{⌊ 2 k q ∕ p ⌋} (2 k q mod p) \equiv \prod_{0 < k < p ∕ 2} 2 k (mod p)

as we needed to show. □

(b)

In order to calculate

(\frac{2}{p})

, we let

q = 2

and

p

be an odd prime. Then

(\frac{2}{p}) = {(- 1)}^{\sum_{0 \leq k < p ∕ 2} ⌊ 4 k ∕ p ⌋}

has solutions for $p = 4 n + 1$ or $4 n + 3$ for some integer $n$ ; in particular, $(- 1, 1, 1, - 1)$ for $p \equiv (1, 3, 5, 7) (\mod 8)$ , respectively; or expressed as the formula

(\frac{2}{p}) = {(- 1)}^{⌊\frac{p + 2}{4}⌋} .

(c)

We may show the relation.

Proposition (C). $\sum_{0 \leq k < p ∕ 2} ⌊ 2 k q ∕ p ⌋ \equiv \sum_{0 \leq k < p ∕ 2} ⌊ k q ∕ p ⌋ (\mod 2)$ if $q$ odd and $p ⊥̸ q$ .

Proof. Let $p$ and $q$ be arbitrary integers such that $p$ is an odd prime, $p ⊥̸ q$ , and $q$ odd. We must show that

\sum_{0 \leq k < p ∕ 2} ⌊ 2 k q ∕ p ⌋ \equiv \sum_{0 \leq k < p ∕ 2} ⌊ k q ∕ p ⌋ . (mod 2)

But

\begin{array}{l} \sum_{0 \leq k < p ∕ 2} ⌊ 2 k q ∕ p ⌋ & = \sum_{0 \leq k < p ∕ 4} ⌊ 2 k q ∕ p ⌋ + \sum_{p ∕ 4 \leq k < p ∕ 2} ⌊ 2 k q ∕ p ⌋ \\ = \sum_{0 \leq k < p ∕ 4} ⌊ 2 k q ∕ p ⌋ + \sum_{- 1 ∕ 2 < k \leq (p - 2) ∕ 4} ⌊ 2 (\frac{p - 1}{2} - k) q ∕ p ⌋ \\ = \sum_{0 \leq k < p ∕ 4} ⌊ 2 k q ∕ p ⌋ + \sum_{0 \leq k < p ∕ 4} ⌊ 2 (\frac{p - 1}{2} - k) q ∕ p ⌋ \\ = \sum_{0 \leq k < p ∕ 4} ⌊ 2 k q ∕ p ⌋ + \sum_{0 \leq k < p ∕ 4} ⌊ (p - 1 - 2 k) q ∕ p ⌋ \\ = \sum_{0 \leq k < p ∕ 4} ⌊ 2 k q ∕ p ⌋ + \sum_{0 \leq k < p ∕ 4} q - ⌈ (2 k + 1) q ∕ p ⌉ \\ = \sum_{0 \leq k < p ∕ 4} ⌊ 2 k q ∕ p ⌋ + \sum_{0 \leq k < p ∕ 4} q - 1 - ⌊ (2 k + 1) q ∕ p ⌋ . \end{array}

Then, since $p ⊥̸ q$ and $q$ odd

\begin{array}{l} \sum_{0 \leq k < p ∕ 2} ⌊ 2 k q ∕ p ⌋ & \equiv \sum_{0 \leq k < p ∕ 4} ⌊ 2 k q ∕ p ⌋ + \sum_{0 \leq k < p ∕ 4} q - 1 - ⌊ (2 k + 1) q ∕ p ⌋ \\ \equiv \sum_{0 \leq k < p ∕ 4} ⌊ 2 k q ∕ p ⌋ + \sum_{0 \leq k < p ∕ 4} ⌊ (2 k + 1) q ∕ p ⌋ \\ \equiv \sum_{0 \leq k < p ∕ 2} ⌊ k q ∕ p ⌋ (mod 2) \end{array}

as we needed to show. □

(d)

We may use the general reciprocity formula of exercise 46 to obtain the law of quadratic reciprocity.

Proposition (D). $(\frac{q}{p}) (\frac{p}{q}) = {(- 1)}^{(p - 1) (q - 1) ∕ 4}$ if $p$ and $q$ are distinct odd primes.

Proof. Let $p$ and $q$ be arbitrary integers such that $p$ and $q$ are distinct odd primes. We must show that

(\frac{q}{p}) (\frac{p}{q}) = {(- 1)}^{(p - 1) (q - 1) ∕ 4} .

From exercise 46

\begin{array}{l} \sum_{0 \leq k < p ∕ 2} ⌊\frac{k q}{p}⌋ & = ⌈ p ∕ 2 ⌉ (⌈ q ∕ 2 ⌉ - 1) + \sum_{0 \leq r < q ∕ 2} ⌈\frac{p r}{q}⌉ ((r - 1) - r) \\ = \frac{(p + 1) (q - 1)}{4} - \sum_{0 \leq r < q ∕ 2} ⌈\frac{p r}{q}⌉ \\ = \frac{(p + 1) (q - 1)}{4} - \frac{q - 1}{2} - \sum_{0 \leq r < q ∕ 2} ⌊\frac{p r}{q}⌋ \\ = \frac{(p - 1) (q - 1)}{4} - \sum_{0 \leq r < q ∕ 2} ⌊\frac{p r}{q}⌋ . \end{array}

Then, since

\begin{array}{l} \sum_{0 \leq k < p ∕ 2} ⌊\frac{2 k q}{p}⌋ + \sum_{0 \leq k < q ∕ 2} ⌊\frac{2 k p}{q}⌋ & \equiv \sum_{0 \leq k < p ∕ 2} ⌊\frac{k q}{p}⌋ + \sum_{0 \leq k < q ∕ 2} ⌊\frac{k p}{q}⌋ \\ \equiv \frac{(p - 1) (q - 1)}{4} (\mod 2) \end{array}

we have

\begin{array}{l} (\frac{q}{p}) (\frac{p}{q}) & = {(- 1)}^{\sum_{0 \leq k < p ∕ 2} ⌊ 2 k q ∕ p ⌋ + \sum_{0 \leq k < q ∕ 2} ⌊ 2 k p ∕ q ⌋} \\ = {(- 1)}^{(p - 1) (q - 1) ∕ 4} \end{array}

as we needed to show. □

______________________________________________________________________________________________________________________________

$\dots$ The idea of this proof goes back to G. Eisenstein, Crelle 28 (1844), 246–248; Eisenstein also gave several other proofs of this and other reciprocity laws in the same volume.

48. [M26] Prove or disprove the following identities, for integers

m

and

n

Some but not all of the identities may be proven.

(a)

The identity

⌊\frac{m + n - 1}{n}⌋ = ⌈\frac{m}{n}⌉

may be disproven by counterexample. Let $m = 0$ and $n = - 1$ . Then

\begin{array}{l} ⌊\frac{m + n - 1}{n}⌋ & = ⌊\frac{0 + - 1 - 1}{- 1}⌋ \\ = ⌊\frac{- 2}{- 1}⌋ \\ = ⌊2⌋ \\ = ⌊2⌋ \\ = 2 \\ \neq 0 \\ = ⌈0⌉ \\ = ⌈\frac{0}{- 1}⌉ \\ = ⌈\frac{m}{n}⌉ . \end{array}

Note, however, that we may prove the identity in the case that $n > 0$ .

Proposition (A). $⌊\frac{m + n - 1}{n}⌋ = ⌈\frac{m}{n}⌉$ if $n > 0$ .

Proof. Let $m$ and $n$ be arbitrary integers such that $n > 0$ . We must show that

⌊\frac{m + n - 1}{n}⌋ = ⌈\frac{m}{n}⌉ .

But since $n > 0$ implies $\frac{n - 1}{n} < 1$ ,

\begin{array}{l} f (x) = c (x) - 1 ⌊\frac{m + n - 1}{n}⌋ & = ⌊\frac{m}{n} + \frac{n - 1}{n}⌋ \\ = ⌈\frac{m}{n}⌉ \end{array}

as we needed to show. □

(b)

The second identity may be proven.

Proposition (B). $⌊\frac{n + 2 - ⌊ n ∕ 25 ⌋}{3}⌋ = ⌊\frac{8 n + 24}{25}⌋$ .

Proof. Let $n$ be an arbitrary integer. We must show that

⌊\frac{n + 2 - ⌊ n ∕ 25 ⌋}{3}⌋ = ⌊\frac{8 n + 24}{25}⌋ .

But

\begin{array}{l} ⌊\frac{n + 2 - ⌊ n ∕ 25 ⌋}{3}⌋ & = ⌈\frac{n - ⌊ n ∕ 25 ⌋}{3}⌉ \\ = ⌈\frac{n + ⌈ - n ∕ 25 ⌉}{3}⌉ \\ = ⌈\frac{⌈ 24 n ∕ 25 ⌉}{3}⌉ \\ = ⌈\frac{8 n}{25}⌉ \\ = ⌈\frac{8 n + 24}{25}⌉ \end{array}

as we needed to show. □

49. [M30] Suppose the integer-valued function

f (x)

satisﬁes the two simple laws (i)

f (x + 1) = f (x) + 1

; (ii)

f (x) = f (f (n x) ∕ n)

for all positive integers

n

. Prove that either

f (x) = ⌊ x ⌋

for all rational

x

, or

f (x) = ⌈ x ⌉

for all rational

x

We may prove the result.

Proposition. If an integer-valued function $f (x)$ satisﬁes $f (x + 1) = f (x) + 1$ and $f (x) = f (f (n x) ∕ n)$ for all positive integers $n$ , either $(\forall x \in ℚ) (f (x) = ⌊ x ⌋)$ or $(\forall x \in ℚ) (f (x) = ⌈ x ⌉)$ .

Proof. Let $f$ be an integer-valued function such that

f (x + 1) = f (x) + 1

and

f (x) = f (f (n x) ∕ n) .

We must show that either

(\forall x \in ℚ) (f (x) = ⌊ x ⌋)

(\forall x \in ℚ (f (x) = ⌈ x ⌉) .

First, we consider the domain of integers. From

f (0) = f (f ((1) 0) ∕ 1) = f (f (0))

we may deduce that $f (0) = 0$ . Then, from the inductive hypotheses $f (k) = k$ and $f (- k) = - k$ for an arbitrary integer $k \geq 0$ , we are able to show that $f (k + 1) = f (k) + 1$ and $f (1 - k) = f (- k) + 1$ respectively, proving by mathematical induction that $f (n) = n$ for all integers $n$ .

Second, we consider the domain of rationals. If $f (\frac{1}{2}) \leq 0$ , we have

\begin{array}{l} f (\frac{1}{2}) & = f (\frac{1}{1 - 2 f (1 ∕ 2)} f (\frac{1}{2} (1 - 2 f (1 ∕ 2)))) \\ = f (\frac{1}{1 - 2 f (1 ∕ 2)} f (\frac{1}{2} - f (\frac{1}{2}))) \\ = f (\frac{1}{1 - 2 f (1 ∕ 2)} f (f (\frac{1}{2}) - f (\frac{1}{2}))) \\ = f (0) \\ = 0; \end{array}

also, if $f (\frac{1}{n - 1}) = 0$ , we have

\begin{array}{l} f (\frac{1}{n - 1}) & = f (\frac{1}{n} f (\frac{n}{n - 1})) \\ = f (\frac{1}{n} f (1 + \frac{1}{n - 1})) \\ = f (\frac{1}{n} (1 + f (\frac{1}{n - 1}))) \\ = f (\frac{1}{n} (1 + 0)) \\ = f (\frac{1}{n}) \\ = 0; \end{array}

and furthermore, if $1 \leq m < n$ , by induction on $m$ and since $m ⌈ n ∕ m ⌉ - n \leq 0$ ,

\begin{array}{l} f (\frac{m}{n}) & = f (\frac{1}{⌈ n ∕ m ⌉} f (\frac{⌈ n ∕ m ⌉ m}{n})) \\ = f (\frac{1}{⌈ n ∕ m ⌉} f (\frac{⌈ n ∕ m ⌉ m + n - n}{n})) \\ = f (\frac{1}{⌈ n ∕ m ⌉} f (\frac{⌈ n ∕ m ⌉ m + n - n m ∕ m}{n})) \\ = f (\frac{1}{⌈ n ∕ m ⌉} f (\frac{n + m (⌈ n ∕ m ⌉ - n ∕ m)}{n})) \\ = f (\frac{1}{⌈ n ∕ m ⌉} f (1 + \frac{m}{n} (⌈\frac{n}{m}⌉ - \frac{n}{m}))) \\ = f (\frac{1}{⌈ n ∕ m ⌉} (1 + f (\frac{m}{n} (⌈\frac{n}{m}⌉ - \frac{n}{m})))) \\ = f (\frac{1}{⌈ n ∕ m ⌉} (1 + f (\frac{1}{n} (m ⌈n ∕ m⌉ - n)))) \\ = f (\frac{1}{⌈ n ∕ m ⌉} (1 + 0)) \\ = f (\frac{1}{⌈ n ∕ m ⌉}) \\ = 0 . \end{array}

Therefore, in the case that $f (\frac{1}{2}) \leq 0$ , $(\forall x \in ℚ) (f (x) = ⌊ x ⌋)$ .

On the other hand, in the case that $f (\frac{1}{2}) > 0$ , we may deﬁne $f^{'} (x) = - f (- x)$ so that $f^{'} (x + 1) = f^{'} (x) + 1$ and $f^{'} (x) = f^{'} (f^{'} (n x) ∕ n)$ , and

\begin{array}{l} f^{'} (\frac{1}{2}) & = f^{'} (\frac{1}{2}) - 1 + 1 \\ = f^{'} (\frac{1}{2} - 1) + 1 \\ = - f (\frac{- 1}{2} + 1) + 1 \\ = 1 - f (\frac{1}{2}) \\ \leq 0 . \end{array}

Therefore, $f^{'} (x) = - f (- x) = - ⌊ - x ⌋ = ⌈ x ⌉$ ; that is, in the case that $f (\frac{1}{2}) > 0$ , $(\forall x \in ℚ) (f^{'} (x) = ⌈ x ⌉)$ .

Hence, either $(\forall x \in ℚ) (f (x) = ⌊ x ⌋)$ or $(\forall x \in ℚ) (f^{'} (x) = ⌈ x ⌉)$ , as we needed to show.
□

______________________________________________________________________________________________________________________________

[P. Eisele and K. P. Hadeler, AMM 97 (1990), 475–477.]

[G. Hamel, Math. Annalen 60 (1905), 459–462.]