Use proof by contraposition to prove that the following statement is true for all positive integers n:
If n2 is a multiple of 3, then n is a multiple of 3.
hint:
If 3|n^2 then 3|n*n
To prove the statement using proof by contraposition, we need to prove the following equivalent statement:
If n is not a multiple of 3, then n^2 is not a multiple of 3.
Proof:
Let's assume that n is not a multiple of 3. We can express this as n = 3k + r, where k is an integer and r is the remainder when n is divided by 3. The possible remainders can be 0, 1, or 2.
Case 1: r = 0
If r = 0, then n is a multiple of 3. However, we assumed n is not a multiple of 3, which contradicts our initial assumption. Therefore, this case is not possible.
Case 2: r = 1
If r = 1, then we can rewrite n as n = 3k + 1. Substituting this into n^2 gives us:
n^2 = (3k + 1)^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1
Since 3k^2 + 2k is an integer, we can rewrite n^2 as n^2 = 3m + 1, where m is an integer. This shows that n^2 is not a multiple of 3.
Case 3: r = 2
If r = 2, then we can rewrite n as n = 3k + 2. Substituting this into n^2 gives us:
n^2 = (3k + 2)^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1
Since 3k^2 + 4k + 1 is an integer, we can rewrite n^2 as n^2 = 3m + 1, where m is an integer. This shows that n^2 is not a multiple of 3.
In both cases 2 and 3, we have shown that if n is not a multiple of 3 (i.e., it leaves a remainder of 1 or 2 when divided by 3), then n^2 is not a multiple of 3.
Therefore, the statement "If n^2 is a multiple of 3, then n is a multiple of 3" is true for all positive integers n.