Combine congruences and certify integer solutions

Try

A schedule repeating every three days and another every five can impose x≡2 mod3 and x≡3 mod5. Testing the representatives 0 through 14 finds x=8. The Chinese remainder theorem explains existence and uniqueness of that residue without relying on a small search.

Predict

Predict why coprimality matters. Moduli 4 and 6 share a parity constraint: residues 1 mod4 and 2 mod6 conflict. With coprime m,n, any pair of residues combines into exactly one class modulo mn. Uniqueness means modulo the product, not a unique integer.

Experiment

For m=3,n=5, use 2·3−1·5=1. Build x=b(2·3)+a(−1·5) for residues a=2,b=3, obtaining 8. Reduce the expression under each modulus to see why the opposite coefficient was chosen.

Understand

Worked proof: if um+vn=1, set x=b um+a vn. Modulo m the first term vanishes and vn≡1, yielding a; modulo n the second vanishes and um≡1, yielding b. Two solutions differ by a number divisible by both m and n; coprimality makes it divisible by mn. This proves the solution class is unique.

For ax+by=c, any gcd of a,b divides the left side, so it must divide c. Conversely scale a Bézout identity by c/gcd(a,b) to obtain a particular solution when divisibility holds. The remaining solutions come from the homogeneous equation.

Invalid claim: noncoprime moduli never work. They work when the prescribed residues agree modulo their gcd, with uniqueness modulo their least common multiple.

Apply

Report a least nonnegative representative only when requested, and distinguish it from the full congruence class. For a Diophantine equation, show that a parameter family contains every solution, not merely that it generates some valid pairs.

Continue

Depth: generalized CRT and lattice methods extend these ideas. Unique factorization, primitive roots, quadratic reciprocity and deeper Diophantine theory remain separate number-theory scope. This unit provides the constructive prerequisites rather than claiming that whole course complete.