Competitive-programming answers often fail at the boundary between a theorem and its input conditions. Modular division requires an inverse that may not exist; a zero cross product requires a separate overlap test. These two subjects share a useful habit: reduce a decision to an exact invariant, then handle exceptional cases explicitly.
Solve a congruence before dividing
Definition 17.1.1
(Linear congruence)
For integers and a positive integer , the statement means for some integer . Write .
Theorem 17.1.2
(Solvability of a linear congruence)
Let be integers, a positive integer and . The congruence has a solution if and only if . In that case its solutions form exactly one residue class modulo , which consists of exactly distinct residues modulo .
Proof
(Reduce by the gcd)
If a solution exists, divides both and , hence . Conversely let and divide by : the reduced congruence has a coefficient coprime to its modulus, so Bézout's identity gives an inverse of modulo and the solution . Every solution of the original congruence satisfies the reduced one, by that division, and every solution of the reduced one satisfies the original, by multiplying by . So the solutions are exactly one class modulo , and this class splits into residues modulo .
Proof X-ray
Why the gcd may be canceled but the coefficient may not
The proof divides by , never by . After the division the coefficient is coprime to the modulus , and that is exactly the hypothesis Bézout's identity needs to produce an inverse. The division also divides the modulus: a congruence can be divided by only together with its modulus. That is why the solution set is one class modulo rather than modulo , and why residues modulo appear. When the argument reduces to the ordinary inverse. The necessity direction uses only that divides both and , and needs no inverse at all.
This is not the same as canceling modulo . An inverse of modulo exists exactly when . For example, 2 has no inverse modulo 6: multiplying any residue by 2 gives an even residue. A congruence may nevertheless be solvable; has solutions. Fermat's formula requires prime and ; a composite modulus or a multiple of invalidates that justification.
Counterexample mode
Canceling a common factor changes the modulus
Claim: implies . Take and . Then and , so the hypothesis holds, but is not divisible by . The repair is to cancel together with the modulus: , that is , and indeed . In the same way is solved by , which is the two residues and modulo ; check .
Common mistake
(Using Fermat's inverse formula for a composite modulus)
For and the formula gives , but . The inverse of modulo is , because . The exponent is justified only for a prime modulus and .
Worked problem: a non-invertible coefficient
Worked example 17.1.3
(A congruence with a non-invertible coefficient)
Solve . Here , and , so solutions exist. Divide by 2 to obtain . Euclid gives , so and . Hence . The two residues modulo 100 are and . Directly, and . Had the right side been 31, the gcd would not divide it and there would be no solution.
Extended Euclid constructs the coefficients, not merely the gcd. The ordinary algorithm replaces by until the remainder vanishes; back-substitution maintains an integer linear combination. With positive modulus, normalize a negative inverse using a modulo operation that returns the desired nonnegative representative. Programming-language remainder conventions differ, so normalize deliberately instead of assuming -7 % 50 is always 43.
Concept lensStructural
Solutions as a coset of a subgroup
In the additive group , the residues with form a subgroup . Because holds exactly when divides , we get , of order . If solves , the full solution set is the coset . For we have and , giving and . The image of is the subgroup of multiples of , so must lie in it.
Orientation uses signs, not slopes
Definition 17.1.4
(Orientation of three points)
For planar points define
A positive value is a left turn from directed to ; negative is a right turn; zero means collinear. This avoids division by a horizontal or vertical difference. For two nondegenerate closed segments and , strictly opposite orientation signs for relative to and for relative to establish a proper interior crossing. If an orientation is zero, check whether that point lies in the other segment's coordinate bounding box. Collinearity alone does not say whether segments overlap.
Worked problem: crossing and overlap
Worked example 17.1.5
(Crossing, overlapping and separated segments)
Let , , , . The orientations of C and D relative to AB are and ; those of A and B relative to CD are and . Both pairs are strictly opposite, so the segments cross properly. Their parametrizations and give , hence the unique intersection is .
Now keep A,B but use , . All four orientations vanish because the points lie on . Their intervals and overlap in , so the closed segments share the whole segment from to , not just a single point. If the second segment instead starts at and ends at , the same collinearity holds but the boxes are disjoint and the segments do not meet.
A point segment, where both endpoints coincide, should be handled as a point-on-segment test rather than relying on a “proper crossing” argument. If coordinates are integers, compute cross products in an integer type wide enough for both products and their difference. For large inputs the difference can overflow even if a single product fits. The bound must be derived from the coordinate limits and chosen representation; floating-point slopes are not a substitute for an overflow proof. A correct sign test with overflowed arithmetic is no longer a correct geometric test.
Common mistake
(Zero orientation does not mean overlap)
A zero cross product says only that three points are collinear. For , , , all four orientations vanish, yet and are disjoint, because their intervals and do not meet. After a zero orientation, always test the bounding boxes.
A check on the whole reduction
The congruence proof has both necessity and sufficiency; reporting only without constructing the reduced inverse leaves half the argument missing. The segment test also has two layers: strict signs settle a proper crossing, whereas zero signs require endpoint and overlap cases. Test a candidate on an ordinary instance, then deliberately try a shared endpoint, parallel overlap and separated collinear segments. These cases reveal assumptions that random-looking inputs often do not exercise.
Combining congruences without assuming coprimality
The familiar Chinese remainder theorem gives one residue class modulo when the moduli are coprime. If they share a divisor, compatibility must be checked first.
Theorem 17.1.6
(Compatibility of two congruences)
Let be positive integers and . The system , has a solution if and only if . In that case the solutions form exactly one residue class modulo , not necessarily modulo .
Proof
(Subtract for necessity, solve a congruence for sufficiency)
If , then is divisible by . Conversely let . The congruence has dividing its right side, so it has a solution by the solvability theorem above; then satisfies both congruences. If and are two solutions, is divisible by both and , hence by ; and adding a multiple of the lcm to a solution preserves both congruences. So the solutions form one class modulo the lcm.
Worked problem: compatible and incompatible remainders
Worked example 17.1.7
(Compatible and incompatible remainders)
Solve and . Their gcd is 2 and divides the difference , so the system is compatible. Write . The second condition becomes , equivalently . Since , and . Indeed 19 leaves remainders 1 and 3. In contrast, , has no solution: the difference 1 is not divisible by 2. Combining incompatible congruences as if the moduli were coprime can produce a plausible-looking integer that fails one of the original checks.
An implementation should handle a modulus of 1 consistently: it imposes no restriction on an integer. Intermediate products in extended Euclid and CRT can exceed the original inputs even if the final residue fits. The exact safe type depends on the algorithm and the allowed input bounds; reducing modulo a number after an overflow does not undo the overflow. A linear number of Euclid iterations in the input bit length does not mean each arithmetic operation has constant bit cost on arbitrarily large integers.
Turning the geometric test into a complete procedure
For a nondegenerate segment , define onSegment(A,B,P) to require both zero orientation and inclusion of in the respective closed coordinate intervals between A and B. For a pair of segments, first test the four strict orientations for a proper crossing. If any orientation is zero, test the corresponding endpoint with onSegment. This covers a shared endpoint and a collinear overlap. If a segment is a point, call the point-on-segment test on the other segment; if both are points, compare them. These conventions matter because changing from closed segments to open segments changes which endpoint contacts count.
An orientation value is twice a signed triangle area, but its magnitude is not a Euclidean distance. The sign alone decides left, right or collinear; a distance computation would involve a different normalization. When classifying a polygon, even a consistent local turn test assumes the stated vertex order and suitable hypotheses such as a simple polygon. A self-intersecting list of vertices requires a different interpretation of signed area and should not be silently treated as an ordinary simple polygon. Separate the mathematical input contract from the computational check that implements it.
Binary powers: preserve a product invariant
For a nonnegative integer exponent and integer modulus , square-and-multiply reduces each product modulo . Initially result=1 mod m, base=a mod m, e=E, where e is the unprocessed exponent. If e is odd, multiply result by base; in either parity, square base and replace e by its integer half. Exponent zero returns the multiplicative identity modulo ; when its canonical representative is 0. Negative exponents need an inverse and are outside this simple procedure.
Theorem 17.1.8
(The square-and-multiply invariant)
At the start of every round, result * base^e is congruent to modulo . In particular, when e=0 the value of result is .
Proof
(The invariant survives one round)
Initially result * base^e is . Suppose the invariant holds at the start of a round and write with . The round sets the new result to result * base^r, the new base to base^2 and the new exponent to , all modulo . Then new result times (new base) is congruent to result * base^r * base^(2q) result * base^e, which is congruent to . For the exponent strictly decreases to , so it reaches , where the invariant reads result .
Worked example 17.1.9
(Computing )
For example, compute . Start with result 1, base 3, exponent 13. The low bit is 1: result becomes 3; square to 9 and halve to 6. With exponent 6 the low bit is 0: retain result 3, square 9 to 13 modulo 17 and halve to 3. The low bit is 1: result becomes ; square 13 to 16 and halve to 1. The last bit is 1: result becomes ; exponent then becomes 0. The answer is 12. An implementation may omit the final unused square, but must still reduce intermediate products without overflow.
Repeated squaring takes logarithmically many arithmetic operations because the remaining exponent is halved each round. That count is distinct from the bit complexity of multiplying arbitrarily large integers, and distinct again from the cost of a modular multiplication routine that avoids fixed-width overflow. If and have a common divisor, the positive-power computation remains valid; only inverse-based reasoning requires coprimality. Distinguishing the algorithm's invariant from a theorem used to reduce the exponent prevents accidental use of Fermat's theorem outside its hypotheses.
For geometric code, a similar boundary audit applies to the cross-product sign. Subtract coordinates in a wide type before multiplying; casting only the already-overflowed result is too late. A double-precision approximation may be reasonable under an explicitly analyzed error tolerance, but in integer-coordinate tasks an exact sufficiently wide representation gives a direct equality-to-zero test. The input bound must cover subtraction, multiplication and the final difference, not just each coordinate separately.
A final check for the modular example is substitution into the original system, not just the reduced one. The 19 found above is 1 modulo 6 and 3 modulo 8, while adding the least common multiple 24 preserves both remainders. This confirms the displayed representative and explains how the full residue class is expressed.
Compatibility becomes a statement about the sum of two ideals.
A path to generalization
From integers to ideals
Compatibility becomes a statement about the sum of two ideals.
In , generates the ideal , so the condition says . In any commutative ring with ideals , the system , is solvable exactly when , and the solutions then form one class modulo . In the intersection of and is .
Exercises
Quick check
(Decide whether has a solution, and if so list all solutions modulo .)
Compute the gcd first.
Solution · Answer
Here and , so solutions exist. Dividing by gives . Since , the inverse of is , so . The residues modulo are , exactly of them. Check: , , .
Quick check
(Solve and .)
Check that divides .
Solution · Answer
divides , so the system is compatible. Write . The second condition is , that is , so . Taking gives , and the solutions are because . Check: and .
Quick check
(Do the closed segments from to and from to meet?)
All four points lie on one line.
Solution · Answer
All four orientations are zero, because all points lie on , so the strict-sign test does not apply. The bounding intervals and for (and likewise for ) share the value , and the point lies on both closed segments. So they meet in exactly one point, the shared endpoint .
Quick check
(Trace square-and-multiply for .)
Start with result 1, base 2, exponent 10.
Solution · Answer
Exponent 10 is even: result stays 1, base becomes , exponent 5. Exponent 5 is odd: result becomes , base becomes , exponent 2. Exponent 2 is even: base becomes , exponent 1. Exponent 1 is odd: result becomes , base becomes , exponent 0. The answer is , in agreement with .