Section 5.5 More Complicated Cases
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 thexxxxxxxxxx
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))
Subsection 5.5.2 The case of coefficients
Another case is that of congruences not of the formExample 5.5.1.
For instance, try now to solve this system:
(mod ) (mod ) (mod )
Surprised? Don't forget to get back to the original modulus!
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
and modulo those moduli and add the two huge numbers in each of those moduli.Then the CRT allows you to put
modulo each of the moduli back together for a complete solution!