Proof by contrapostive/contradiction

**thecleric** · March 24th 2009, 04:53 PM

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.

**Grandad** · March 24th 2009, 11:42 PM

Hello thecleric

Originally Posted by thecleric

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

**thecleric** · March 24th 2009, 11:52 PM

how would i show this, given your technique as a contradiction?

**Grandad** · March 25th 2009, 01:44 AM

Hello thecleric

Originally Posted by thecleric

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

Thread: Proof by contrapostive/contradiction

LinkBack

Thread Tools

Display

Proof by contrapostive/contradiction

Prime number proof

Contrapositive

Similar Math Help Forum Discussions

Proof by contradiction.

Help with Proof by Contradiction

Contradiction proof

[SOLVED] direct proof and proof by contradiction

proof by contradiction

Search Tags