Appendix 1: Proofs in Mathematics | A1.6

Question 4

Use proof by contradiction to prove that if for an integer aa, a2a^2 is divisible by 3, then aa is divisible by 3.

Check your answer with HomiSolve it yourself, then let Homi check your steps and spot mistakes.
Solution
Understand the Question
  • In a proof by contradiction, we assume the opposite of what we want to prove and show that this leads to a logical impossibility (contradiction).
  • To prove that aa is divisible by 33, we assume that aa is not divisible by 33.
  • By Euclid's division lemma, any integer aa not divisible by 33 leaves a remainder of 11 or 22, so it can be expressed as a=3k+1a = 3k + 1 or a=3k+2a = 3k + 2.
  • Squaring both forms shows that a2a^2 leaves a remainder of 11 and is never divisible by 33, contradicting the given condition that a2a^2 is divisible by 33.

Step 1 · Assume the Opposite and Formulate Cases

Assume to the contrary that aa is not divisible by 33.

When divided by 33, aa can leave a remainder of either 11 or 22. Therefore, aa can be written in one of two forms for some integer kk:

Case 1: a=3k+1a = 3k + 1

Case 2: a=3k+2a = 3k + 2

Step 2 · Evaluate a2a^2 for Both Cases

For Case 1 (a=3k+1a = 3k + 1)

a2=(3k+1)2=(3k)2+2(3k)(1)+12=9k2+6k+1=3(3k2+2k)+1=3m+1(where m=3k2+2k is an integer)\begin{aligned} a^2 &= (3k + 1)^2 \\ &= (3k)^2 + 2(3k)(1) + 1^2 \\ &= 9k^2 + 6k + 1 \\ &= 3(3k^2 + 2k) + 1 \\ &= 3m + 1 \quad (\text{where } m = 3k^2 + 2k \text{ is an integer}) \end{aligned}

For Case 2 (a=3k+2a = 3k + 2)

a2=(3k+2)2=(3k)2+2(3k)(2)+22=9k2+12k+4=9k2+12k+3+1=3(3k2+4k+1)+1=3n+1(where n=3k2+4k+1 is an integer)\begin{aligned} a^2 &= (3k + 2)^2 \\ &= (3k)^2 + 2(3k)(2) + 2^2 \\ &= 9k^2 + 12k + 4 \\ &= 9k^2 + 12k + 3 + 1 \\ &= 3(3k^2 + 4k + 1) + 1 \\ &= 3n + 1 \quad (\text{where } n = 3k^2 + 4k + 1 \text{ is an integer}) \end{aligned}

Step 3 · Identify Contradiction and Conclude

In both cases, a2a^2 leaves a remainder of 11 when divided by 33, meaning a2a^2 is not divisible by 33.

This contradicts the given fact that a2a^2 is divisible by 33.

Hence, our assumption that aa is not divisible by 33 is false.

Therefore, aa must be divisible by 33.

Answer

Hence proved by contradiction that if a2a^2 is divisible by 33, then aa is divisible by 33.

Common Mistakes
  • Incomplete Cases: Only testing a=3k+1a = 3k + 1 and forgetting that numbers not divisible by 33 can also be of the form a=3k+2a = 3k + 2.
  • Factoring Error in Case 2: Forgetting to split 44 as 3+13 + 1 when factoring out 33 from 9k2+12k+49k^2 + 12k + 4.
  • Wrong Assumption: Assuming the premise (a2a^2 is divisible by 33) is false instead of assuming the negation of the conclusion (aa is not divisible by 33).

More questions in A1.6

Q1

Suppose a+b=c+da + b = c + d, and a<ca < c. Use proof by contradiction to show b>db > d.

Q2

Let rr be a rational number and xx be an irrational number. Use proof by contradiction to show that r+xr + x is an irrational number.

Q3

Use proof by contradiction to prove that if for an integer aa, a2a^2 is even, then so is aa.

[Hint : Assume aa is not even, that is, it is of the form 2n+12n + 1, for some integer nn, and then proceed.]

Q4

Use proof by contradiction to prove that if for an integer aa, a2a^2 is divisible by 3, then aa is divisible by 3.

Q5

Use proof by contradiction to show that there is no value of nn for which 6n6^n ends with the digit zero.

Q6

Prove by contradiction that two distinct lines in a plane cannot intersect in more than one point.

← Back to Appendix 1: Proofs in Mathematics