Facts.

No justification is needed for the problems on this page: just answers!

1. Let P (x) be an arbitrary proposition that depends on an integer x.  Suppose that you are trying to prove the claim

Which of the following methods could you use to prove this claim?

(a)  Choose a positive integer x e 勿, and prove that P (x) is true for that value of x. (b)  Show that if P (x) is true, then x > 1.

(c) Assume that x < 1 and that P (x) is false, and deduce a contradiction.

(d) Prove that P (1) is true; then, assume P (k) is true for all 1 < k < n, and use this to show that P (n + 1) must also be true.

[1 mark]

2. What is the smallest natural number with four distinct prime factors?

(a) 30                           (b) 945                         (c)  16                           (d)  210

[1 mark]

3.  Consider the proposition P = - ╱Ax e R, 3y  > 0 e R such that x2   = y、.  Which of the following statements is logically equivalent to P?

(a)  “For any real number x, there is a positive real number y such that x2   y .” (b)  “For any real number x, there is a negative real number y such that x2   y .”

(c)  “There is a real number x such that for every negative real number y , x2   y .”

(d)  “There is a real number x such that for every positive real number y , x2   y .”

[1 mark]

4.  Consider the following process, that takes in an integer n as input:

On which of the following inputs does this process run forever?

(a)  1                             (b) 4                             (c) 6                             (d) 8

[1 mark]

Calculations.

Show your working! Each problem on this page has points awarded for working, as well as

for the right answer.

5. Use the Euclidean algorithm to calculate the GCD of 21 and 13.

Show your working (either by making a table to record values of a, b, q, T throughout this process, or otherwise.)                                                                                                [4 marks]

6.  Create a truth table for the compound proposition (p - q) A (T 4 (-T)). Is this proposition

logically equivalent to (p A q) A T?

[4 marks]

Proofs.

There are          proof-based questions on this test: one on this page and one on the next.

Try to solve them!

We give out partial credit for good-faith attempts, so even if you don’t think you’ve got a

“proof,” do try to explain in your own words what you think is going on.

7. Define the values an  as follows:  let ao  =  1, a1  =  1, and for any n  e N with n  >  1, let an＋1  = an(2) - 2an − 1 .

3 mod 4.

[4 marks]

8. Let G be a graph on n vertices. Suppose that G is connected, that no vertex in G has degree 1, and the product of all of the degrees of the vertices in G is 64.

Prove that G must have an Eulerian circuit. (Note: you are allowed to use any results from class without proof.)                                                                                                 [4 marks]