Chapter: Divisibility and Modular Arithmetic

In this chapter, we will provide different algorithms in Python useful for modular arithmetic. Please refer to elementary number theory for a theoretical introduction in modular arithmetic.

  1. Algorithm: Greatest Common Divisor (Python)
  2. Algorithm: Extended Greatest Common Divisor (Python)
  3. Algorithm: Calculation of Inverses Modulo a Number (Python)
  4. Algorithm: Continued Fraction (Python)
  5. Algorithm: Jacobi Symbol (Python)

Thank you to the contributors under CC BY-SA 4.0!