Understanding GCD and Modular Arithmetic
The greatest common divisor identifies the largest integer dividing two values exactly. The Euclidean algorithm finds this divisor using repeated remainder calculations. Each division replaces a larger problem with a smaller one. This process finishes when the remainder becomes zero. The previous nonzero remainder is the required GCD. Extended Euclidean calculations add useful coefficients to that process. Those coefficients satisfy Bézout's identity for the entered integers. They also reveal modular inverses when the GCD equals one.
Working with modular values
Modular arithmetic studies integers through their remainders after division. It treats numbers with matching remainders as congruent values. For example, seventeen and five are congruent modulo twelve. Their difference equals twelve, which the modulus divides exactly. Modular addition and multiplication can reduce values before calculations. This keeps intermediate values smaller and easier to inspect. A modular inverse reverses multiplication within a chosen modulus. Such an inverse exists only for coprime values. The extended Euclidean algorithm provides the inverse efficiently. Modular exponentiation handles large powers through repeated squaring. This method avoids computing an enormous ordinary power first.
Solving congruences and checking results
A linear congruence has the form ax congruent b modulo n. Solutions depend on the GCD of a and n. A solution exists when that GCD divides b exactly. Dividing the equation by this common divisor simplifies it. The reduced coefficient then has an inverse under the smaller modulus. Multiplying by that inverse produces a base solution. Additional solutions follow by adding multiples of the reduced modulus. Congruence checking is even simpler and uses a difference test. Two integers are congruent when their difference divides by n. This calculator exposes each major step. It also reports coprimality and useful modulus information. CSV export supports record keeping and further analysis. PDF export creates a readable calculation summary for sharing. These tools make modular number theory calculations easier daily.