Results 1 to 2 of 2

Thread: Proof by contradiction

  1. #1
    Member
    Joined
    Jan 2009
    From
    Kingston, PA
    Posts
    96

    Unhappy Proof by contradiction

    If u and v have different parities( one is even and one is odd), then ( a,b,c) is primitive.

    Fact: If (a, b, c) is not primitive, then there exists a prime number p and natural numbers a`, b`, c` , such that a=pa`, b=pb` , c=pc`

    Fact 2: if p is a prime number, and m,n are elements of N such tha p|mn , then p|m or p|n
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Apr 2009
    From
    Atlanta, GA
    Posts
    409

    Pythagorean Theorem

    Well, for starters, you ought to specify that we're referring to the equations $\displaystyle (a,b,c)=(u^2-v^2,2uv,u^2+v^2)$. Also, this theorem is false: $\displaystyle u$ and $\displaystyle v$ must not only have opposite parities, they must be relatively prime. Example: $\displaystyle 6$ and $\displaystyle 3$ have opposite parity, yet $\displaystyle (27,36,45)$ is NOT primitive. The correct theorem should read: "If $\displaystyle (u,v)=1$, then $\displaystyle (a,b,c)$ is primitive." Moving on...

    To prove by contradiction, we start with the premise "$\displaystyle u$ and $\displaystyle v$ have no common divisors AND there exists a prime $\displaystyle p$ that divides $\displaystyle a,b,c$." We will show this premise to be impossible:

    Lemma: if $\displaystyle (u,v)=1$, $\displaystyle u$ and $\displaystyle v$ must have opposite parities, one even one odd. $\displaystyle p|b$ so $\displaystyle p|2uv$, so $\displaystyle p=2$ or $\displaystyle p|u$ or $\displaystyle p|v$. If $\displaystyle p=2$ then since $\displaystyle u$ and $\displaystyle v$ have opposite parities, so $\displaystyle p|u$ or $\displaystyle p|v$. WLOG, suppose $\displaystyle p|u$. Now, $\displaystyle p|a$ so $\displaystyle p|u^2-v^2$. Since $\displaystyle p|u$, $\displaystyle p|v^2$ so $\displaystyle p|v$. Thus, $\displaystyle (u,v)\neq1$, and we have our contradiction. Therefore our premise is false.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Contradiction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Sep 22nd 2010, 08:29 PM
  2. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Feb 27th 2010, 10:07 PM
  3. proof by contradiction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Nov 1st 2009, 12:34 PM
  4. Proof by Contradiction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Oct 7th 2009, 01:08 PM
  5. Proof by contradiction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Apr 11th 2009, 04:12 PM

Search Tags


/mathhelpforum @mathhelpforum