Solution for Section 3.6 Question 1

1. We are asked to prove, using the method of contradiction, the statement: "n Z and "primes p,  if p | n², then p | n.

Proof The negation of the given statement is:  $ n Z and $ a prime p such that  p | n²  and  pn.

We now assume that the negation is true and we need to show that this leads to a contradiction.

Consider the prime factorization (from the Unique Factorization Theorem) of each of n and n². 

Suppose that the unique prime factorization of n is:   n = p₁^e₁ · p₂^e₂ · ... · p_k^e_k,  and since pn, we know that  pp_i  for any 1 i k.

The unique prime factorization of n² is: n² = (p₁^e₁ · p₂^e₂ · ... · p_k^e_k)² =  p₁^2e₁ · p₂^2e₂ · ... · p_k^2e_k, and since p | n², we know that  p = p_i for some 1 i k.
(Keep in mind that p is a prime.)

We have now discovered that if the negation of this statement were true, then both pp_i and p = p_i for some 1 i k. This is a contradiction and therefore the negation must be false. Hence the original statement: "n Z and "primes p,  if p | n², then p | n, must be true.

Back to Section 3.6