hey I understand how to do a proof by contradiction but i dont know where to start with this question, Use proof by contradiction to show that for all integers n, if n2 is divisible by 3 then n is divisible by
3.
thank you very much
hey I understand how to do a proof by contradiction but i dont know where to start with this question, Use proof by contradiction to show that for all integers n, if n2 is divisible by 3 then n is divisible by
3.
thank you very much
I think you meant n^2 with n2.
For contradiction, start with the opposide of the claim:
Let there be an integer n such that n^2 is divisible by 3 WHILE n itself is not divisible by 3.
Then do something about it
Sorry I got to go...
I'll check later...
-O
Look at some examples.
$\displaystyle n = 2^3 \cdot 3^2 \cdot 5\, \Rightarrow \,n^2 = 2^6 \cdot 3^4 \cdot 5^2$, n squared must have a factor of 3.
$\displaystyle n = 2^3 \cdot 7^2 \cdot 11\, \Rightarrow \,n^2 = 2^6 \cdot 7^4 \cdot 11^2$, n squared cannot have a factor of 3.
Does that help?
Let there be an integer n such that n^2 is divisible by 3 WHILE n itself is not divisible by 3.
n^2 = 3k, where k is an integer
n^2 - 1 = 3k-1, now (3k-1) is not divisible by 3, right?
(n-1)(n+1) = 3k-1
Then we can say:
(n-1) is NOT divisible by 3 AND (n+1) is NOT divisible by 3.
means n is divisible by 3. (*)
=> CONTRADICTION.
(*) Exactly "one" of three consecutive integers is divisible by 3
-O
If you are asking: "why n^2 is divisible by 3" That's our assumption. Starting point.
If you are asking why (n-1) and (n+1) is not divisible by 3? The reason: (n-1)*(n+1) is not divisible by 3. If the result of an integer multiplication is not divisible by 3, then none of its components is divisible by 3.
Finally, (n-1), n, (n+1) are consecutive. One MUST be divisible by 3.
-O