(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
n ≤ x for some fixed
very large x. Each time n is a square, you win 1.5
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
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
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 ≤
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
(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