Chapter ObjeCtives
After studying this chapter, you will be able to:
• Attack the proofs of conjectures using the techniques of direct proof, proof by
contraposition, and proof by contradiction.
• Recognize when a proof by induction is appropriate and carry out such a proof
using either the first or second principle of induction.
• Mathematically prove the correctness of programs that use loop statements.
• Test whether a given positive integer is prime; if not, find its prime factorization.
• Work with number theoretic ideas of prime factorization, greatest common
divisor, and the Euler phi function.
The nonprofit organization at which you volunteer has received donations of 792 bars
of soap and 400 bottles of shampoo. You want to create packages to distribute to
homeless shelters such that each package contains the same number of shampoo
bottles and each package contains the same number of bars of soap.
Question: How many packages can you create?
This problem is solvable by trial and error, but it’s much easier to use an ancient
algorithm that is discussed in this chapter.
First, however, we consider how to prove “real-world” arguments as opposed
to the formal arguments of Chapter 1. It is helpful to have an arsenal of techniques
for attacking a proof. Direct proof, proof by contraposition, and proof by
contradiction are examined in Section 2.1. Many of the proofs given in this section
are simple “number theory” results, that is, results about integers, such as “The
product of two even integers is even.”
Section 2.2 concentrates on mathematical induction, a proof technique with
particularly wide application in computer science. In Section 2.3 we see how,
using induction, proof of correctness can be extended to cover looping statements.
Finally, Section 2.4 explores some further number theory results, particularly
concerning prime numbers.
2 2
Proofs, Induction, and
Number Theory
C h a p t e r
97
After studying this chapter, you will be able to:
• Attack the proofs of conjectures using the techniques of direct proof, proof by
contraposition, and proof by contradiction.
• Recognize when a proof by induction is appropriate and carry out such a proof
using either the first or second principle of induction.
• Mathematically prove the correctness of programs that use loop statements.
• Test whether a given positive integer is prime; if not, find its prime factorization.
• Work with number theoretic ideas of prime factorization, greatest common
divisor, and the Euler phi function.
The nonprofit organization at which you volunteer has received donations of 792 bars
of soap and 400 bottles of shampoo. You want to create packages to distribute to
homeless shelters such that each package contains the same number of shampoo
bottles and each package contains the same number of bars of soap.
Question: How many packages can you create?
This problem is solvable by trial and error, but it’s much easier to use an ancient
algorithm that is discussed in this chapter.
First, however, we consider how to prove “real-world” arguments as opposed
to the formal arguments of Chapter 1. It is helpful to have an arsenal of techniques
for attacking a proof. Direct proof, proof by contraposition, and proof by
contradiction are examined in Section 2.1. Many of the proofs given in this section
are simple “number theory” results, that is, results about integers, such as “The
product of two even integers is even.”
Section 2.2 concentrates on mathematical induction, a proof technique with
particularly wide application in computer science. In Section 2.3 we see how,
using induction, proof of correctness can be extended to cover looping statements.
Finally, Section 2.4 explores some further number theory results, particularly
concerning prime numbers.
2 2
Proofs, Induction, and
Number Theory
C h a p t e r
97