TMUA Paper 2: Mathematical proof, set 2

• Answer all questions. No calculator.
• Each question has exactly one correct answer.

1. 11 mark

   A student wants to prove: 'The sum of any two consecutive odd integers is divisible by 4.' Which of the following is a valid direct proof?

   1. A Let the two consecutive odd integers be n and n + 1, where n = 2k + 1 for integer k. Then their sum is n + (n + 1) = 2n + 1 = 2(2k + 1) + 1 = 4k + 3, which is of the form 4k + 3, so divisible by 4.
   2. B Let the two consecutive odd integers be n and n + 2, where n = 2k + 1 for integer k. Then their sum is n + (n + 2) = 2n + 2 = 2(2k + 1) + 2 = 4k + 4 = 4(k + 1), which is divisible by 4.
   3. C Let the two consecutive odd integers be n and n + 2, where n = 2k for integer k. Then their sum is n + (n + 2) = 4k + 2 = 2(2k + 1), which is divisible by 4 because 2k + 1 is an integer.
   4. D Let the two consecutive odd integers be n and n + 2, where n = 2k + 1 for integer k. Then their sum is n + (n + 2) = 2n + 2, which is even, and every even number is divisible by 4, so the sum is divisible by 4.
2. 21 mark

   A student wants to prove: 'The difference between the squares of any two consecutive integers is odd.' Which of the following is a valid direct proof?

   1. A Let the two consecutive integers be n and n + 1. Then (n + 1)^2 - n^2 = (n^2 + 2n + 1) - n^2 = 2n + 1, which is odd, since it has the form 2n + 1 with n an integer.
   2. B Let the two consecutive integers be n and n + 1. Then (n + 1)^2 - n^2 = n^2 + 1 - n^2 = 1, which is odd.
   3. C Let the two consecutive integers be n and n + 2. Then (n + 2)^2 - n^2 = (n^2 + 4n + 4) - n^2 = 4n + 4 = 4(n + 1), which is odd because n + 1 is an integer.
   4. D Let the two consecutive integers be n and n + 1. Then (n + 1)^2 - n^2 = 2n + 1. Since 2n is even, 2n + 1 is even plus 1, so the difference could be odd or even depending on n.
3. 31 mark

   A student wants to prove: '|n| + n is even for every integer n.' Which of the following is a valid proof by cases?

   1. A Case n >= 0: |n| = n, so |n| + n = 2n, which is even. Case n < 0: |n| = n, so |n| + n = 2n, which is even. Since every integer satisfies one of these, |n| + n is even for every integer n.
   2. B Case n >= 0: |n| = n, so |n| + n = 2n, which is even. Since this covers the case n >= 0, |n| + n is even for every integer n.
   3. C Case n >= 0: |n| = n, so |n| + n = 2n, which is even. Case n < 0: |n| = -n, so |n| + n = -n + n = 0, which is even. Every integer is either non-negative or negative, and both cases give an even result, so |n| + n is even for every integer n.
   4. D Case n >= 0: |n| = n, so |n| + n = 2n, which is even. Case n < 0: |n| = -n, so |n| + n = -n + n = 0, and since 0 is not positive, it is not even.
4. 41 mark

   A student wants to prove: 'n^2 leaves remainder 0 or 1 when divided by 4, for every integer n.' Which of the following is a valid proof by cases?

   1. A Case n even: n = 2k, so n^2 = 4k^2, which leaves remainder 0 when divided by 4. Case n odd: n = 2k + 1, so n^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1, which leaves remainder 1 when divided by 4. Since every integer is even or odd, and both cases give remainder 0 or 1, n^2 always leaves remainder 0 or 1 when divided by 4.
   2. B Case n even: n = 2k, so n^2 = 4k^2, remainder 0. Case n odd: n = 2k + 1, so n^2 = 4k^2 + 2k + 1, and this expression leaves a remainder that depends on k, so no single remainder can be stated for odd n.
   3. C Case n even: n = 2k, so n^2 = 4k^2, which leaves remainder 0 when divided by 4. This shows n^2 always leaves remainder 0 or 1 when divided by 4.
   4. D Case n even: n = 2k, so n^2 = 4k^2, remainder 0. Case n odd: n = 2k, so n^2 = 4k^2, remainder 0. Since both cases give remainder 0, n^2 always leaves remainder 0 when divided by 4.
5. 51 mark

   In a proof by contradiction that there is no largest prime number, which is the correct starting assumption?

   1. A Assume there is no largest prime number, and derive a contradiction from that.
   2. B Assume that there are only finitely many primes, p_1, p_2, ..., p_n, so that p_n is the largest one, and show this leads to a contradiction.
   3. C Assume every prime number is odd, and show this is impossible.
   4. D Assume some prime number p is larger than every other prime number and every composite number, and show no such number exists.
6. 61 mark

   A student wants to prove: 'If n^2 is even, then n is even.' Which of the following is a valid proof by contradiction?

   1. A Assume, for contradiction, that n^2 is even but n is odd. Since n is odd, write n = 2k + 1, so n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1, which is odd. This contradicts n^2 being even, so n must be even.
   2. B Assume, for contradiction, that n is odd. Since n is odd, n^2 is odd (odd x odd = odd). This shows n^2 is odd, which is what we wanted to prove.
   3. C Assume, for contradiction, that n^2 is odd and n is even. Since n is even, write n = 2k, so n^2 = 4k^2, which is even. This contradicts n^2 being odd, so n must be odd.
   4. D Assume, for contradiction, that n^2 is even but n is odd. Since n is odd, write n = 2k + 1, so n^2 = 4k^2 + 4k + 1. Since 4k^2 + 4k is even, n^2 is even, which is what we assumed, so there is no contradiction and the proof fails.
7. 71 mark

   A student claims: 'For every positive integer n, 2^n + 1 is prime.' Which of the following correctly disproves this claim?

   1. A n = 1: 2^1 + 1 = 3, which is prime, so n = 1 disproves the claim.
   2. B n = 2: 2^2 + 1 = 5, which is odd, so it is not prime, so n = 2 disproves the claim.
   3. C n = 4: 2^4 + 1 = 17, which is prime, so n = 4 disproves the claim.
   4. D n = 3: 2^3 + 1 = 9 = 3 x 3, which is not prime, so n = 3 disproves the claim.
8. 81 mark

   A student claims: 'If a and b are integers with a < b, then a^2 < b^2.' Which of the following correctly disproves this claim?

   1. A a = 1, b = 2: a < b, and a^2 = 1 < 4 = b^2, so this disproves the claim.
   2. B a = -2, b = -1: a < b (-2 < -1), and a^2 = 4, b^2 = 1, so a^2 > b^2, but since both are negative the claim does not apply here, so this does not count as a counterexample.
   3. C a = -3, b = 1: a < b (-3 < 1), and a^2 = 9, b^2 = 1, so a^2 = 9 > 1 = b^2, violating a^2 < b^2, so this disproves the claim.
   4. D a = 2, b = 3: a < b, and a^2 = 4 < 9 = b^2, as claimed; however since 4 and 9 are both perfect squares this is a special case, so it disproves the claim.
9. 91 mark

   You are told: 'If a number is a multiple of 8, then it is a multiple of 4' and '60 is a multiple of 4.' Which of the following can be validly deduced?

   1. A 60 is a multiple of 8.
   2. B Nothing about whether 60 is a multiple of 8 follows from these two statements alone.
   3. C 60 is not a multiple of 8.
   4. D Every multiple of 4 is a multiple of 8.
10. 101 mark

    By evaluating 1, 1 + 4, 1 + 4 + 9, 1 + 4 + 9 + 16 (giving 1, 5, 14, 30), a student conjectures a formula for the sum of the squares of the first n positive integers. Which of the following gives both the correct conjecture and a valid justification for every n, not just the four cases checked?

    1. A Conjecture: the sum of the squares of the first n positive integers is n(n + 1)(2n + 1)/6. Justification: the values 1, 5, 14, 30 match n(n + 1)(2n + 1)/6 for n = 1, 2, 3, 4, and since the pattern holds for these four cases, it must hold for every n.
    2. B Conjecture: the sum of the squares of the first n positive integers is [n(n + 1)/2]^2. Justification: substituting n = 1, 2, 3, 4 into [n(n + 1)/2]^2 gives 1, 9, 36, 100, which matches the observed sums 1, 5, 14, 30.
    3. C Conjecture: the sum of the squares of the first n positive integers is n(n + 1)/2. Justification: since the sum of the first n positive integers is n(n + 1)/2, and each term being added is a square, the sum of their squares must also be n(n + 1)/2.
    4. D Conjecture: the sum of the squares of the first n positive integers is n(n + 1)(2n + 1)/6. Justification: this can be proved by mathematical induction. It holds for n = 1, since 1 x 2 x 3 / 6 = 1. If it holds for n = k, then adding (k + 1)^2 to both sides gives k(k + 1)(2k + 1)/6 + (k + 1)^2 = (k + 1)(2k^2 + 7k + 6)/6 = (k + 1)(k + 2)(2k + 3)/6, which is exactly the formula with k + 1 in place of k. Since it holds for n = 1 and holding for n = k always gives it for n = k + 1, it holds for every positive integer n.
11. 111 mark

    A student is asked to prove: 'If n is a multiple of 4, then n^2 is a multiple of 16.' The proof has been written as four separate lines, given here in a scrambled order:

    W: So n^2 = (4k)^2 = 16k^2.

    X: Suppose n is a multiple of 4, so n = 4k for some integer k.

    Y: Since k^2 is an integer, n^2 is 16 times an integer, so n^2 is a multiple of 16.

    Z: Therefore, if n is a multiple of 4, then n^2 is a multiple of 16, as required.

    Which order of these four lines gives a valid direct proof?

    1. A X, W, Y, Z
    2. B W, X, Y, Z
    3. C X, Y, W, Z
    4. D X, W, Z, Y
12. 121 mark

    Suppose n is a positive integer for which n^2 - n is divisible by 6. Which of the following must be true?

    1. A n must be even.
    2. B n must be a multiple of 3.
    3. C n leaves a remainder of 0 or 1 when divided by 3.
    4. D n leaves a remainder of 1 or 2 when divided by 3.

Worked solutions

Every question below carries the reasoning, not just the answer. The official material for this test publishes a correct option letter and nothing else.

1. Question 1Answer: B

   1. To prove a statement about two consecutive odd integers, write the first as n = 2k + 1 for integer k, and the second, two more than the first, as n + 2 = 2k + 3.
   2. Their sum is (2k + 1) + (2k + 3) = 4k + 4 = 4(k + 1).
   3. Since k + 1 is an integer, this shows the sum is exactly 4 times an integer, that is, divisible by 4.
   4. This chain is valid for every integer k, giving a complete direct proof, so the answer is B.
   • Why not A: Treats n + 1, rather than n + 2, as the next odd integer; since n is odd, n + 1 is even, so this pair are not both odd, and the resulting expression 4k + 3 does not even reach the correct form.
   • Why not C: Uses n = 2k, the algebraic form for an even integer, to represent what is claimed to be the odd number n, so the case being tested is not actually two odd integers; separately, 2(2k + 1) shows only divisibility by 2, since 2k + 1 need not itself be even, not divisibility by 4.
   • Why not D: Asserts that every even number is divisible by 4, which is false in general (6 is even but not a multiple of 4), so the final deduction does not follow even though the setup up to that point is correct.

2. Question 2Answer: A

   1. Represent two consecutive integers as n and n + 1.
   2. Expand (n + 1)^2 correctly: (n + 1)^2 = n^2 + 2n + 1, so the difference (n + 1)^2 - n^2 = 2n + 1.
   3. 2n is even for any integer n, and an even number plus 1 is always odd, so 2n + 1 is odd for every integer n.
   4. This holds for every n, giving a complete direct proof, so the answer is A.
   • Why not B: Expands (n + 1)^2 as n^2 + 1, omitting the cross term 2n; the correct expansion is n^2 + 2n + 1, and dropping it turns a genuinely variable difference into a constant.
   • Why not C: Uses n and n + 2, which differ by 2 and so are not consecutive integers (they are two integers of the same parity); it also misreads 4(n + 1), an expression that is always a multiple of 4 and therefore always even, as odd.
   • Why not D: Correctly reaches 2n + 1 but then treats 'even plus 1' as if its parity depended on n; adding 1 to any even number always gives an odd number, regardless of which even number 2n is, so the conclusion is certain, not conditional.

3. Question 3Answer: C

   1. Every integer n satisfies exactly one of n >= 0 or n < 0, so these two cases are exhaustive.
   2. Case n >= 0: by definition |n| = n, so |n| + n = 2n, which is even since n is an integer.
   3. Case n < 0: by definition |n| = -n, so |n| + n = (-n) + n = 0, and 0 is even.
   4. Both cases give an even result, so |n| + n is even for every integer n, matching option C.
   • Why not A: Uses |n| = n for the case n < 0 as well as for n >= 0, forgetting that the absolute value flips the sign of a negative number; the negative case is never actually tested.
   • Why not B: Tests only the case n >= 0 and never examines n < 0; a proof by cases must dispose of every case, and leaving one untested makes the proof incomplete regardless of whether the conclusion happens to be true.
   • Why not D: Correctly computes |n| + n = 0 in the negative case, but then wrongly claims 0 is not even because it is not positive; 0 is even, since 0 = 2 x 0, and evenness has nothing to do with sign.

4. Question 4Answer: A

   1. Every integer is either even or odd, so these two cases are exhaustive for a statement about all integers.
   2. Case n even: n = 2k, so n^2 = 4k^2, leaving remainder 0 when divided by 4.
   3. Case n odd: n = 2k + 1, so n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 4(k^2 + k) + 1, leaving remainder 1 when divided by 4.
   4. Both cases are covered and each gives remainder 0 or 1, so n^2 always leaves remainder 0 or 1 when divided by 4, matching option A.
   • Why not B: Expands (2k + 1)^2 incorrectly as 4k^2 + 2k + 1 instead of 4k^2 + 4k + 1, an arithmetic slip that loses the correct coefficient of the middle term and obscures that the remainder is always exactly 1 in the odd case.
   • Why not C: Tests only the case n even and never examines n odd, so the case split is not exhaustive; the conclusion 'always 0 or 1' cannot be established from one case alone, even though it happens to be true.
   • Why not D: Uses n = 2k, the algebraic form for an even integer, to represent the case that is supposed to be odd, so the odd case is never actually tested; the resulting claim that n^2 always leaves remainder 0 is false, since 3^2 = 9 leaves remainder 1.

5. Question 5Answer: B

   1. A proof by contradiction begins by assuming the negation of the statement to be proved.
   2. The statement is 'there is no largest prime number'; its negation is 'there is a largest prime number,' equivalently, the primes are exactly p_1, p_2, ..., p_n for some finite n, with p_n the largest.
   3. From this assumption, the classic argument forms N = p_1 x p_2 x ... x p_n + 1 and shows N has a prime factor not among p_1, ..., p_n, contradicting that the list was complete.
   4. The correct starting assumption is therefore option B.
   • Why not A: Assumes the statement to be proved, 'there is no largest prime,' rather than its negation; a proof by contradiction must start from the opposite of the target statement, namely that a largest prime does exist.
   • Why not C: Is not the negation of 'there is no largest prime number.' Whether every prime is odd is a different question entirely (and false, since 2 is prime and even), so refuting it says nothing about whether a largest prime exists.
   • Why not D: Confuses 'the largest prime number' with 'the largest number of any kind'; since composite numbers are unbounded, no number is larger than every composite number, so this assumption is about the wrong quantity and does not correctly negate the original statement, which only concerns primes.

6. Question 6Answer: A

   1. To prove 'if n^2 is even then n is even' by contradiction, assume the hypothesis holds and the conclusion fails: n^2 is even, but n is odd.
   2. Since n is odd, write n = 2k + 1, so n^2 = (2k + 1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.
   3. This expresses n^2 as an even number plus 1, so n^2 is odd.
   4. This contradicts the assumption that n^2 is even, so the assumption 'n is odd' must be false, and n is even, matching option A.
   • Why not B: Never uses the assumption that n^2 is even; it only shows odd implies odd-squared, which does not address the conditional 'if n^2 is even then n is even' at all, since the hypothesis of that conditional is left untouched.
   • Why not C: Negates the wrong statement: to prove 'if n^2 is even then n is even' by contradiction, one must assume the hypothesis (n^2 is even) together with the negation of the conclusion (n is odd), not swap both parts; this option in fact addresses a different, though related, statement.
   • Why not D: Correctly reaches 4k^2 + 4k + 1 but misjudges its parity: 4k^2 + 4k is even, so 4k^2 + 4k + 1 (even plus 1) is odd, not even; the arithmetic itself is right but the parity conclusion drawn from it is wrong, which is exactly the contradiction the proof needs.

7. Question 7Answer: D

   1. To disprove 'for every positive integer n, 2^n + 1 is prime,' it suffices to exhibit one positive integer n where the expression is not prime.
   2. Testing n = 3: 2^3 + 1 = 8 + 1 = 9.
   3. 9 = 3 x 3, so 9 is composite, not prime.
   4. n = 3 is a positive integer for which the expression fails to be prime, a valid counterexample, so the answer is D.
   • Why not A: n = 1 gives 3, which is prime; a counterexample to 'the expression is always prime' must be a value where the expression is NOT prime, so a value that keeps it prime supports the claim rather than disproving it.
   • Why not B: Argues 5 is not prime because it is odd; being odd does not make a number non-prime, since most primes are odd, and 5 is in fact itself prime, so this does not disprove the claim at all.
   • Why not C: n = 4 gives 17, which is prime; like option A, this keeps the pattern intact for this value rather than breaking it, so it cannot serve as a counterexample.

8. Question 8Answer: C

   1. To disprove 'if a < b then a^2 < b^2' for integers a and b, it suffices to find one pair with a < b but a^2 not less than b^2.
   2. Let a = -3 and b = 1. Then a < b, since -3 < 1.
   3. Compute a^2 = 9 and b^2 = 1.
   4. Since 9 is not less than 1, the inequality a^2 < b^2 fails for this pair, giving a valid counterexample, so the answer is C.
   • Why not A: Gives a = 1, b = 2, where a^2 = 1 < 4 = b^2, exactly consistent with the claim; a counterexample must show the inequality failing, and this pair keeps it holding, so it does not disprove anything.
   • Why not B: Correctly computes a^2 = 4 > 1 = b^2 for a = -2, b = -1, which does violate the claimed inequality and so is in fact a valid counterexample; but it then wrongly insists the claim 'does not apply' to negative integers, even though the claim as stated places no such restriction, so it fails to recognise its own correct counterexample.
   • Why not D: Gives a = 2, b = 3, where a^2 = 4 < 9 = b^2, which is again consistent with the claim rather than violating it; describing this as a special case that 'disproves' the claim confuses a supporting example with a counterexample.

9. Question 9Answer: B

   1. The given conditional has the form 'if A then B,' with A = multiple of 8 and B = multiple of 4.
   2. We are told B holds (60 is a multiple of 4), which is the consequent of the conditional, not its antecedent.
   3. Knowing the consequent of 'if A then B' holds does not let you validly conclude anything about A: affirming the consequent is not a valid rule of deduction, since other numbers could satisfy B without satisfying A.
   4. So from these two statements alone, nothing about whether 60 is a multiple of 8 can be validly deduced, matching option B (checking 60 directly against 8 is a separate calculation, not a deduction from the given statements).
   • Why not A: Commits the fallacy of affirming the consequent: from 'if A then B' and 'B,' one cannot conclude 'A.' Some multiples of 4, such as 8 or 24, are also multiples of 8, but others, such as 12 or 60, are not, so 'multiple of 4' alone never settles whether the number is a multiple of 8.
   • Why not C: Also goes further than the given premises allow: knowing 60 is a multiple of 4 does not, by itself, rule out it also being a multiple of 8 in general, since some multiples of 4 are multiples of 8; that 60 specifically is not a multiple of 8 is a fact about 60, not something the two given logical statements deliver.
   • Why not D: States the converse of the given conditional as if it were equivalent to it; 'if A then B' does not imply 'if B then A,' and this converse is false in any case, since 12 is a multiple of 4 but not of 8.

10. Question 10Answer: D

    1. Listing the sums 1, 1 + 4 = 5, 1 + 4 + 9 = 14, 1 + 4 + 9 + 16 = 30 suggests the conjecture that the sum of the squares of the first n positive integers is n(n + 1)(2n + 1)/6 (this gives 1, 5, 14, 30 for n = 1, 2, 3, 4, as required).
    2. To justify this beyond four cases, prove it by mathematical induction. Base case n = 1: n(n + 1)(2n + 1)/6 = 1 x 2 x 3 / 6 = 1, which matches 1^2 = 1.
    3. Inductive step: assume the formula holds for n = k, so 1^2 + ... + k^2 = k(k + 1)(2k + 1)/6. Adding (k + 1)^2 to both sides gives k(k + 1)(2k + 1)/6 + (k + 1)^2 = (k + 1)[k(2k + 1) + 6(k + 1)]/6 = (k + 1)(2k^2 + 7k + 6)/6 = (k + 1)(k + 2)(2k + 3)/6, which is the formula with n = k + 1 in place of k.
    4. Since the formula holds for n = 1, and holding for n = k implies it holds for n = k + 1, it holds for every positive integer n by induction, matching option D.
    • Why not A: States the correct formula n(n + 1)(2n + 1)/6, but the justification only checks four small cases and then asserts the pattern 'must hold' for every n with no general argument; agreement on finitely many cases suggests a conjecture but does not by itself prove it.
    • Why not B: Confuses the sum of squares with the sum of cubes: [n(n + 1)/2]^2 is in fact the formula for 1^3 + 2^3 + ... + n^3, not for 1^2 + 2^2 + ... + n^2. Substituting n = 1, 2, 3, 4 gives 1, 9, 36, 100, which agrees with the observed sums only at n = 1 and disagrees from n = 2 onward (9, not 5; 36, not 14; 100, not 30), so the claimed match is false.
    • Why not C: Assumes that because each term is a square, the sum of the squares must obey the same formula as the sum of the plain integers; n(n + 1)/2 is the formula for 1 + 2 + ... + n, and substituting n = 1, 2, 3, 4 gives 1, 3, 6, 10, not the observed sums 1, 5, 14, 30.

11. Question 11Answer: A

    1. A direct proof of an 'if... then...' statement should begin by assuming the hypothesis: line X, 'Suppose n is a multiple of 4, so n = 4k for some integer k.'
    2. The next step performs the algebra that follows from this assumption: line W, 'So n^2 = (4k)^2 = 16k^2.'
    3. Then the reasoning explains why this form gives the desired property: line Y, 'Since k^2 is an integer, n^2 is 16 times an integer, so n^2 is a multiple of 16.'
    4. Finally the overall conditional conclusion is stated: line Z, giving the order X, W, Y, Z, which is option A.
    • Why not B: Opens with W, 'n^2 = (4k)^2 = 16k^2,' before the assumption in X has introduced k at all; the algebraic step must come after the assumption that defines k, not before it.
    • Why not C: States the conclusion in Y, 'n^2 is a multiple of 16,' immediately after the assumption in X, before the algebraic step in W that actually justifies it; the working must precede the claim it supports.
    • Why not D: Places the final conclusion in Z before the line in Y that explains why 16k^2 makes n^2 a multiple of 16; the overall conclusion should come last, after every supporting step.

12. Question 12Answer: C

    1. n^2 - n = n(n - 1), the product of two consecutive integers, is always even, since one of any two consecutive integers is even, so divisibility by 2 is automatic and never the deciding factor.
    2. Divisibility by 6 therefore comes down to divisibility by 3, which depends on the remainder of n when divided by 3, so check each of the three residue classes.
    3. Remainder 0 (n = 3k): n - 1 = 3k - 1, and n(n - 1) = 3k(3k - 1), a multiple of 3. Remainder 1 (n = 3k + 1): n - 1 = 3k, and n(n - 1) = (3k + 1)(3k) = 3k(3k + 1), a multiple of 3. Remainder 2 (n = 3k + 2): n - 1 = 3k + 1, and n(n - 1) = (3k + 2)(3k + 1) = 9k^2 + 9k + 2, which leaves remainder 2 when divided by 3, not a multiple of 3.
    4. So n^2 - n is divisible by 6 exactly when n leaves remainder 0 or 1 on division by 3, which is option C; checking every residue class is needed here because no single small example settles the general claim.
    • Why not A: Checking n = 3 might tempt an even/odd rule, but n = 3 is odd and satisfies the condition (3^2 - 3 = 6, divisible by 6), while n = 2 is even and fails (2^2 - 2 = 2, not divisible by 6); the condition does not depend on the parity of n at all, since n(n - 1) is always even regardless.
    • Why not B: Assumes that for n^2 - n to be divisible by 6, n itself must be a multiple of 3; but n = 1 satisfies the condition (1^2 - 1 = 0, divisible by 6) despite not being a multiple of 3, so this is not merely unproven, it is false.
    • Why not D: Swaps one of the two correct residues for an incorrect one: n leaving remainder 2 when divided by 3, such as n = 2 or n = 5, gives n^2 - n equal to 2 or 20, neither divisible by 6; remainder 2 is exactly the residue for which the condition fails, not one for which it holds.