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

  • Thread starter songoku
  • Start date
  • #1
1,771
168
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
4,535
1,835
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
1,771
168
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
4,535
1,835
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
1,771
168
Thank you very much Delta2
 
  • #6
PeroK
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
18,172
9,845
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,056
683
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
1,771
168
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,030
472
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
2020 Award
18,172
9,845
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
1,771
168
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
2020 Award
18,172
9,845
The expression would be: ##n^2 = 2a## where ##a## is integer?

Thanks
Do you know what a prime factorisation is?
 
  • #13
1,771
168
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
4,535
1,835
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
2020 Award
18,172
9,845
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
1,771
168
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
4,535
1,835
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,030
472
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
2020 Award
18,172
9,845
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
4,535
1,835
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,030
472
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
1,771
168
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
678
538
Removed my reply as it had already been covered by other posts
 
Last edited:
  • #24
WWGD
Science Advisor
Gold Member
5,631
5,083
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.
 

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

Replies
7
Views
18K
  • Last Post
Replies
15
Views
2K
  • Last Post
Replies
14
Views
17K
  • Last Post
Replies
5
Views
3K
Replies
15
Views
78K
Replies
16
Views
1K
Replies
8
Views
13K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
3
Views
2K
Top