Exercises 33

Exercises

(1) a) Let C(M, N) denote the binomial coeﬃcient M choose N. Find the

prime factorization of C(2N, N).

b) Find a good upper bound for C(2N, N).

c) Use a) and b) to show that ϑ(x) = O(x).

(2) Calculate lcm[1, 2,...,N] in terms of ψ(N).

(3) You are offered to make bets in favor of integers being squares. Integers

n are drawn at random from the interval

x−x3/4

n ≤ x for some fixed

very large x. Each time n is a square, you win 1.5

x1/2

dollars. Each

time it is not, you lose one dollar. Should you accept these bets?

(4) Prove the infinitude of primes by first proving the infinitude of squarefree

numbers (J. Perrott.)

(5) Use the formula

n≤x

ψ

x

n

= T(x)

to prove that a ≤ 1 ≤ A and thus show that if ψ(x)/x has a limit as

x → ∞, that limit must equal 1 (Chebyshev.)

(6) Let A ⊆ Z and denote by NA(x) the number of elements a ∈ A with

|a| ≤ x. Show that if NA(x) grows faster than any power of log(x), the

total set of prime divisors of the elements of A is infinite. Show that if c

is any positive constant, the total set of prime divisors of the sequence

[exp(logc(n))]

for n = 1, 2, 3,... is infinite. (Hint: The Fundamental

Theorem of Arithmetic in logarithmic form.)

(7) † Let N(a, b, c) denote the number of solutions of the inequality ak +

bm ≤ c in nonnegative integers k and m. Express N(a, b, c) in terms of

sums involving the integer part function and establish the estimate

N(a, b, c) −

1

2

c

a

+ 1

c

b

+ 1 ≤

1

2

+

3c

4a

+

3c

4b

when a, b and c are positive real numbers. About how many positive

integers less than or equal to x are there of the form 2k·3m when x is

large?

(8) Show that n! is never a square for n ≥ 2.

(9) Let n be an arbitrary positive integer. Show that counted with mul-

tiplicity every prime occurs at least as often in total as a factor of the

integers in the interval [n+1, 2n] as it does of the integers in the interval

[1,n].