COMPSCI 250: Homework 3 Solved

Description

(15 points) Problem 3.1.4

The least common multiple of two naturals x and y is the smallest natural that both x and y divide. For example, lcm(8, 12) = 24 because 8 and 12 each divide 24, and there is no smaller natural that both 8 and 12 divide.

1. Find the least common multiple of 60 and 339.

2. Find the least common multiple of 2³3²5⁴ and 2²3⁴5³.

3. Describe a general method to find the least common multiple of two naturals, given their factorization into primes (and assuming that the factorization exists and is unique).

(15 points) Problem 3.3.4

We have defined the factorial n! of a natural n to be the product of all the naturals from 1 through n, with 0! being defined as 1. Let p be an odd prime number. Prove that (p − 1)! is congruent to −1 modulo p. (Hint: Pair as many numbers as you can with their multiplicative inverses.)

(17 points) Problem 3.5.4

Suppose that the naturals m₁, . . . , m_k are pairwise relatively prime and that for each i from 1 through k, the natural x satisfies x ≡ x_i (mod m_i) and the natural y satisfies y ≡ y_i (mod m_i). Explain why for each i, xy satisfies xy ≡ x_iy_i (mod m_i) and x + y satisfies (x + y) ≡ (x_i + y_i) (mod m_i). Now suppose that z₁, · · · , z_j are some naturals and that we have an arithmetic expression in the z_i’s (a combination of them using sums and products) whose result is guaranteed to be less than M, the product of the m_i’s. Explain how we can compute the exact result of this arithmetic expression using the Chinese Remainder Theorem only once, no matter how large j is.

(8 points) Problem 4.1.6

(uses Java) Give a recursive definition of and a recursive static method for the natural subtraction function, with pseudo-Java header

natural minus (natural x, natural y).

On input x and y this function returns x−y if this is a natural (i.e., if x ≥ y) and 0 otherwise.

(15 points) Problem 4.3.2

Let the finite sequence a₀, a₁, · · · , a_n be defined by the rule a_i = b + i · c. Prove by induction on n that the sum of the terms in the sequence is (n + 1)(a₀ + a_n)/2. (Hint: In the base case, n = 0 and so a₀ is equal to a_n. For the induction case, note that the sum for n + 1 is equal to the sum for n plus the one new term a_n+1.)

(15 points) Problem 4.3.6

Define S(n) to be the sum, for all i from 1 through n, of _i(i+1)¹ . Prove by induction on all naturals n (including 0) that S(n) = 1 − _n+1¹ .

(15 points) Problem 4.4.1

Consider a variant of Exercise 4.4.3, for $4 and $11 bills (made, we might suppose, by a particularly inept counterfeiter). What is the minimum number k such that you can make up $n for all n ≥ k? Prove that you can do so.

Extra credit:

(10 points) Problem 3.4.6

A Fermat number is a natural of the form F_i = 2²ⁱ + 1, where i is any natural. In 1730 Goldbach used Fermat numbers to give an alternate proof that there are infinitely many primes.

1. List the Fermat numbers F₀, F₁, F₂, F₃, and F₄,

2. Prove that for any n the product F₀ · F₁ · … · F_n is equal to F_n+1 − 2.

3. Argue that no two different Fermat numbers can share a prime factor. Since there are infinitely many Fermat numbers, there must thus be infinitely many primes.

3