Skip to main content

Integers and Modular Arithmetic

Study this module after the core proof, induction and invariant lessons in Proofs and Discrete Structures. You also need the Semester 00 programming gate and algebra readiness. Existing module numbers and routes remain stable; this module is placed next to proofs in the learning sequence.

Outcomes: model integer divisibility; prove Euclid correct and terminating; verify Bezout certificates; distinguish primes from coprime pairs; use modular inverses only when valid; implement repeated squaring; produce complete linear-congruence solutions and interpret cyclic reachability.

Workload: 25–35 additional focused hours: lessons and hand practice 15–21, lab/project 6–8, assessment and integration 4–6. These author estimates await learner calibration. The integrated semester evidence reuses this work. Full-book reading is not required; use the selective reading guide.

Entry check​

Explain a = qm + r, trace a terminating loop, distinguish a universal claim from examples, and implement a function returning a list. Repair notation/algebra in Semester 00 if needed; use the proofs module for invariants and induction. No calculus is needed. Attempt the concrete cases in entry-check calibration, keeping the answers covered until you have tried them.

Learning sequence​

  1. Divisibility and remainders: 2–3 hours.
  2. Euclid and Bezout certificates: 3–4 hours.
  3. Primes and factorization: 2–3 hours.
  4. Congruences and inverses: 3–4 hours.
  5. Modular exponentiation: 2–3 hours.
  6. Complete solutions and cycles: 3–4 hours.
  7. Guided lab, project and assessment.

What is new and what is reused​

The proof module already introduces divisibility and congruence as examples. Reuse those definitions and proof habits; this module adds the algorithms, edge cases, completeness arguments and computing applications. Optional CRT and sieve exploration belong after the required gates and have no mandatory workload allowance here. Production cryptography is outside scope.

Status: authored module with executable calibration checks; independent mathematical review and learner pilot pending. Preserve failed attempts, assistance declarations and a delayed recheck. Passing the checker alone does not pass the assessment.