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.

2. ## Prime number proof

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 $\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$

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

4. ## Contrapositive

Hello thecleric
Originally Posted by thecleric
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?