# Thread: [SOLVED] discrete math help

1. ## [SOLVED] discrete math help

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

2. I think you meant n^2 with n2.

Let there be an integer n such that n^2 is divisible by 3 WHILE n itself is not divisible by 3.

Sorry I got to go...
I'll check later...

-O

3. Originally Posted by oswaldo
I think you meant n^2 with n2.

Let there be an integer n such that n^2 is divisible by 3 WHILE n itself is not divisible by 3.

Sorry I got to go...
I'll check later...

-O
The "something about it" would be to consider the prime factor decomposition of n and hence of n^2 ....

4. i understand prime factor decomposition sort of, but i dont understand how to implement it. but thanks for the help so far

5. Originally Posted by last_chance
i understand prime factor decomposition sort of, but i dont understand how to implement it. but thanks for the help so far
Look at some examples.
$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.

$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?

6. 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. (*)

(*) Exactly "one" of three consecutive integers is divisible by 3

-O

7. yah thats what i figured it does clear it up alot thanks. but how do you know that first one is clearly a factor of 3?

8. 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