CS202: Discrete Structures

3.3: Divisibility: Direct Proofs and Counterexamples

• 3.3.1: Divisibility

  • 3.3.1.1: Divisibility Definition

    • Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Number Theory I" URL

      Read Section 1, "Divisibility" on pages 1 - 4 and Section 4, "The Greatest Common Divisor" on pages 7 - 12. This reading overlaps that of Bender and Williamson.

    • University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Number Theory" URL

      Read "Remainders and Modular Arithmetic," page NT-6 to the top of NT-9. Section 2 and Section 3 are motivational, and you should at a minimum scan over them. Note that these discussions in the readings pertain to integers. In considering divisors of zero as you read through these sections, remember that every integer a divides 0, since a · 0 = 0. This also holds for rational, irrational, and real numbers, since w · 0 = 0 for any real number w.

      We say that division by zero is undefined. Why do we say that? Consider the following line of reasoning: suppose x is a non-zero number, and when it is divided by zero, the result is the specific number y. It can be proved that, if x / 0 = y, then x = 0 multiplied by y (i.e. x = 0 * y). But, then, x = 0 * y = 0, because any number multiplied by 0 is 0. However, we assumed that x was non zero, a contradiction.

      If x were 0, then x / 0 = 0 / 0 = y. Again, this implies that 0 = 0 * y. This, in turn, implies that y could be any number. This is, again, a contradiction, because we assumed that y was a specific number.

      Mathematical definitions and proofs are specified to adhere to certain rules. One of those rules is that results do not lead to contradictions. Therefore, we say that division by 0 is not defined.

      Theorem 1 on page NT-3 states that for any given integer, > or = 2, can be written as the product of prime numbers. Each of these primes will be a divisor of the given integer.
      

  • 3.3.1.2: Divisibility of Algebraic Expressions

    • Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Induction I" URL

      Read Section 3, "A Divisibility Theorem."
      

• 3.3.2: Proving Properties of Divisibility

  • Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Number Theory I" URL

    Review Lemma 1 in Section 1.1 on page 2. Then Read Section 5, "The Fundamental Theorem of Arithmetic," on pages 12 - 15. Finally, Read Section 1.2, which presents the Division theorem in its entirety on pages 2 - 5.