Results 1 to 4 of 4

Math Help - Proof by contrapostive/contradiction

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    19

    Proof by contrapostive/contradiction

    If a prime number divides the square of an integer, then the prime divides the integer.

    I have to prove this by contrapositive and contradiction. I know the definition and difference between the two but this proof is hard and I am losing energy fast.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Prime number proof

    Hello thecleric
    Quote Originally Posted by thecleric View Post
    If a prime number divides the square of an integer, then the prime divides the integer.

    I have to prove this by contrapositive and contradiction. I know the definition and difference between the two but this proof is hard and I am losing energy fast.
    Given a prime p and an integer n, suppose that A is the proposition " p|n^2 ", and that B is the proposition " p|n ". Then we must show that A \Rightarrow B.

    By the fundamental theorem of arithmetic, n has a unique prime factorization: n = \prod p_i^{r_i} for some primes p_i

    \Rightarrow n^2 = \prod p_i^{r_i}\prod p_i^{r_i} =\prod p_i^{2r_i}

    Now \neg B \Rightarrow p does not divide n \Rightarrow p \ne p_i for any i

    \Rightarrow (\neg B \Rightarrow  p does not divide n^2)

    So \neg B \Rightarrow \neg A.

    Therefore A \Rightarrow B

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    Posts
    19
    how would i show this, given your technique as a contradiction?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Contrapositive

    Hello thecleric
    Quote Originally Posted by thecleric View Post
    how would i show this, given your technique as a contradiction?
    I'm not quite sure where the problem is.

    The contrapositive of A \Rightarrow B is \neg B \Rightarrow \neg A, and I have shown that, in this case, \neg B \Rightarrow \neg A. In other words, if p does not divide n then p does not divide n^2.

    This, then, contradicts the assertion that p does divide n^2. Therefore p | n^2 \Rightarrow p | n.

    Does that make it any clearer?

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by contradiction.
    Posted in the Discrete Math Forum
    Replies: 20
    Last Post: October 6th 2011, 01:11 PM
  2. Help with Proof by Contradiction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 27th 2010, 10:33 PM
  3. Contradiction proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 4th 2010, 08:20 PM
  4. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  5. proof by contradiction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 1st 2009, 12:34 PM

Search Tags


/mathhelpforum @mathhelpforum