# Proving and Disproving

• Jan 18th 2008, 07:30 AM
TheRekz
Proving and Disproving
1. [tex] \forall m,n \in Z, if m + n is even then either m and n are both even or
they are both odd [\math]

2. Prove or disprove using contradiction. Every integer > 11 is the sum of two
composite integers.

For the first number, is it the same if I prove that if m and n are both even then m +n is even and if m and n are both odd then m + n is even?
• Jan 18th 2008, 08:06 AM
ThePerfectHacker
Quote:

Originally Posted by TheRekz
1. $\forall m,n \in Z, if m + n$ is even then either m and n are both even or
they are both odd

By division algorithm we can write $m=2a+r_1$ where $r_1=0,1$ and $n=2b+r_2$ then $n+m = 2(a + b) + (r_1+r_2)$ for this to be even we require that $(r_1,r_2)=(0,0)$ or $(r_1,r_2)=(1,1)$, i.e. both even or both odd.
Quote:

2. Prove or disprove using contradiction. Every integer > 11 is the sum of two
composite integers.
If $n>11$ is even then $n - 4 > 2$ is even and these are composite, thus, $n=4+(n-4)$. If $n>11$ and is odd then we $n-9>2$ is even and so composite which means we can write $n = 9 + (n-9)$.
• Jan 18th 2008, 08:39 AM
TheRekz
is there any other way to proof this?? your explanation seems complicated although it makes sense. I don't quite understand where did you get the m = 2a + r from?? so you mean r can be either 0 or 1 here depends whether m is odd or even? if m is even then r is 0?? r can therefore also be 2 right?
• Jan 18th 2008, 09:17 AM
CaptainBlack
Quote:

Originally Posted by TheRekz
1. [tex] \forall m,n \in Z, if m + n is even then either m and n are both even or
they are both odd [\math]

(all number refered to are in $\mathbb{Z}$)

Supose there are $n$ and $m$ such that $n$ is odd and $m$ even and $n+m$ is even.

By supposition there exist $k_1$ and $k_2$ such that $n=2k_1+1,\ m=2k_2$.

Then $n+m=2(k_1+k_2)+1$ which is odd, which contradicts our supposition.

Hence if $n+m$ is even either $m$ and $n$ are both even or they are both odd

RonL
• Jan 18th 2008, 09:20 AM
CaptainBlack
Quote:

Originally Posted by TheRekz
1
For the first number, is it the same if I prove that if m and n are both even then m +n is even and if m and n are both odd then m + n is even?

No you have to show that if n+m is even both n and m are even or both are odd, and that you will not have done.

RonL
• Jan 18th 2008, 09:40 AM
TheRekz
Quote:

Originally Posted by CaptainBlack
No you have to show that if n+m is even both n and m are even or both are odd, and that you will not have done.

RonL

can you help me to do number 2?? Cause I don't really get it on the post no.2 answer
• Jan 18th 2008, 11:16 AM
CaptainBlack
Quote:

Originally Posted by TheRekz
can you help me to do number 2?? Cause I don't really get it on the post no.2 answer

ImPerfectHackers proof is quite simple (and neat):

Suppose that there is an integer $N> 11$ not the sum of two composite integers.

Then $N$ is even or odd.

Case 1: $N$ even, put $n_1=4,\ n_2=N-4$, then both $n_1$ and $n_2$ are even and greater than $2$ and hence composite, but this contradicts our assumption so $N$ cannot be composite.

Case 2: $N$ odd, put $n_1=9,\ n_2=N-9$, then both $n_1$ is composite and $n_2$ is even and greater than $2$ and hence composite, but this contradicts our assumption so $N$ cannot be composite.

Case 1 and Case 2 together contradict the original assumption and so the theorem: Every integer > 11 is the sum of two composite integers; is proven by contradiction.

RonL
• Jan 23rd 2008, 04:19 PM
TheRekz
Quote:

Originally Posted by CaptainBlack
ImPerfectHackers proof is quite simple (and neat):

Suppose that there is an integer $N> 11$ not the sum of two composite integers.

Then $N$ is even or odd.

Case 1: $N$ even, put $n_1=4,\ n_2=N-4$, then both $n_1$ and $n_2$ are even and greater than $2$ and hence composite, but this contradicts our assumption so $N$ cannot be composite.

Case 2: $N$ odd, put $n_1=9,\ n_2=N-9$, then both $n_1$ is composite and $n_2$ is even and greater than $2$ and hence composite, but this contradicts our assumption so $N$ cannot be composite.

Case 1 and Case 2 together contradict the original assumption and so the theorem: Every integer > 11 is the sum of two composite integers; is proven by contradiction.

RonL

just one more question, how do we know that n2 is even here?? thanks??
• Jan 23rd 2008, 09:13 PM
CaptainBlack
Quote:

Originally Posted by TheRekz
just one more question, how do we know that n2 is even here?? thanks??

In Case 1:By hypothesis N is even, and > 11, so N-4 is even (and >7)

In Case 2:By hypothesis N is odd, and > 11, so N-9 is even (and >2)

(even-even is even, and odd-odd is also even)

RonL