
Divisibility
MIT's 6.1200J Mathematics for Computer Science, taught by Erik Demaine, covers number theory applied to computing. This lecture works through divisibility, the greatest common divisor, and the Extended Euclidean Algorithm, building the tools needed for later cryptography topics in the course. Demaine develops the proofs on the board step by step, showing how GCD computations connect to solving linear Diophantine equations and to finding modular inverses. The session is part of the Spring 2024 offering of MIT's discrete mathematics course for computer science students, which also covers graph theory, counting, and probability elsewhere in the syllabus. Runtime is about 79 minutes, recorded in a standard MIT OpenCourseWare lecture hall format with clear audio and legible board work throughout.