Calculate with residue classes without invalid cancellation

Try

Modulo 5, integers −2,3 and 8 represent the same residue because their differences are multiples of 5. Congruence a≡b mod m means m divides a−b, with a positive modulus m. A least nonnegative representative lies from 0 through m−1.

Predict

Predict which ordinary algebra operations remain safe. Adding or multiplying congruent integers preserves congruence. Dividing requires care: a nonzero integer can represent a noninvertible residue, so cancellation is not automatic.

Experiment

Make a multiplication row for 3 modulo 7. The products 0,3,6,2,5,1,4 visit every residue, and 3·5≡1 identifies inverse 5. Compare multiplication by 2 modulo 6, whose outputs only visit 0,2,4 and therefore cannot reach 1.

Understand

Worked inverse theorem: a has a multiplicative inverse modulo m≥2 exactly when gcd(a,m)=1. Bézout gives au+mv=1 in the coprime case, so u is an inverse. Conversely an inverse gives au−km=1, forcing any common divisor of a,m to divide 1.

Consequently ax≡ay implies x≡y when a is invertible, by multiplying both sides by its inverse. Without coprimality, 2·1≡2·4 mod6 while 1 and 4 differ modulo 6. The failure is loss of information under multiplication, much like a noninjective function.

Invalid remainder: calling −2 the least nonnegative residue of −17 modulo 5. It is congruent, but the requested canonical representative is 3.

Apply

Specify the modulus in every congruence and check an inverse by multiplication. Use residues to simplify large expressions step by step, but never cancel a factor without the gcd condition or an explicitly constructed inverse.

Continue

Depth: repeated squaring computes large modular powers efficiently. Fermat/Euler theorems, multiplicative orders and cryptographic applications require further hypotheses and are reserved for the full number-theory course; modular arithmetic alone is not a security guarantee.