# Math Help - Modular systems?

1. ## Modular systems?

I don't know what they are called, but i found some good pdf describing them some time ago, now it's lost. I have been searching for "modular systems" but I haven't found anything of worth. Is that their real name or are they called anything else?

An example:

$\left\{\begin{array}{cc}a \cdot x\ +\ b \cdot y\ \equiv\ e\ (\mbox {mod } n) \\
\ c \cdot x\ +\ d \cdot y\ \equiv\ f\ (\mbox {mod } m) \end{array}\right.$

Edit: Oops, I obviously forgot the most important part...

Edit: The next thing to do when I have find a good-looking symetrical solution for this systemis to solve this system:

$\left\{\begin{array}{l}
a_{1,1}\cdot x_1\ +\ a_{1,2}\cdot x_2\ +\ a_{1,3}\cdot x_3\ +\ ...\ a_{1,n}\cdot x_n\ \equiv\ r_1\ (\text{mod }m_1) \\
a_{2,1}\cdot x_1\ +\ a_{2,2}\cdot x_2\ +\ a_{2,3}\cdot x_3\ +\ ...\ a_{2,n}\cdot x_n\ \equiv\ r_2\ (\text{mod }m_2) \\
a_{3,1}\cdot x_1\ +\ a_{3,2}\cdot x_2\ +\ a_{3,3}\cdot x_3\ +\ ...\ a_{3,n}\cdot x_n\ \equiv\ r_3\ (\text{mod }m_3) \\
\vdots \\
a_{n,1}\cdot x_1\ +\ a_{n,2}\cdot x_2\ +\ a_{n,3}\cdot x_3\ +\ ...\ a_{n,n}\cdot x_n\ \equiv\ r_n\ (\text{mod }m_n)
\end{array}\right.$

2. It is called "modular arithmetic". It first appeared in Disquitiones Arithmetic in 1801 by Gauss. They are powerful because they over simplify divisibility arguments.

Simple,
$a\equiv b(\mbox{ mod }n)$
Means,
$n$ divides $a-b$

3. I don't know if you got my question properly, since I realized i wasn't finished with it. Searching at "Modolar arithmetic" didn't get me much further...

4. I mean the type of equation system, what is it called? And if it is just "modular arithmetic", which I can't find anything about that explains about equation systems of that kind, how do you solve the equation I gave as an example in the first post? Thanks in advance.

5. Originally Posted by TriKri
I mean the type of equation system, what is it called? And if it is just "modular arithmetic", which I can't find anything about that explains about equation systems of that kind, how do you solve the equation I gave as an example in the first post? Thanks in advance.
I don't clearly understand what you want but if you want to solve the equations, you can use Chinese Remainder theorem
Chinese Remainder Theorem

Keep Smiling
Malay

6. Let's se, we have

$\left\{\begin{array}{l}a \cdot x\ +\ b \cdot y\ \equiv\ e\ (\mbox {mod } n) \\
c \cdot x\ +\ d \cdot y\ \equiv\ f\ (\mbox {mod } m) \end{array}\right.$

$b\cdot y\ \equiv\ e - a\cdot x\ (\text{mod }n)$

Set $b'$ so that $b'\cdot b\ \equiv\ gcd(b,\ n)\ (\text{mod }n)$

$b'\cdot b\cdot y\ \equiv\ b'\cdot(e - a\cdot x)\ (\text{mod }n)$
$gcd(b,\ n)\cdot y\ \equiv\ b'\cdot e - b'\cdot a\cdot x\ (\text{mod }n)$

If we do the same with the other equation we get:

$\left\{\begin{array}{l}
gcd(b,\ n)\\gcd(d,\ m)
\end{array}\!\!\!\begin{array}{l}
\cdot\ y\ \equiv\ b'\cdot e\\\cdot\ y\ \equiv\ d'\cdot f
\end{array}\!\!\!\begin{array}{l}
-\ b'\cdot a\cdot x\\-\ d'\cdot c\cdot x
\end{array}\begin{array}{l}
(\text{mod }n)\\(\text{mod }m)
\end{array}
\right.$

This is how far I get. Does anyone know any way to simplify it a bit? Maybe how to get rid of the coefficients in front of y?

7. Originally Posted by TriKri

Set $b'$ so that $b'\cdot b\ \equiv\ gcd(b,\ n)\ (\text{mod }n)$
What are you doing!

$b'\cdot b\cdot y\ \equiv\ b'\cdot(e - a\cdot x)\ (\text{mod }n)$
$gcd(b,\ n)\cdot y\ \equiv\ b'\cdot e - b'\cdot a\cdot x\ (\text{mod }n)$

Maybe how to get rid of the coefficients in front of y?
There is no general way to remove the the coefficient. But there is a theorem that gaurrentes the existence and all incongruent solutions that you obtain.

Just basically solve it like an ordinary 2x2 system of equations (except for division). I can do if for you if you want by an example.

8. Originally Posted by ThePerfectHacker
Just basically solve it like an ordinary 2x2 system of equations (except for division).
But can you blend different equations with different modulus?

9. Oh, okey I see now.

Let's define $\frac{\square}{\square}$ as it is normally defined, a rational number without mind of modulus, and $\square/\square\ (\text{mod }\square)$ as integer modulus division, in other words, if $c\ =\ a/b\ (\text{mod }n)$, then $c$ is such that $b\cdot c\ \equiv\ a\ (\text{mod }n)$, not necessarily the lowest possible positive integer; that's possible only if $gcd(b, n)|a$, else $c$ is undefined. We could really say that $b\cdot c\ \equiv\ a\ +\ j\cdot n\ (\text{mod }n)$, where $j$ is an arbitrary integer, so $c$ can actually be $\equiv\ a/b\ +\ j\cdot(n/b)\ (\text{mod }n)$, let's say only one $c$-value per $j$-value.

$\left\{\begin{array}{l}
a\cdot x\ \! +\ b\cdot\ \! y\ \equiv\ e\ \ \! (\mbox{mod }n)\\
c\cdot x\ +\ d\cdot y\ \equiv\ f\ (\mbox{mod }m)
\end{array}\right.$

We can make that

$\left\{\begin{array}{l}
\displaystyle\frac{m}{gcd(n,\ m)}\cdot(a\cdot x\ \! +\ b\cdot\ \! y)\ \equiv\ \displaystyle\frac{m}{gcd(n,\ m)}\cdot e\ \ \! (\mbox{mod }lcm(n,\ m))\\
\\
\displaystyle\frac{n}{gcd(n,\ m)}\cdot(c\cdot x\ +\ d\cdot y)\ \equiv\ \displaystyle\frac{n}{gcd(n,\ m)}\cdot f\ (\mbox{mod }lcm(n,\ m))
\end{array}\right.$

So that we have the same modulus in both equations. The conditions are still the same. And we can assume every system already is in that form, only using one modulus. And $e$ and $f$ we can move over to the left side instead. So our new system is:

$\left\{\begin{array}{l}
a\cdot x\ \! +\ b\cdot\ \! y\ +\ e\ \ \! \equiv\ 0\ (\mbox{mod }n)\\
c\cdot x\ +\ d\cdot y\ +\ f\ \equiv\ 0\ (\mbox{mod }n)
\end{array}\right.$

$\frac{d}{gcd(b,\ d)} \cdot (a\cdot x\ +\ b\cdot y\ +\ e)\ \equiv\ 0\ (\mbox{mod }n)$

$lcm(b,\ d)\cdot y\ +\ \frac{d}{gcd(b,\ d)} \cdot (a\cdot x\ +\ e)\ \equiv\ 0\ (\mbox{mod }n)$

In the same way we can get

$lcm(b,\ d)\cdot y\ +\ \frac{b}{gcd(b,\ d)} \cdot (c\cdot x\ +\ f)\ \equiv\ 0\ (\mbox{mod }n)$

By subtracting these two equations we get

$\frac{d}{gcd(b,\ d)} \cdot (a\cdot x\ +\ e)\ -\
\frac{b}{gcd(b,\ d)} \cdot (c\cdot x\ +\ f)
\ \equiv\ 0\ (\mbox{mod }n)$

$\frac{d\cdot a\ -\ b\cdot c}{gcd(b,\ d)}\cdot x
\ \equiv\
\frac{b\cdot f\ -\ d\cdot e}{gcd(b,\ d)}\ +\ j\cdot n\ (\mbox{mod }n)$

$\begin{array}{|c|}\hline\\\displaystyle{
x\ \equiv\
\frac{b\cdot f\ -\ d\cdot e}{gcd(b,\ d)}\left/\frac{d\cdot a\ -\ b\cdot c}{gcd(b,\ d)}\right.\ +\ j\cdot\left(n\left/\frac{d\cdot a\ -\ b\cdot c}{gcd(b,\ d)}\right.\right)\ (\mbox{mod }n)
}\\\\\hline\end{array}$

Now we can insert that to one of the original equations:

$a\cdot x\ +\ b\cdot y\ +\ e\ \equiv\ 0\ (\text{mod }n)$

$b\cdot y\ \equiv\ -a\cdot x\ -\ e\ +\ i\cdot n\ (\text{mod }n)$

$y\ \equiv\ (-a\cdot x\ -\ e)/b\ +\ i\cdot(n/b)\ (\text{mod }n)$

Now I don't know if it even is correct. And if it should be correct it is probably not possible to follow the development in both directions. If it is correct and it can be followed in both directions, this solution should give all valid values for $x$ and $y$ and nothing more.

Equations with modular arithmetic is a lot more messy than "normal" linear equations, so it is highly possible that many steps in this derivation is illegal.

10. No, I don't know how to solve it. It is obviously wrong, one among the reasons is that the final solution is completely unsymmetrical, while the problem statement is perfectly symmetrical.

One thing I have come up with is that if any solutions exists this must be satisfied:

$\left\{\begin{array}{rll}
e&\!\!\!\!\!|gcd(a,\ b,\ n&\!\!\!\!\!)\\
f&\!\!\!\!\!|gcd(c,\ d,\ m&\!\!\!\!\!)
\end{array}\right.
$

I hope to get further soon.