Results 1 to 4 of 4

Thread: 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
    Thanks
    1

    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 $\displaystyle p$ and an integer $\displaystyle n$, suppose that $\displaystyle A$ is the proposition " $\displaystyle p|n^2$ ", and that $\displaystyle B$ is the proposition " $\displaystyle p|n$ ". Then we must show that $\displaystyle A \Rightarrow B$.

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

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

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

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

    So $\displaystyle \neg B \Rightarrow \neg A$.

    Therefore $\displaystyle 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
    Thanks
    1

    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 $\displaystyle A \Rightarrow B$ is $\displaystyle \neg B \Rightarrow \neg A$, and I have shown that, in this case, $\displaystyle \neg B \Rightarrow \neg A$. In other words, if $\displaystyle p$ does not divide $\displaystyle n$ then $\displaystyle p$ does not divide $\displaystyle n^2$.

    This, then, contradicts the assertion that $\displaystyle p$ does divide $\displaystyle n^2$. Therefore $\displaystyle 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: Oct 6th 2011, 01:11 PM
  2. Help with Proof by Contradiction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 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: Feb 27th 2010, 10:07 PM
  5. proof by contradiction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Nov 1st 2009, 12:34 PM

Search Tags


/mathhelpforum @mathhelpforum