Prove that if n^2 is a multiple of 2, then n is multiple of 2

[songoku]

Homework Statement

Prove that if $n^2$ is multiple of 2 then n is multiple of 2 (n is integer)

Relevant Equations

Multiple of 2 = 2k

This is what I did:

If n is multiple of 2, then n can be stated in the form of 2k, where k is integer. So:
$$n^2=(2k)^2=4k^2=2(2k^2)$$ means that $n^2$ is multiple of 2

But I am pretty sure my working is wrong because I think what I did is the other way around, proving $n^2$ is multiple of 2 if $n$ is multiple of 2

How to do direct proof for this question? Thanks

 

[Delta2]

Homework Statement:: Prove that if $n^2$ is multiple of 2 then n is multiple of 2 (n is integer)
Relevant Equations:: Multiple of 2 = 2k

But I am pretty sure my working is wrong because I think what I did is the other way around, proving n2 is multiple of 2 if n is multiple of 2

Yes that's exactly what you did so you proved nothing towards the wanted.

To prove that if $n^2$ is even then $n$ is also even , use proof by contradiction: Assume that $n$ is not even and hence it will be $n=2k+1$. Then use this to prove that $n^2=2m+1$ for some $m(k)$, hence $n^2$ is not even either which is a contradiction.

 

[songoku]

To prove that if $n^2$ is even then $n$ is also even , use proof by contradiction: Assume that $n$ is not even and hence it will be $n=2k+1$. Then use this to prove that $n^2=2m+1$ for some $m(k)$, hence $n^2$ is not even either which is a contradiction.

Is there maybe a way to do direct proof for this question, not using contradiction?

Thanks

 

[Delta2]

Is there maybe a way to do direct proof for this question, not using contradiction?

Thanks

None that I know of. We basically use the fact that if it is not even then it is odd, and there is no other option, that is that the set of natural numbers splits to the set of evens and the set of odds. Even if there is some other proof (maybe using induction) it will use this fact.

 

[songoku]

Thank you very much Delta2

 

[PeroK]

Is there maybe a way to do direct proof for this question, not using contradiction?

Thanks

There a direct proof by considering prime factorisation.

$2$ appears in the prime factorisation of $n^2$ iff it appears in the prime factorisation of $n$.

In general, $n^2$ is divisible by $p$ iff $n$ is divisible by $p$, as they have the same prime factors, with $n^2$ having twice the powers.

 

[pasmith]

Homework Statement:: Prove that if $n^2$ is multiple of 2 then n is multiple of 2 (n is integer)
Relevant Equations:: Multiple of 2 = 2k

This is what I did:

If n is multiple of 2, then n can be stated in the form of 2k, where k is integer. So:
$$n^2=(2k)^2=4k^2=2(2k^2)$$ means that $n^2$ is multiple of 2

But I am pretty sure my working is wrong because I think what I did is the other way around, proving $n^2$ is multiple of 2 if $n$ is multiple of 2

How to do direct proof for this question? Thanks

Use the contrapositive: "if P then Q" is equivalent to "if (not Q) then (not P)".

 

[songoku]

There a direct proof by considering prime factorisation.

$2$ appears in the prime factorisation of $n^2$ iff it appears in the prime factorisation of $n$.

In general, $n^2$ is divisible by $p$ iff $n$ is divisible by $p$, as they have the same prime factors, with $n^2$ having twice the powers.

So I only need to write explanation, no need to do any algebraic working?

Maybe something like this:
If $n^2$ is multiple of 2, it means 2 is one of prime factorisation of $n^2$ so $n^2$ is divisible by 2. Since $n^2$ is divisible by 2, this means $n$ is also divisible by 2 so it is proven that $n$ is also multiple of 2.

Thanks

 

[anuttarasammyak]

It is easy to prove the contraposition, i.e. let n be an odd number, n^2 is also an odd number.

 

[PeroK]

So I only need to write explanation, no need to do any algebraic working?

Maybe something like this:
If $n^2$ is multiple of 2, it means 2 is one of prime factorisation of $n^2$ so $n^2$ is divisible by 2. Since $n^2$ is divisible by 2, this means $n$ is also divisible by 2 so it is proven that $n$ is also multiple of 2.

Thanks

I would simply say that $n$ and $n^2$ have the same prime factors. Hence, any prime divides $n$ iff it divides $n^2$.

That's more general than just proving the case for even numbers.

If you want, you can write out the expression for the prime factorisation of $n^2$ and $n$ to support the claim.

 

[songoku]

If you want, you can write out the expression for the prime factorisation of $n^2$ and $n$ to support the claim.

The expression would be: $n^2 = 2a$ where $a$ is integer?

Thanks

 

[PeroK]

The expression would be: $n^2 = 2a$ where $a$ is integer?

Thanks

Do you know what a prime factorisation is?

 

[songoku]

Do you know what a prime factorisation is?

What I know is something like this: Prime factorisation of 15 is 3 x 5

That's why I thought prime factorisation of $n^2$ is 2 x something

 

[Delta2]

That's why I thought prime factorisation of n2 is 2 x something

You can do much better than that. Given the prime factorization of $n$ can you express in terms of it , the prime factorization of $n^2$? Also given the fundamental theorem of number theory, this prime factorization of $n^2$ that you will find is the only one that exists.
(Using your example if 3x5 is the prime factorization of 15, what is the prime factorization of $15^2$?

 

[PeroK]

What I know is something like this: Prime factorisation of 15 is 3 x 5

That's why I thought prime factorisation of $n^2$ is 2 x something

I noticed this is pre-calculus, so perhaps writing down the general prime factorisation of an integer is too advanced.

The important point is to understand at some level that a prime divides $n$ iff it divides $n^2$.

 

[songoku]

You can do much better than that. Given the prime factorization of $n$ can you express in terms of it , the prime factorization of $n^2$? Also given the fundamental theorem of number theory, this prime factorization of $n^2$ that you will find is the only one that exists.
(Using your example if 3x5 is the prime factorization of 15, what is the prime factorization of $15^2$?

Do you mean the prime factorisation of $n^2$ is $2^2 a$?

 

[Delta2]

Do you mean the prime factorisation of $n^2$ is $2^2 a$?

it will prove to be of that form yes, but it is not so obvious as you think

 

[anuttarasammyak]

Say $n^2$ is an even number, n is also even. Because if n is odd, $n^2$ cannot be even.

Say $n^2$ is an even number, n is multiple of 4. Because as mentioned above n is even so n=2m ,$n^2=4m^2$.

 

[PeroK]

Say $n^2$ is an even number, n is also even. Because if n is odd, $n^2$ cannot be even.

Say $n^2$ is an even number, n is multiple of 4. Because as mentioned above n is even so n=2m ,$n^2=4m^2$.

We know this already. We're trying to use prime factorisation as a more general method.

 

[Delta2]

I think @songoku doesn't seem so familiar with some concepts of number theory like the prime factorization, so I wonder if trying to prove this via the prime factorization route is a good idea...

 

[anuttarasammyak]

We know this already. We're trying to use prime factorisation as a more general method.

So I try some generalization.

Say $n^2$ is a multiple of prime number p, n is also its multiple. Because if n is not so, $n^2$ cannot be so neither.

 

[songoku]

I think @songoku doesn't seem so familiar with some concepts of number theory like the prime factorization, so I wonder if trying to prove this via the prime factorization route is a good idea...

Yes, maybe I just drop the idea of prime factorization

I am able to do this question by using contradiction and contrapositive so I think it is enough. Direct proof is only due to my curiosity

Thank you very much for all the help and explanation Delta2, PeroK, pasmith, anuttarasammyak

 

[Steve4Physics]

Removed my reply as it had already been covered by other posts

 

[WWGD]

There is a general definition of a prime : p is a prime if $p|(a \ cdot b)$ then p|a or p|b . Maybe you can use that for p=2. I think this applies to Euclidean Domains/Rings.