n = 5k + 2 for some integer k, what is the value of n² mod 5?30⁵ · 40³?m and n are integers with m mod 6 = 3 and n mod 6 = 4. What is (m + n) mod 6?n, if n is divisible by 4, then n is divisible by 2"?x such that x² + 1 = 0". Which of the following best describes this statement?n, n² + 3 is divisible by 4.Proof. Suppose n is a particular but arbitrarily chosen odd integer. [We must show 4 | (n² + 3).]
By definition of odd, n = 2k + 1 for some integer k.
Let t = k² + k + 1. Then t is an integer (sums and products of integers are integers), and n² + 3 = 4t.
By definition of divisibility, 4 | (n² + 3).
Marking guide (4 marks, 1 per criterion).
n = 2k + 1).(2k + 1)² + 3 = 4k² + 4k + 4.4(k² + k + 1).a, b, and c, if a | b and b | c, then a | c.Proof. Suppose a, b, c are particular but arbitrarily chosen integers with a | b and b | c. [We must show a | c.]
By definition of divisibility:
Substituting the first into the second:
Let k = r · s. Then k is an integer (product of integers is an integer), and c = a · k.
By definition of divisibility, a | c.
Marking guide (3 marks, 1 per criterion).
b = ar and c = bs).c = a(rs).rs is an integer, so a | c.d = 3 to prove that for every integer n, the integer n² + 2n has the form 3k or 3k + 2 for some integer k.Proof. Let n be a particular but arbitrarily chosen integer. By the quotient-remainder theorem with d = 3, exactly one of the following holds for some integer q:
Case 1: n = 3q.
Let k = 3q² + 2q (an integer). Then n² + 2n = 3k. Has the form 3k. ✓
Case 2: n = 3q + 1.
Let k = 3q² + 4q + 1 (an integer). Then n² + 2n = 3k. Has the form 3k. ✓
Case 3: n = 3q + 2.
Let k = 3q² + 6q + 2 (an integer). Then n² + 2n = 3k + 2. Has the form 3k + 2. ✓
In every case n² + 2n has the form 3k or 3k + 2 for some integer k.
Marking guide (3 marks, 1 per criterion).
d = 3 to split n into the three cases.n² + 2n in all three cases.3k or 3k + 2) for each case and a clean overall conclusion.Observation. The form 3k + 1 never arises. So in fact a stronger statement holds: n² + 2n mod 3 ∈ {0, 2} for every integer n.
m and n, if m and n are both odd, then m + n is odd".
m + n when m and n are both odd, and prove it.(1) Counterexample. Take m = 1 and n = 3. Both are odd. Their sum is
which is even by definition (witness k = 2), not odd. The hypothesis is true (both are odd) and the conclusion is false (the sum is not odd). One such pair is enough to disprove the universal claim.
Acceptable variants: any specific pair of odd integers whose sum is even, e.g. (1, 1), (3, 5), (−1, 7).
(2) Correct conclusion. "For all integers m and n, if m and n are both odd, then m + n is even."
Proof. Suppose m and n are particular but arbitrarily chosen odd integers. [We must show m + n is even.]
By definition of odd:
Watch. The two witnesses r and s need not be the same. Calling both k is the classic find-the-mistake error.
Then
Let t = r + s + 1. Then t is an integer (sum of integers is an integer), and m + n = 2t.
By definition of even, m + n is even.
Marking guide (4 marks total, 1 per criterion).
m = 2j + 1, n = 2k + 1). Reusing the same letter is the classic trap.m + n = 2 · (integer) and concluding even.r and s, the number r² + s² is a rational number.Proof. Suppose r and s are particular but arbitrarily chosen rational numbers. [We must show r² + s² is rational.]
By definition of rational,
Square each:
Combine over a common denominator:
Let p = a²d² + b²c² and q = b²d².
p is an integer because products and sums of integers are integers.q = b² · d² is an integer for the same reason, and q ≠ 0 because b ≠ 0 and d ≠ 0 imply b² ≠ 0 and d² ≠ 0, hence b²d² ≠ 0 by the zero-product property.So r² + s² = p / q with p, q integers and q ≠ 0. By definition of rational, r² + s² is rational.
Alternative (cite Theorem 4.2.2). Once r² and s² are each shown rational (numerator a square of an integer; denominator a nonzero square), Theorem 4.2.2 (sum of two rationals is rational) finishes the argument in one line.
Marking guide (6 marks, 1 per criterion).
r = a/b, s = c/d, b, d ≠ 0).r² = a²/b² and s² = c²/d²).b²d².a²d² + b²c² is an integer.b²d² is a nonzero integer. This is the point most often missed.S be the set of students at a university and C the set of courses offered. Let E(s, c) denote "student s is enrolled in course c".
∀, ∃, and the predicate E: "There is a course that every student is enrolled in". [3 marks]∀ s ∈ S, ∃ c ∈ C such that E(s, c). [3 marks](1) Symbolic form.
Read: "there exists a course c such that for every student s, s is enrolled in c."
Why this order counts. The course must be fixed first (∃ first), and then it must work for every student (∀ inside). Swapping the order to ∀ s ∃ c, E(s, c) would only say "every student is enrolled in at least one course", a much weaker claim. The two statements have completely different meanings (see Section 3.3, the loves-table examples).
(2) Negation, with no ∼ before any quantifier.
Walk the negation left-to-right, flipping each quantifier and pushing ∼ inside as we go.
Final form:
Read: "there is a student who is not enrolled in any course", equivalently, "some student is enrolled in no course at all".
Marking guide (6 marks total).
Part (1) · 3 marks, 1 per criterion:
∃ c ∈ C.∀ s ∈ S, with proper scope.E(s, c) with arguments in the right order.Part (2) · 3 marks, 1 per criterion:
∀ to ∃.∃ to ∀.∼E(s, c) in the innermost position.p ∨ q
p → r
q → r
∴ r
Three variables p, q, r give 2³ = 8 rows. The premise columns are p ∨ q, p → r, and q → r; the conclusion column is r. A row is critical when all three premises are true. The argument is valid iff the conclusion is true in every critical row.
| p | q | r | p ∨ q | p → r | q → r | ∴ r | critical? |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | yes · conclusion T ✓ |
| T | T | F | T | F | F | F | no |
| T | F | T | T | T | T | T | yes · conclusion T ✓ |
| T | F | F | T | F | T | F | no |
| F | T | T | T | T | T | T | yes · conclusion T ✓ |
| F | T | F | T | T | F | F | no |
| F | F | T | F | T | T | T | no · p ∨ q is F |
| F | F | F | F | T | T | F | no · p ∨ q is F |
Premise columns: p ∨ q, p → r, q → r.
Conclusion column: ∴ r.
Critical rows (all three premises T): rows 1, 3, and 5. In each of those rows the conclusion r is also T.
Explanation. In every row where all three premises hold simultaneously, the conclusion r is also true. There is no critical row in which the conclusion fails, so no counterexample exists. The argument therefore preserves truth.
Recognise the form. This is the inference rule Division into cases (Chapter 2.3, Rule 8): from p ∨ q together with p → r and q → r, conclude r. Once the rule is proven valid by truth table (as above), it can be cited by name in later proofs without re-deriving.
Marking guide (4 marks, 1 per criterion).
p ∨ q, p → r, q → r) and which is the conclusion (r).