Basic Proofs Methods II

Two-part proof of P <=> Q
(i) Show P => Q by any method.
(ii) Show Q => P by any method.
Therefore, P => Q

Example. Let a be a prime, and b and c be positive integers. Prove that a divides the product bc if and only if a divides b or a divides c.

Proof.
(i) Suppose a is a prime and a divides bc. By the Fundamenta Theorem of Arithmetic, b and c may be written uniquely as products of primes: b = p1p2p3...pkq1q2q3...qr. Since a is a prime and a divides bc, a is one of the prime factors of bc. Thus, either a = pi for some i or a = qj for some j. If a = pi, then a divides b. If a = qj, then a divides c. Therefore, either a divides b or a divides c.
(ii) Suppose a divides b or a divides c.If a divides b, then a divides bc. If a divides c, then again a divides bc. In either case, a divides bc.

QED