NTIC More Complicated Cases

Section 5.5 More Complicated Cases

Solving linear congruences is a completely solved problem (up to computer power). Although one does not usually cover all extensions in an introductory course, the following subsections will introduce some, without full detail.

🔗

Subsection 5.5.1 Moduli which are not coprime

🔗

What happens if, in a system of congruences, we don't have the enviable situation where all the

$n_i$ are relatively prime? Let's go back to the interact from before one last time, with some moduli which are not pairwise coprime, and see if we get anything.

xxxxxxxxxx
 
@interact(layout=[['a_1','n_1'],['a_2','n_2'],['a_3','n_3']])
def _(a_1=(r'\(a_1\)',1), a_2=(r'\(a_2\)',2), a_3=(r'\(a_3\)',3), n_1=(r'\(n_1\)',5), n_2=(r'\(n_2\)',6), n_3=(r'\(n_3\)',7)):
    try:
        answer = []
        for i in [1..n_1*n_2*n_3]:
            if (i%n_1 == a_1) and (i%n_2 == a_2) and (i%n_3 == a_3):
              answer.append(i)
        string1 = r"<ul><li>$x\equiv %s \text{ (mod }%s)$</li>"%(a_1,n_1)
        string2 = r"<li>$x\equiv %s \text{ (mod }%s)$</li>"%(a_2,n_2)
        string3 = r"<li>$x\equiv %s \text{ (mod }%s)$</li></ul>"%(a_3,n_3)
        pretty_print(html("The simultaneous solutions to "))
        pretty_print(html(string1+string2+string3))
        if len(answer)==0:
            pretty_print(html("are none"))
        else:
            pretty_print(html("all have the form "))
            for ans in answer:
                pretty_print(html("$%s$ modulo $%s$"%(ans,n_1*n_2*n_3)))
    except ValueError as e:
        pretty_print(html("Make sure the moduli are appropriate for solving!"))
        pretty_print(html("Sage gives the error message:"))
        pretty_print(html(e))

🔗

As previously mentioned, Qin discovered a very general method for getting answers in this situation. An answer exists as long as

$\gcd(n_i,n_j)$ divides

$a_i-a_j$ for all

$i$ and

$j\text{.}$ V.-A. Lebèsgue was the first to rediscover this in the modern era, in 1859.

🔗

Subsection 5.5.2 The case of coefficients

🔗

Another case is that of congruences not of the form

$x \equiv a\text{ (mod }n)\text{,}$ but of the form

$Ax\equiv B\text{ (mod }n)\text{.}$ What can we say when there are coefficients for the variable in our linear system?

🔗

If you have simultaneous congruences with coefficients,

$\begin{equation*} A_ix\equiv B_i\text{ (mod }N_i) \end{equation*}$

🔗

then first write their individual solutions in the form

$x\equiv a_i$ (mod

$n_i$ ). Then you can use the CRT to get a solution of that system, which is also a solution of the ‘big’ system.

🔗

For instance, try now to solve

$2x\equiv 2$ (mod $5$ )
$5x\equiv 4$ (mod $6$ )
$3x\equiv 2$ (mod $7$ )

🔗

Surprised? Don't forget to get back to the original modulus!

🔗

See also Example 6.5.2 for combining these ideas with those of Proposition 5.4.4.

🔗

Subsection 5.5.3 A practical application

🔗

Finally, there is a practical application. Suppose you are adding two very large numbers – too big for your computer! How would you do it? The answer is one can use the CRT, in particular the ideas of Proposition 5.4.4.

First, pick a few mutually coprime moduli smaller than the biggest you can add on your computer.
Then, reduce your two numbers $x$ and $y$ modulo those moduli and add the two huge numbers in each of those moduli.
Then the CRT allows you to put $x+y$ modulo each of the moduli back together for a complete solution!

🔗

Needless to say, we won't do an actual example of this. See [C.2.4, Chapter 3.3] for a basic example and a reference.