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

Media Hopper link: Quotient-Remainder Theorem

Greatest Common Denominators

Media Hopper link: Greatest Common Denominators and The Euclidean Algorithm

Linear Diophantine Equations

Media Hopper link: Diophantine Equations

Exercises

• Exercise Set 4.10 Questions 9, 13, and 27