**Unit 2: The Greatest Common Divisor**
*Even when an integer is not prime, it can still behave in a prime-like
fashion with many other integers. We call two integers that act this
way* **relatively prime***. This concept is as important to elementary
number theory as the notion of prime numbers, and it depends entirely on
the* **greatest common divisor** *of the two integers in question,
abbreviated as their* **gcd***. A surprisingly efficient method to
compute the gcd is due to the same Euclid who showed us earlier that
there are infinitely many primes, and we will study it here in some
detail.*

*We next turn to the topic of **linear Diophantine equations**. These
are basically the same linear equations that you studied in precalculus,
but with a twist: we only want integer solutions. This greatly restricts
what we can do, but the gcd provides a criterion for when a linear
Diophantine equation can be solved, and the Euclidean algorithm – which
we need to compute the gcd anyway – provides a splendid technique for
solving them. This leads us to **Bezout’s identity**, which “turns the
tables” on these relationships and provides a powerful tool for
subsequent units.*

**Unit2 Learning Outcomes**

Upon successful completion of this unit, you will be able to:
- define the greatest common divisor (gcd) and identify important
properties of the gcd;
- compute the gcd of two integers using the Euclidean Algorithm and
predict how many steps it will take;
- explain why there are infinitely many prime numbers in arithmetic
sequences with a certain property defined by the gcd;
- determine which linear Diophantine equations have solutions and
solve them; and
- use the Extended Euclidean Algorithm to write the gcd in terms of
Bezout’s identity.

**2.1 The Greatest Common Divisor**
**2.1.1 Definition and Elementary Properties**
- **Reading: Wissam Raji’s “An Introductory Course in Elementary
Number Theory - Section 1.5: The Greatest Common Divisor”**
Link: Wissam Raji’s “An Introductory Course in Elementary Number
Theory - Section 1.5: The Greatest Common
Divisor”
(PDF)

```
Instructions: Read “Section 1.5: The Greatest Common Divisor” on
pages 21-24.
Reading this section, taking notes, and studying the examples
should take approximately 30 minutes.
```

**Assessment: Wissam Raji’s “An Introductory Course in Elementary Number Theory - GCD Exercises”**Link: Wissam Raji’s “An Introductory Course in Elementary Number Theory - GCD Exercises” (PDF)Instructions: Try to do Exercises 1, 3, 4, 5, and 6 on page 25.

After attempting the exercises assigned above, discuss your solutions in the course discussion forum. Feel free to respond to other students’ postings as well. If you haven’t already done so, you will need to create a free account at the link above to participate in the discussions.

Completing this assessment should take approximately 1 hour.

**2.1.2 Dirichlet’s Theorem**
- **Reading: Wissam Raji’s “An Introductory Course in Elementary
Number Theory: Section 2.4.1: The Fundamental Theorem of Arithmetic
and Section 2.4.2: More on the Infinitude of Primes”**
Link: Wissam Raji’s “An Introductory Course in Elementary Number
Theory: Section 2.4.1: The Fundamental Theorem of Arithmetic and
Section 2.4.2: More on the Infinitude of
Primes”
(PDF)

```
Instructions: Reread “Section 2.4.1: The Fundamental Theorem of
Arithmetic” on pages 41–44. Then read “Section 2.4.2: More on the
Infinitude of Primes” on pages 45-46.
Reading these sections, taking notes, and studying the examples
should take approximately 1 hour.
```

**Assessment: Wissam Raji’s “An Introductory Course in Elementary Number Theory - Infinitude of Primes Exercise”**Link: Wissam Raji’s “An Introductory Course in Elementary Number Theory - Infinitude of Primes Exercise” (PDF)Instructions: Try to do Exercise 4 on page 46.

After attempting the exercise assigned above, discuss your solution in the course discussion forum. Feel free to respond to other students’ postings as well. If you haven’t already done so, you will need to create a free account at the link above to participate in the discussions.

Completing this assessment should take approximately 15 minutes.

**2.2 The Euclidean Algorithm**
**2.2.1 Statement of the Algorithm and Some Examples**
- **Reading: Wissam Raji’s “An Introductory Course in Elementary
Number Theory - Section 1.6: The Euclidean Algorithm”**
Link: Wissam Raji’s “An Introductory Course in Elementary Number
Theory - Section 1.6: The Euclidean
Algorithm”
(PDF)

```
Instructions: Read “Section 1.6: The Euclidean Algorithm” on pages
25-28. Be sure to follow the examples carefully!
Reading this section, taking notes, and studying the examples
should take approximately 30 minutes.
```

**Assessment: Wissam Raji’s “An Introductory Course in Elementary Number Theory - Euclidean Algorithm Exercises”**Link: Wissam Raji’s “An Introductory Course in Elementary Number Theory - Euclidean Algorithm Exercises” (PDF)Instructions: Try to do Exercises 2, 3, 4, and 5 on pages 28–29.

After attempting the exercises assigned above, discuss your solutions in the course discussion forum. Feel free to respond to other students’ postings as well. If you haven’t already done so, you will need to create a free account at the link above to participate in the discussions.

Completing this assessment should take approximately 1 hour.

**2.2.2 “How Much Time Do I Have To Waste On This?” An Analysis of the
Algorithm’s Efficiency**
- **Reading: Wissam Raji’s “An Introductory Course in Elementary
Number Theory - Section 1.7.1: Lame’s Theorem”**
Link: Wissam Raji’s “An Introductory Course in Elementary Number
Theory - Section 1.7.1: Lame’s
Theorem”
(PDF)

```
Instructions: Read “Section 1.7.1: Lame’s Theorem” on pages
29-31.
Reading this section, taking notes, and studying the examples
should take approximately 30 minutes.
```

**Assessment: Wissam Raji’s “An Introductory Course in Elementary Number Theory - Upper Bound Exercises”**Link: Wissam Raji’s “An Introductory Course in Elementary Number Theory - Upper Bound Exercises” (PDF)Instructions: Try to do Exercises 3 and 4 on page 34.

After attempting the exercises assigned above, discuss your solutions in the course discussion forum. Feel free to respond to other students’ postings as well. If you haven’t already done so, you will need to create a free account at the link above to participate in the discussions.

Completing this assessment should take approximately 30 minutes.

**2.2.3 Binet’s Formula and the Golden Ratio**
- **Reading: Wissam Raji’s “An Introductory Course in Elementary
Number Theory - Section 1.7.2: Binet’s Formula”**
Link: Wissam Raji’s “An Introductory Course in Elementary Number
Theory - Section 1.7.2: Binet’s
Formula”
(PDF)

```
Instructions: Read “Section 1.7.2: Binet’s Formula” on pages
31–34.
Reading this section, taking notes, and studying the examples
should take approximately 30 minutes.
```

**Assessment: Wissam Raji’s “An Introductory Course in Elementary Number Theory - Binet’s Formula Exercises”**Link: Wissam Raji’s “An Introductory Course in Elementary Number Theory - Binet’s Formula Exercises” (PDF)Instructions: Try to do Exercises 5 and 6 on page 34.

Completing this assessment should take approximately 30 minutes.

**2.2.4 The Lucas Sequence (Optional)**
- **Reading: Wissam Raji’s “An Introductory Course in Elementary
Number Theory - Lucas Sequence Exercise”**
Link: Wissam Raji’s “An Introductory Course in Elementary Number
Theory - Lucas Sequence
Exercise”
(PDF)

```
Instructions: Try to do Exercise 7 on page 34.
After attempting the exercise assigned above, discuss your solution
in the course discussion forum. Feel free to respond to other
students’ postings as well. If you haven’t already done so, you will
need to create a free account at the link above to participate in
the discussions.
Completing this assessment should take approximately 1 hour.
```

**2.3 Linear Diophantine Equations**
**2.3.1 Definition and Criterion for Solvability**
- **Reading: Wissam Raji’s “An Introductory Course in Elementary
Number Theory - Section 2.6: Linear Diophantine Equations”**
Link: Wissam Raji’s “An Introductory Course in Elementary Number
Theory - Section 2.6: Linear Diophantine
Equations”
(PDF)

```
Instructions: Read “Section 2.6: Linear Diophantine Equations” on
pages 49-51.
Reading this section, taking notes, and studying the examples
should take approximately 15 minutes.
```

**Assessment: Wissam Raji’s “An Introductory Course in Elementary Number Theory - Linear Diophantine Equation Exercises”**Link: Wissam Raji’s “An Introductory Course in Elementary Number Theory - Linear Diophantine Equation Exercises” (PDF)Instructions: Try to do Exercises 1, 2, and 4 on page 51.

Completing this assessment should take approximately 1 hour.

**2.3.2 Sage Lab: “Visualizing the Solutions to Linear Diophantine
Equations”**
- **Web Media: The Saylor Foundation’s Sage Lab: “Visualizing
Solutions to Linear Diophantine Equations”**
Link: The Saylor Foundation’s Sage Lab: “Visualizing Solutions to
Linear Diophantine
Equations”
(Sage)

```
Instructions: Download the linked set of labs. Upload the second
one (2.3.2-SageWS2.sws) to the Sage website where you created an
account (subunit 1.4.2). Work through the lab carefully.
Completing this assignment should take approximately 30 minutes.
```