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
 
1
@interact(layout=[['a_1','n_1'],['a_2','n_2'],['a_3','n_3']])
2
def _(a_1=(r'\(a_1\)',1), a_2=(r'\(a_2\)',1), a_3=(r'\(a_3\)',1), n_1=(r'\(n_1\)',6), n_2=(r'\(n_2\)',10), n_3=(r'\(n_3\)',14)):
3
    try:
4
        answer = []
5
        for i in [1..n_1*n_2*n_3]:
6
            if (i%n_1 == a_1) and (i%n_2 == a_2) and (i%n_3 == a_3):
7
              answer.append(i)
8
        string1 = r"<ul><li>$x\equiv %s \text{ (mod }%s)$</li>"%(a_1,n_1)
9
        string2 = r"<li>$x\equiv %s \text{ (mod }%s)$</li>"%(a_2,n_2)
10
        string3 = r"<li>$x\equiv %s \text{ (mod }%s)$</li></ul>"%(a_3,n_3)
11
        pretty_print(html("The simultaneous solutions to "))
12
        pretty_print(html(string1+string2+string3))
13
        if len(answer)==0:
14
            pretty_print(html("are none"))
15
        else:
16
            pretty_print(html("all have the form "))
17
            for ans in answer:
18
                pretty_print(html("$%s$ modulo $%s$"%(ans,n_1*n_2*n_3)))
19
    except ValueError as e:
20
        pretty_print(html("Make sure the moduli are appropriate for solving!"))
21
        pretty_print(html("Sage gives the error message:"))
22
        pretty_print(html(e))

    
    
    
    
        
            
                Language:
                
            
        
    
    




    
    
        
        Messages

🔗

Playing with this interact should reveal that sometimes there isn’t any solution at all, and that when there are multiple solutions they are actually congruent modulo a smaller number! (See Exercise 5.6.24 for the latter.)

🔗

As previously mentioned, Qin discovered a very general method for getting answers in this situation. From his method, he seems to have been aware that an answer exists as long as

gcd (n_{i}, n_{j})

divides

a_{i} - a_{j}

for all

i

and

j,

though he did not explicitly state (and certainly did not prove) it. V.-A. Lebèsgue

⁴

www-history.mcs.st-andrews.ac.uk/Biographies/Lebesgue_Victor.html

was the first to rediscover this latter fact in the modern era, in 1859. (See [E.7.44] for a comparative analysis with some Indian and European developments.)

🔗

Subsection 5.5.2 The case of coefficients

🔗

Another case is that of congruences not of the form

x \equiv a (mod n),

but of the form

A x \equiv B (mod n) .

What can we say when there are coefficients for the variable in our linear system?

🔗

If you have simultaneous congruences with coefficients,

A_{i} x \equiv B_{i} (mod N_{i})

🔗

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.

🔗

Example 5.5.1.

🔗

For instance, try now to solve this system:

$2 x \equiv 2$ (mod $5$ )
$5 x \equiv 4$ (mod $6$ )
$3 x \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.5.

🔗

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.5.

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 [E.2.4, Chapter 3.3] for a basic example and a reference.

Prev Top Next