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

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 Helper
Gold Member
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
Homework Helper
Gold Member
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
Homework Helper
Gold Member
2020 Award
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.

songoku and Delta2
pasmith
Homework Helper
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
Gold Member
It is easy to prove the contraposition, i.e. let n be an odd number, n^2 is also an odd number.

songoku
PeroK
Homework Helper
Gold Member
2020 Award
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
Homework Helper
Gold Member
2020 Award
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
Homework Helper
Gold Member
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##?

songoku and PeroK
PeroK
Homework Helper
Gold Member
2020 Award
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
Homework Helper
Gold Member
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

songoku
anuttarasammyak
Gold Member
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##.

songoku
PeroK
Homework Helper
Gold Member
2020 Award
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
Homework Helper
Gold Member
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...

songoku
anuttarasammyak
Gold Member
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

Delta2
Steve4Physics
Homework Helper
Gold Member