Solved–Problem Set 2 –Solution

Description

0. [6 marks] divisibility…

Composite(n): \n is greater than 1 and not prime.” for n 2 N. Prove the statements below.

0. 1. [3 marks]

8n 2 N⁺; Composite(n² + 3n + 2)

2. [3 marks]

8n 2 N⁺; Composite(n² + 6n + 5)

2. [21 marks] more gcd!

Let a; b 2 N, assume they are not both 0. Dene L = fn 2 N⁺ : 9x; y 2 Z; n = ax + byg. Prove the claims below, being sure to rst state the claim you are proving in predicate logic, and then to write the complete proof. You may use the result of earlier claims in proving later ones, for example you might use claim (f) to help prove claim (g). Anti-hint: You may not use Claims (1){(6) from Tutorial 4, since you are proving some of them!

2. 1. [3 marks] Claim: L has a minimum element m, i.e. m is no larger than any other element of L. You

may use, without proof, the fact that any non-empty, nite set of real numbers has a minimum element¹

2. 2. [3 marks] Claim: Any multiple km, where k 2 N+, is an element of L.

2. 3. [3 marks] Claim: Any element c 2 L is a multiple of m. Hint: Show that you may assume that c is non-negative, no smaller than m, and then use the Quotient-Remainder Theorem to derive a contradiction.

2. 4. [3 marks] Claim: m divides a and m divides b.

2. 5. [3 marks] Claim: Any natural number n that divides both a and b also divides m.

2. 6. [3 marks] Claim: m is the greatest common divisor of a and b.

2. 7. [3 marks] Claim: If a and b are coprime, i.e. m = gcd a; b = 1, and c 2 Z, and a j bc, then a divides c.

Hint: a j c is equivalent to c 0 (mod a), and 2(f) should be helpful here.

2. [3 marks] a prime example…

Theorem 2.3 established that there are innitely many prime numbers. It seems pretty clear all but one prime number are odd. You can go further:

2. 1. [3 marks] Prove that that the set P = fp j P rime(p) ^ p 3 (mod 4)g is innite.

Hint: Think about the technique of Theorem 2.3, and also that there are other arithmetic manipulations other than adding one, such as multiplying by 4 or even subtracting 1.

4. [7 marks] Function growth. Now let’s leave numbers and talk about functions. Consider the following denition:²

De nition 1. Let f; g : N ! R§0. We say that g is eventually dominated by f if and only if there exists n0 2 R^§0 such that every natural number n greater than or equal to n0 satises g(n) µ f(n).

We can express this denition in a predicate Edom(f; g): \g is eventually dominated by f“, where

f; g : N ! R^§0, in the following way:

EDom(f; g) : 9n0 2 ^R§0; 8n 2 ^N; n § n0 ) g(n) µ f(n)

(a)Let f(n) = 0:5n² and g(n) = 2n + 1650. Prove that g is eventually dominated by f. Do NOT use

part (b) to prove this part; we want to see you construct a proof with concrete numbers rather than the variables you’ll use in part (b).

Hint: pay attention to the order of the quantiers. The rst line of your proof should introduce the variable n0, and give it a concrete value.

(b)Prove the following statement, which is a generalization of the previous part:

8a; b 2 R^§0; g(n) = an + b is eventually dominated by f(n) = 0:5n²:

Hint: you don’t need to pick the \best” n0 here, just pick one that works and makes the proof’s calculations easy for you to work with! Which variables can n0 depend on?