DMP 5.3: Quotient-Remainder Theorem and Euclidean Algorithm

Reading

There are a few ideas that were omitted from earlier chapters and need to be understood before tackling the material on RSA cryptography.

• Section 5.4 pages 308–310: The Well-Ordering Principle for the Integers with the Quotient-Remainder Theorem
• Section 4.10 pages 250–253: The Euclidean Algorithm and definition of Greatest Common Divisor (GCD)

The topic of Diophantine Equations is not covered in Epp but you can find it in the online Levin textbook Discrete Mathematics as part of a chapter on divisibility and congruence.

• Levin Section 5.2 item Solving Linear Diophantine Equations

Videos

The Quotient-Remainder Theorem

Greatest Common Denominators

Linear Diophantine Equations

Exercises

• Exercise Set 4.10 Questions 9, 13, and 27