Results 1 to 9 of 9

Thread: Proving and Disproving

  1. #1
    Member
    Joined
    Jun 2007
    Posts
    117

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by TheRekz View Post
    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.
    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)$.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2007
    Posts
    117
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by TheRekz View Post
    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]
    By contradiction:

    (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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by TheRekz View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jun 2007
    Posts
    117
    Quote Originally Posted by CaptainBlack View Post
    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
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by TheRekz View Post
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jun 2007
    Posts
    117
    Quote Originally Posted by CaptainBlack View Post
    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??
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by TheRekz View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. disproving a limit.
    Posted in the Differential Geometry Forum
    Replies: 11
    Last Post: Jul 19th 2011, 06:30 AM
  2. proving or disproving probabillity density function
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: Jul 22nd 2010, 12:18 AM
  3. Help disproving this
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: Mar 14th 2010, 09:59 AM
  4. disproving prime numbers
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: Oct 1st 2008, 05:22 AM
  5. Disproving the completeness of a set of connectives
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Feb 18th 2008, 12:09 PM

Search Tags


/mathhelpforum @mathhelpforum