Thread: proof

If n is an integer that is NOT a multiple of 3, then n^2 = 1 mod 3

I did ...

to the contrary, if n is a multiple of 3 then n = 0 mod 3

then n^2 is also a multiple of 3 -> n^2 = 0 mod3 reaching a contradition

---> <---- therefore n^2 = 1mod 3 when n is not a multiple of 3. QED.

Is this correct?

Originally Posted by smoothi963

If n is an integer that is NOT a multiple of 3, then n^2 = 1 mod 3

I did ...

to the contrary, if n is a multiple of 3 then n = 0 mod 3

then n^2 is also a multiple of 3 -> n^2 = 0 mod3 reaching a contradition

---> <---- therefore n^2 = 1mod 3 when n is not a multiple of 3. QED.

Is this correct?

i'm afraid not. first of all, you made no assumption that n^2 was not 0 mod 3 so the contradiction doesn't really stand.

note that you have an implication, that is, P => Q, you proved ~P=>~Q, which is not really a valid proof of P=>Q

Originally Posted by smoothi963

If n is an integer that is NOT a multiple of 3, then n^2 = 1 mod 3

I did ...

to the contrary, if n is a multiple of 3 then n = 0 mod 3

then n^2 is also a multiple of 3 -> n^2 = 0 mod3 reaching a contradition

---> <---- therefore n^2 = 1mod 3 when n is not a multiple of 3. QED.

Is this correct?

Try one of these:

We show that if n is an integer that is NOT a multiple of 3, then n^2 = 1 mod 3.

Proof:

Assume n is not a multiple of 3, then we have two cases, n = 3k + 1 for some integer k, or n = 3m + 2 for some integer m.

case 1: n = 3k + 1

if n = 3k + 1, then n^2 - 1 = (3k + 1)^2 - 1 = 9k^2 + 6k + 1 - 1 = 9k^2 + 6k = 3(3k^2 + 2k).

since 3k^2 + 2k is an integer, 3 | n^2 - 1. this means n^2 = 1 mod 3 ...note, 3 | n^2 - 1 means "3 divides n^2 - 1"

case 2: n = 3m + 2

if n = 3m + 2, then n^2 - 1 = (3m + 2)^2 - 1 = 9m^2 + 12m + 4 - 1 = 3(3m^2 + 4m + 1)

since 3m^2 + 4m + 1 is an integer, 3 | n^2 - 1. this means n^2 = 1 mod 3

so we see in both cases where n is not a multiple of 3, n^2 = 1 mod 3

QED


Alternate proof:

Assume n is not a multiple of 3, then n = 1 mod 3 or n = 2 mod 3.

case 1: n = 1 mod 3

if n = 1 mod 3, then n^2 = 1^2 mod 3, so n^2 = 1 mod 3

case 2: n = 2 mod 3

if n = 2 mod 3, then n^2 = 2^2 mod 3, so n^2 = 4 mod 3, which is the same as saying n^2 = 1 mod 3 (do you know why?)

so in both cases where n is not a multiple of 3, we have n^2 = 1 mod 3

QED


I'm sure that the first proof is valid, for the second, it depends on whether or not you can square both sides of a congruence modulus, which i think you can, but i'm not sure, i rarely work in modulus, i usually translate to algebra and manipulate and then translate back, similar to what i did in the first

If you still insist on doing it by contradiction this is how:

for an implication P=>Q, a proof by contradiction means we assume P is true and Q is false and show that a contradiction results. that is, we show

(P and ~Q)=>C

where C is a contradiction