NTIC Basic Integer Division

Chapter 2 Basic Integer Division

In this chapter, we introduce some concepts of numbers which are familiar, but key for our further study. In particular, we try to understand why they work.

The division algorithm (Section 2.1),
The greatest common divisor (Section 2.2), and
The Euclidean algorithm (Section 2.3).

🔗

Then we'll put them together with the Bezout identity (Section 2.4).

🔗

Summary: Basic Integer Division

Here are some of the main results of this chapter.

The Division Algorithm is a foundational result.
- We use it immediately to prove a well-known fact in Proposition 2.1.4.
- Note that the proof in Subsection 2.1.2 uses the Well-Ordering Principle.
We review Common Divisors and the greatest common divisor, introducing its characterization in Theorem 2.2.4.
The Euclidean algorithm is foundational for this task; see Example 2.3.1 for a good example.
Then we use the previous section's work to prove the Bezout identity.
- We do several examples.
- Importantly, we use this notion to introduce the key concept of Relatively Prime, and prove some facts about this concept.

Finally, we have Exercises.