• Mar 24th 2009, 05:53 PM
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.
• Mar 25th 2009, 12:42 AM
Prime number proof
Hello thecleric
Quote:

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$

• Mar 25th 2009, 12:52 AM
thecleric
• Mar 25th 2009, 02:44 AM
Contrapositive
Hello thecleric
Quote:

Originally Posted by thecleric
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$.