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

• songoku

#### 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

songoku said:
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
Delta2 said:
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

songoku said:
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

songoku said:
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
songoku said:
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
PeroK said:
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

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

• songoku
songoku said:
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
PeroK said:
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

songoku said:
The expression would be: ##n^2 = 2a## where ##a## is integer?

Thanks
Do you know what a prime factorisation is?

• songoku
PeroK said:
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

songoku said:
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
songoku said:
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
Delta2 said:
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##?

songoku said:
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
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
anuttarasammyak said:
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.

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
PeroK said:
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
Delta2 said:
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
• 