10.8. Verifying the Solution

In regular algebra, you often come across linear equations of the forms a times x = b. In linear congruence, we are in the modular world, meaning everything is given some modulus. We want to find x such that ax ≡ b mod N.

In the realm of algebra, we frequently encounter equations like ax = b, where the variable x is computed by dividing b by a (assuming a ≠ 0). In linear congruences, however, the numbers involved operate within a defined boundary called a modulus. Instead of a single solution, there are generally multiple possible values of x that satisfy the condition ax ≡ b mod N, as this relates to the remainders when divided by N. Hence, our goal is to identify valid values for x that adhere to this congruence relation.

Consider you have a clock that runs on a 12-hour cycle. If you say it's 8 hours now, and you add 5 hours, instead of saying it's 13 o'clock, you'd say it's 1 o'clock the next cycle. Here, the clock is akin to our modulus, wrapping the numbers around once they exceed a certain point.

For example, if 6x ≡ 4 mod 10, possible solutions include x = 4 and x = 9. However, there are infinitely many solutions in the form of x = 4 + 10k, where k is any integer.

In our example of 6x ≡ 4 mod 10, we check different x values: for x = 4, we find that 64 = 24, which when divided by 10 leaves a remainder of 4. Similarly, for x = 9, 69 = 54 also gives a remainder of 4 when considered mod 10. This indicates that both values satisfy the congruence, and due to the nature of modular arithmetic, we can infinitely generate solutions by adjusting x with multiples of the modulus, 10 in this case.

Think of a number line that repeats every 10 steps. If you stand on '4' and move 10 steps, you end up back on '4' again. The same applies if you moved to '14' or '-6'—all these positions share the same property regarding modulo 10.

To solve linear congruences using the extended Euclid’s algorithm, we can multiply both sides by the multiplicative inverse of a, if GCD(a, N) = 1.

In modular arithmetic, finding an inverse means looking for an integer x such that (a * x) mod N = 1. For this inverse to exist, a must be coprime to N (GCD(a, N) = 1). Using the Extended Euclidean Algorithm, we can compute this inverse. After obtaining it, we can transform the equation, allowing us to express x in a manageable form, leading to a final solution that respects the original congruence.

Imagine trying to balance a scale. If weights on both sides aren’t balanced (i.e., GCD issues), adjusting one side slightly won’t help. However, if they are balanced (GCD = 1), you can manipulate one side to effectively find the right positioning—this is the core of finding inverses in congruences.

The CRT allows us to solve a system of linear congruences with pairwise coprime moduli, saying there's a unique solution modulo the product of these moduli.

The CRT presents a powerful strategy for dealing with multiple linear congruences simultaneously. When remainders from different moduli are coprime, the CRT guarantees that there exists a unique solution corresponding to the product of all moduli. It allows us to find one specific solution, which can then be adjusted into the required interval by considering the multiples of the product to obtain other valid solutions within the specified range.

Picture a detective trying to solve multiple alibis that don't overlap when examining the same crime; each alibi (the different moduli) must fit perfectly without contradiction (they are coprime). Once the conditions agree, you can find a unique truth or timeline of events (the unique solution), stemming from these diverse accounts.

--