Exercises 33 Exercises (1) a) Let C(M, N) denote the binomial coefficient 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].
Previous Page Next Page