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

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

4. ## Contrapositive

Hello thecleric
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$.