# Proving and Disproving

• Jan 18th 2008, 06: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, 07:06 AM
ThePerfectHacker
Quote:

Originally Posted by TheRekz
1. $\displaystyle \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 $\displaystyle m=2a+r_1$ where $\displaystyle r_1=0,1$ and $\displaystyle n=2b+r_2$ then $\displaystyle n+m = 2(a + b) + (r_1+r_2)$ for this to be even we require that $\displaystyle (r_1,r_2)=(0,0)$ or $\displaystyle (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 $\displaystyle n>11$ is even then $\displaystyle n - 4 > 2$ is even and these are composite, thus, $\displaystyle n=4+(n-4)$. If $\displaystyle n>11$ and is odd then we $\displaystyle n-9>2$ is even and so composite which means we can write $\displaystyle n = 9 + (n-9)$.
• Jan 18th 2008, 07: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, 08: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 $\displaystyle \mathbb{Z}$)

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

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

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

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

RonL
• Jan 18th 2008, 08: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, 08: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, 10: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 $\displaystyle N> 11$ not the sum of two composite integers.

Then $\displaystyle N$ is even or odd.

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

Case 2: $\displaystyle N$ odd, put $\displaystyle n_1=9,\ n_2=N-9$, then both $\displaystyle n_1$ is composite and $\displaystyle n_2$ is even and greater than $\displaystyle 2$ and hence composite, but this contradicts our assumption so $\displaystyle 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, 03:19 PM
TheRekz
Quote:

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

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

Then $\displaystyle N$ is even or odd.

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

Case 2: $\displaystyle N$ odd, put $\displaystyle n_1=9,\ n_2=N-9$, then both $\displaystyle n_1$ is composite and $\displaystyle n_2$ is even and greater than $\displaystyle 2$ and hence composite, but this contradicts our assumption so $\displaystyle 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, 08: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