• Mar 24th 2009, 04: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 24th 2009, 11:42 PM
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 \$\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\$

• Mar 24th 2009, 11:52 PM
thecleric
• Mar 25th 2009, 01:44 AM
Contrapositive
Hello thecleric
Quote:

Originally Posted by thecleric