In this section, we're going to focus on divisibility, another topic that students should already be familiar with. We'll continue developing methods of proving mathematical theorems and end with an application of Euclid's theorem to the design of computer algorithms.
Video Lectures
In this next sequence of lectures, we’re going to get more into number theory proper, starting with what’s called divisibility. In the final lecture, we’ll see how these concepts can be applied in a computer science setting by deriving an algorithm for finding the greatest common divisor of two numbers that’s much more efficient than the one you learned in elementary school. (lecture slides)
In this lecture, we're going to prove two new theorems about divisibility: The first shows that divisibility is transitive and the second shows that if a number is a common divisor of two other numbers then it's also a divisor of every linear combination of those numbers. That last one may seem a little abstract but it's going to be essential to coming up with a method for finding the greatest common divisor of two numbers that's more efficient that the one you learned in elementary school. (lecture slides)
The method you learned in elementary school for finding the greatest common divisor of two numbers works - but not very well. It has some steps for which there are no known, efficient algorithms. In this lecture, we'll see how number theory can be applied to practical situations by developing a different, much more efficient algorithm for finding the greatest common divisor of two numbers. (lecture slides)
