Linear Congruences & Solutions

Math for CS · Axiom Academy

Solving ax ≡ b (mod n) with the Extended Euclidean Algorithm Linear congruences are equations of the form where we want to find all integers x satisfying this congruence. This is fundamental for cryptography, as solving linear congruences is necessary for finding modular inverses and breaking RSA-like systems. Not all linear congruences have solutions. Whether a solution exists depends on the relationship between a , b , and n . The Extended Euclidean Algorithm To solve , we use the Extended Euclidean Algorithm (EEA). This algorithm not only finds but also finds integers s and t such that: Linear congruence solvable iff Extended Euclidean Algorithm finds coefficients satisfying Essential for computing modular inverses Critical for implementing RSA and other cryptographic systems

This is the written version of the interactive lesson above. See the full Math for CS course.