Exercise I

For the following statements A and B, say if A  =⇒ B , B  =⇒ A, A  ⇐⇒ B, or neither. Explain quickly why. No need to be very formal, and you can use anything that you know.

1. A: x ≥ 0, B: x is the square of a real number (here, x is a real number).

2. A: p is prime, B: p is divisible by 2 (here p is an integer).

3. A: p is not prime, B: p is divisible by 2 (here p is an integer).

4. A: a2 + b2  = 10000, B: a and b have the same parity (here, a and b are integers).

5. A: a and b are both prime, B: a + b is prime (here, a and b are integers).

Exercise II

1. Define the terms “perfect square” and “consecutive perfect squares” . Then, show that the difference between consecutive perfect squares is odd.

2. Consider the following definition of the “◁” symbol.

Let x and y be integers. Write x ◁ y if 3x + 5y = 7k for some integer k.

(a) Show that 1 ◁ 5, 3 ◁ 1, and 0 ◁ 7.

(b) Prove that if a ◁ b and c ◁ d, then (a + c) ◁ (b + d).

Exercise III

1. Show that an integer n is odd if and only if 2n + 2 is divisible by 4.

2. Consider a,b,d ∈ Z.  Show that a and b are divisible by d if and only if au + bv is divisible by d for any u,v ∈ Z.

Exercise IV

For each statement below, explain why it is false. If you give a counterexample, make sure your explanation is complete.

1. For any n ∈ N, 22n  + 1 is prime.

2. For all n ∈ N, n2 + n + 41 is prime.

3. The expression ((¬p ∧ q) ∨ ((¬r ∧ p) ∧ ¬p)) is a contradiction.

4. Let a,b ∈ Z. If a|b and b|a, then a = b.

5. Let n ∈ N. If n is not prime, then it has a divisor d with 1 < d < n.