# Prove if $n^2$ is even, then $n$ is even

I'm learning math and it is assumed that $n^2$ is even then I have to prove that $n$ is also even ( n is an integer number ).

I searched online and people were suggesting to prove the other way around which means that if you were to assume that $n$ is odd and $n^2$ is odd then you proved your original one which made no sense. Can someone please elaborate on this and what is the best way to prove that ?

• Do you know how to write an even number? Sep 20, 2017 at 21:14
• You can write an odd number as $2k+1$ where $k$ is an integer. Sep 20, 2017 at 21:15
• you can write an even number by n= 2m. Right?
– user481197
Sep 20, 2017 at 21:33

To prove $P \implies Q$ you can prove $\sim Q \implies \sim P$ - not $Q$ implies not $P$. This is called contraposition. Both statements are equivalent. Here's how we prove the contrapositive.

Let $n = 2j +1$. Squaring gives $n^2 = 4j^2 + 4j + 1 = 2(2j^2 + 2j) +1$. Hence $n^2$ is odd.

This is easier than proving that if $n^2$ is even then $n$ is even.

• oohh so i don't even need to prove n is even, but I can simply use some logic and math to prove that opposite which will automatically prove what I wanted?
– user481197
Sep 20, 2017 at 21:31
• This proves that indeed $n$ is even if its square is even. If we say two statements are equivalent, then they are the "same." I suggest reading on propositional logic, perhaps from a book on writing proofs, to understand this better. Sep 20, 2017 at 21:36
• one last question, wouldn't that be the same as proving " the product of two odd numbers is odd"? because you write here m,n are integers and m=2q +1 and n = 2r +1 and then eventually ending up with 2(2qr+q+r) +1 ? is this the same prove or am i hallucinating?
– user481197
Sep 20, 2017 at 21:40
• Define "same." Here's a sketch: take two odd numbers and multiply. Can you write the product as $2j+1$? I won't provide details. If you want a proof verification, attempt it and pose that as another question with the "proof-verification" tag. Sep 20, 2017 at 21:43
• sorry for not being clear, I don't have a similar question but i just wanted to make sure that I understood and while writing it down it appeared to me that what we did here is actually the same as proving what I just said above. I got lost again because of non-proving what the actual thing is but instead proving something else, where you can conclude from that it is the same.
– user481197
Sep 20, 2017 at 21:47

## Definitions

1. $x\text{ is even} := \exists y[y+y=x]$ (Denote as $E(x)$)
2. $x\text{ is odd} := \exists y[S(y+y)=x]$ (Denote as $O(x)$)

## Axioms

1. $\forall x[S(x) \ne 0]$
2. $\forall x \forall y[S(x)=S(y) \implies x=y]$
3. $\forall x[x+0=x]$
4. $\forall x \forall y[x+S(y)=S(x+y)]$
5. $[\varphi(0) \land [\forall x[\varphi(x) \implies \varphi(S(x))]]] \implies [\forall x \varphi(x)]$
6. $\forall x[x*0=0]$
7. $\forall x\forall y[x*S(y)=(x*y)+x]$

## Part 1: Addition is commutative

Let $\varphi(y)$ denote $\forall x[y+x=x+y]$.

Let $\psi a(y)$ denote $a+y=y+a$.

01. 0+0=0+0                                         =
02. ψ0(0)                                           ψdef 01
03. ψ0(b)                                         assumption
04. 0+b=b+0                                       ψdef 03
05. S(0+b)=S(b+0)                                 = 04
06. 0+S(b)=S(b+0)                                 A4
07. 0+S(b)=S(b)                                   A3
08. 0+S(b)=S(b)+0                                 A3
09. ψ0(S(b))                                      ψdef 08
10. ψ0(b)→ψ0(S(b))                                  →I 03-09
11. ∀x[ψ0(x)→ψ0(S(x))]                              ∀I 10
12. [ψ0(0)]∧[∀x[ψ0(x)→ψ0(S(x))]]                    ∧I 02 12
13. [[ψ0(0)]∧[∀x[ψ0(x)→ψ0(S(x))]]]→[∀xψ0(x)]        A5
14. ∀xψ0(x)                                         MP 12 13
15. ∀x[0+x=x+0]                                     ψdef 14
16. ϕ(0)                                            ϕdef 15
17. ϕ(b)                                          assumption
18. ∀x[b+x=x+b]                                   ϕdef 17
19. 0+S(b)=S(b)+0                                 ∀E 15
20. ψSb(0)                                        ψdef 19
21. ψSb(a)                                      assumption
22. S(b)+a=a+S(b)                               ψdef 21
23. S(b)+S(a)=S(S(b)+a)                         A4
24. S(b)+S(a)=S(a+S(b))                         para 23 22
25. S(b)+S(a)=S(S(a+b))                         A4 24
26. b+a=a+b                                     ∀E 18
27. S(b)+S(a)=S(S(b+a))                         para 25 26
28. S(b)+S(a)=S(b+S(a))                         A4 27
29. b+S(a)=S(a)+b                               ∀E 18
30. S(b)+S(a)=S(S(a)+b)                         para 28 29
31. S(b)+S(a)=S(a)+S(b)                         A4 30
32. ψSb(S(a))                                   ψdef 31
33. ψSb(a)→ψSb(S(a))                              →I 21-32
34. ∀x[ψSb(x)→ψSb(S(x))]                          ∀I 33
35. [ψSb(0)]∧[∀x[ψSb(x)→ψSb(S(x))]]               ∧I 20 34
36. [[ψSb(0)]∧[∀x[ψSb(x)→ψSb(S(x))]]]→[∀xψSb(x)]  A5
37. ∀xψSb(x)                                      MP 36 35
38. ϕ(S(b))                                       ϕdef 37
39. ϕ(b)→ϕ(S(b))                                    →I 17-38
40. ∀x[ϕ(x)→ϕ(S(x))]                                ∀I 39
41. [ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]                       ∧I 16 40
42. [[ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]]→[∀xϕ(x)]            A5
43. ∀xϕ(x)                                          MP 42 41

We shall use $P1$ to denote this.

## Part 2: Addition is associative

Let $\varphi(x)$ denote $(a+b)+x=a+(b+x)$.

01. (a+b)+0=a+b                           A3
02. b+0=b                                 A3
03. (a+b)+0=a+(b+0)                       para 01 02
04. ϕ(0)                                  ϕdef 03
05. ϕ(c)                                assumption
06. (a+b)+c=a+(b+c)                     ϕdef 05
07. S((a+b)+c)=S(a+(b+c))               = 06
08. (a+b)+S(c)=S(a+(b+c))               A4 07
09. (a+b)+S(c)=a+S(b+c)                 A4 08
10. (a+b)+S(c)=a+(b+S(c))               A4 09
11. ϕ(S(c))                             ϕdef 10
12. ϕ(c)→ϕ(S(c))                          →I 05-11
13. ∀x[ϕ(x)→ϕ(S(x))]                      ∀I 12
14. [ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]             ∧I 04 13
15. [[ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]]→[∀xϕ(x)]  A5
16. ∀xϕ(x)                                MP 15 14

We shall use $P2$ to denote this.

## Part 3: Multiplication is left-distributive

Let $\varphi(x)$ denote $a*(b+x)=(a*b)+(a*x)$.

01. b+0=b                                 A3
02. a*(b+0)=a*b                           = 01
03. a*0=0                                 A6
04. (a*b)+0=a*b                           A3
05. (a*b)+(a*0)=a*b                       para 04 03
06. a*(b+0)=(a*b)+(a*0)                   para 02 05
07. ϕ(0)                                  ϕdef 06
08. ϕ(c)                                assumption
09. a*(b+c)=(a*b)+(a*c)                 ϕdef 08
10. b+S(c)=S(b+c)                       A4
11. a*(b+S(c))=a*S(b+c)                 = 10
12. a*(S(b+c))=(a*(b+c))+a              A7
13. a*(b+S(c))=(a*(b+c))+a              para 11 12
14. a*(b+S(c))=((a*b)+(a*c))+a          para 13 09
15. (a*b)+(a*c))+a=(a*b)+((a*c)+a)      P2
16. a*(b+S(c))=(a*b)+((a*c)+a)          para 14 15
17. a*S(c)=(a*c)+a                      A7
18. a*(b+S(c))=(a*b)+(a*S(c))           para 16 17
19. ϕ(S(c))                             ϕdef 18
20. ϕ(c)→ϕ(S(c))                          →I 08-19
21. ∀x[ϕ(x)→ϕ(S(x))]                      ∀I 20
22. [ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]             ∧I 07 21
23. [[ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]]→[∀xϕ(x)]  A5
24. ∀xϕ(x)                                MP 23 22

We shall use $P3$ to denote this.

## Part 4: Every non-zero number has a predecessor

Let $\varphi(x)$ denote $x \ne 0 \implies \exists y [S(y)=x]$.

01. 0≠0                                 assumption
02. ⊥                                   01
03. Ǝy[S(y)=0]                          explosion
04. 0≠0→Ǝy[S(y)=0]                        →I 01-03
05. ϕ(0)                                  ϕdef 04
06. ϕ(a)                                assumption
07. a≠0→Ǝy[S(y)=a]                      ϕdef 06
08. S(a)≠0                            assumption
09. S(a)=S(a)                         =
10. Ǝy[S(y)=S(a)]                     ƎI 09
10. S(a)≠0→Ǝy[S(y)=S(a)]                →I 08-10
11. ϕ(S(a))                             ϕdef 10
12. ϕ(a)→ϕ(S(a))                          →I 06-11
13. ∀x[ϕ(x)→ϕ(S(x))]                      ∀I 12
14. [ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]             ∧I 05 13
15. [[ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]]→[∀xϕ(x)]  A5
16. ∀xϕ(x)                                MP 15 14

We shall use $P4$ to denote this.

## Part 5: Every number is either odd or even

Let $\varphi(x)$ denote $[E(x) \land \neg O(x)] \lor [O(x) \land \neg E(x)]$.

01. 0+0=0                                      A3
02. Ǝy[y+y=0]                                  ƎI 01
03. E(0)                                       Edef 02
04. O(0)                                     assumption
05. Ǝy[S(y+y)=0]                             Odef 04
06. S(b+b)=0                               assumption
07. ⊥                                      A1
08. ⊥                                        ƎE 05 06-07
09. ¬O(0)                                      ¬I 04-08
10. E(0)∧¬O(0)                                 ∧I 03 09
11. [E(0)∧¬O(0)]∨[O(0)∧¬E(0)]                  vI 10
12. ϕ(0)                                       ϕdef 11
13. ϕ(a)                                     assumption
14. [E(a)∧¬O(a)]∨[O(a)∧¬E(a)]                ϕdef 13
15. E(a)∧¬O(a)                             assumption
16. E(a)                                   ∧E 15
17. ∃y[y+y=a]                              Edef 16
18. b+b=a                                assumption
19. S(b+b)=S(a)                          18
20. ∃y[S(y+y)=S(a)]                      ∃I 19
21. ∃y[S(y+y)=S(a)]                        ∃E 17 18-20
22. O(S(a))                                Odef 21
23. E(S(a))                              assumption
24. ∃y[y+y=S(a)]                         Edef 23
25. b+b=S(a)                           assumption
26. b=0                              assumption
27. 0+0=S(a)                         para 25 26
28. 0=S(a)                           A3 27
29. ⊥                                A1
30. b≠0                                ¬I 26-29
31. ∃z[S(z)=b]                         P4 30
32. S(c)=b                           assumption
33. S(c)+S(c)=S(a)                   para 25 32
34. S(S(c)+c)=S(a)                   A4 33
35. S(c)+c=a                         A2 34
36. c+S(c)=a                         P1 35
37. S(c+c)=a                         A4 36
38. ∃y[S(y+y)=a]                     ∃I 37
39. ¬O(a)                            ∧E 15
40. ⊥                                38 39
41. ⊥                                  ∃E 31 32-40
42. ⊥                                    ∃E 24 25-41
43. ¬E(S(a))                               ¬I 23-43
44. O(S(a))∧¬E(S(a))                       ∧I 22 43
45. [E(S(a))∧¬O(S(a))]∨[O(S(a))∧¬E(S(a))]  ∨I 44
46. ϕ(S(a))                                ϕdef 45
47. [E(a)∧¬O(a)]→ϕ(S(a))                     →I 15-46
48. O(a)∧¬E(a)                             assumption
49. O(a)                                   ∧E 48
50. ∃y[S(y+y)=a]                           Odef 49
51. S(b+b)=a                             assumption
52. S(S(b+b))=S(a)                       = 51
53. S(b+S(b))=S(a)                       A4 52
54. S(S(b)+b)=S(a)                       P1 53
55. S(b)+S(b)=S(a)                       A4 54
56. ∃y[y+y=S(a)]                         ∃I 55
57. ∃y[y+y=S(a)]                           ∃E 50 51-56
58. E(S(a))                                Edef 57
59. O(S(a))                              assumption
60. ∃y[S(y+y)=S(a)]                      Odef 59
61. S(b+b)=S(a)                        assumption
62. b+b=a                              A2 61
63. ∃y[y+y=a]                          ∃I 62
64. ¬E(a)                              ∧E 48
65. ⊥                                  63 64
66. ⊥                                    ∃E 60 61-65
67. ¬O(S(a))                               ¬I 59-66
68. E(S(a))∧¬O(S(a))                       ∧I 58 67
69. [E(S(a))∧¬O(S(a))]∨[O(S(a))∧¬E(S(a))]  ∨I 68
70. ϕ(S(a))                                ϕdef 69
71. [O(a)∧¬E(a)]→ϕ(S(a))                     →I 48-70
72. ϕ(S(a))                                  ∨E 14 47 71
73. ϕ(a)→ϕ(S(a))                               →I 48-72
74. ∀x[ϕ(x)→ϕ(S(x))]                           ∀I 73
75. [ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]                  ∧I 12 74
76. [[ϕ(0)]∧[∀x[ϕ(x)→ϕ(S(x))]]]→[∀xϕ(x)]       A5
77. ∀xϕ(x)                                     MP 76 75

We shall use $P5$ to denote this.

## Part 6: If $n^2$ is even then $n$ is even

01. E(n*n)                                                   assumption
02. ∃y[y+y=n*n]                                              Edef 01
03. [E(n)∧¬O(n)]∨[O(n)∧¬E(n)]                                P5 n
04. E(n)∧¬O(n)                                             assumption
05. E(n)                                                   ∧E 04
06. [E(n)∧¬O(n)]→E(n)                                        →I 04-05
07. O(n)∧¬E(n)                                             assumption
08. O(n)                                                   ∧E 07
09. ∃y[S(y+y)=n]                                           Odef 08
10. S(b+b)=n                                             assumption
11. S(b+b)*S(b+b)=n*n                                    = 10
12. (S(b+b)*(b+b))+S(b+b)=n*n                            A7 11
13. (S(b+b)*((b+0)+b))+S(b+b)=n*n                        A3 12
14. (S(b+b)*((0+b)+b))+S(b+b)=n*n                        P1 13
15. (S(b+b)*(((b*0)+b)+b))+S(b+b)=n*n                    A6 14
16. (S(b+b)*((b*S(0))+b))+S(b+b)=n*n                     A7 15
17. (S(b+b)*(b*S(S(0))))+S(b+b)=n*n                      A7 16
18. ((S(b+b)*b)*S(S(0)))+S(b+b)=n*n                      P3 17
19. (((S(b+b)*b)*S(0))+(S(b+b)*b))+S(b+b)=n*n            A7 18
20. ((((S(b+b)*b)*0)+(S(b+b)*b))+(S(b+b)*b))+S(b+b)=n*n  A7 19
21. ((0+(S(b+b)*b))+(S(b+b)*b))+S(b+b)=n*n               A6 20
22. (((S(b+b)*b)+0)+(S(b+b)*b))+S(b+b)=n*n               P1 21
23. ((S(b+b)*b)+(S(b+b)*b))+S(b+b)=n*n                   A3 22
24. S(((S(b+b)*b)+(S(b+b)*b))+(b+b))=n*n                 A4 23
25. S((((S(b+b)*b)+(S(b+b)*b))+b)+b)=n*n                 P2 24
26. S(((S(b+b)*b)+((S(b+b)*b)+b))+b)=n*n                 P2 25
27. S(((S(b+b)*b)+(b+(S(b+b)*b)))+b)=n*n                 P1 26
28. S((((S(b+b)*b)+b+(S(b+b)*b)))+b)=n*n                 P2 27
29. S((((S(b+b)*b)+b)+((S(b+b)*b))+b))=n*n               P2 28
30. ∃y[S(c+c)=n*n]                                       ∃I 29
31. ∃y[S(c+c)=n*n]                                         ∃E 09 10-30
32. O(n*n)                                                 Edef 31
33. [E(n*n)∧¬O(n*n)]∨[O(n*n)∧¬E(n*n)]                      P5 n*n
34. E(n*n)∧¬O(n*n)                                       assumption
35. ¬O(n*n)                                              ∧E 34
36. ⊥                                                    31 35
37. [E(n*n)∧¬O(n*n)]→⊥                                     →I 34-36
38. O(n*n)∧¬E(n*n)                                       assumption
39. ¬E(n*n)                                              ∧E 38
40. ⊥                                                    01 39
41. [O(n*n)∧¬E(n*n)]→⊥                                     →I 38-40
42. ⊥                                                      ∨E 33 37 41
43. E(n)                                                   explosion
44. [O(n)∧¬E(n)]→E(n)                                        →I 07-43
45. E(n)                                                     ∨E 03 06 44
46. E(n*n)→E(n)                                                →I 01-45

## Conclusion

This is surprisingly provable in intuitionistic logic.

• I really think this is overkill for what the OP asks. Sep 21, 2017 at 15:26
• This is amazing. 10 outta 10 Sep 21, 2017 at 22:14
• Please tell which language it is, so as to make better out of it. Sep 16, 2020 at 21:09
• Please don't tell me you did this by hand. Sep 28, 2020 at 13:11
• I did this by hand. Sep 28, 2020 at 13:12

Lemma: Let $m, n \in \Bbb Z$. If $m+n$ is even, then $m$ has the same parity as $n$.

Proof: Suppose by contradiction, without loss of generality, that $m$ and $n$ have different parities. Therefore $m = 2a$ and $n = 2b + 1$. So $2|2(a+b) + 1 \implies 2|1$, absurd. Therefore $m$ and $n$ have the same parities.

Now see that $n^2 - n = n(n-1)$, product of two consecutive numbers. So $n^2$ and $-n$ have the same parity (the product is even, analyze the remainder for each case) . Therefore $-n$ is even so $n$ is also even.

• Best and unique. Sep 16, 2020 at 21:06