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

  • Thread starter songoku
  • Start date
  • #1
songoku
2,109
280
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
 

Answers and Replies

  • #2
Delta2
Homework Helper
Insights Author
Gold Member
5,695
2,473
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.
 
  • #3
songoku
2,109
280
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
 
  • #4
Delta2
Homework Helper
Insights Author
Gold Member
5,695
2,473
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.
 
  • #5
songoku
2,109
280
Thank you very much Delta2
 
  • #6
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2021 Award
23,248
14,761
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.
 
  • Like
Likes songoku and Delta2
  • #7
pasmith
Homework Helper
2,435
1,042
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)".
 
  • #8
songoku
2,109
280
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
 
  • #9
anuttarasammyak
Gold Member
1,794
894
It is easy to prove the contraposition, i.e. let n be an odd number, n^2 is also an odd number.
 
  • #10
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2021 Award
23,248
14,761
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.
 
  • #11
songoku
2,109
280
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
 
  • #12
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2021 Award
23,248
14,761
The expression would be: ##n^2 = 2a## where ##a## is integer?

Thanks
Do you know what a prime factorisation is?
 
  • #13
songoku
2,109
280
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
 
  • #14
Delta2
Homework Helper
Insights Author
Gold Member
5,695
2,473
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##?
 
  • Like
Likes songoku and PeroK
  • #15
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2021 Award
23,248
14,761
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##.
 
  • #16
songoku
2,109
280
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##?
 
  • #17
Delta2
Homework Helper
Insights Author
Gold Member
5,695
2,473
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
 
  • #18
anuttarasammyak
Gold Member
1,794
894
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##.
 
  • #19
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2021 Award
23,248
14,761
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.
 
  • #20
Delta2
Homework Helper
Insights Author
Gold Member
5,695
2,473
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...
 
  • #21
anuttarasammyak
Gold Member
1,794
894
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.
 
  • #22
songoku
2,109
280
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 :oldbiggrin:

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
 
  • #23
Steve4Physics
Homework Helper
Gold Member
1,469
1,276
Removed my reply as it had already been covered by other posts
 
Last edited:
  • #24
WWGD
Science Advisor
Gold Member
6,198
7,722
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.
 

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

Replies
15
Views
255
Replies
10
Views
373
Replies
6
Views
312
Replies
10
Views
468
Top