Results 1 to 10 of 10

Math Help - Modular systems?

  1. #1
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    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) \\<br />
                                        \ 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}<br />
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) \\<br />
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) \\<br />
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) \\<br />
\vdots \\<br />
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)<br />
\end{array}\right.
    Last edited by TriKri; December 6th 2006 at 06:02 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    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...
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    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.
    Last edited by TriKri; November 18th 2006 at 05:32 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member malaygoel's Avatar
    Joined
    May 2006
    From
    India
    Posts
    648
    Quote Originally Posted by TriKri View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    Let's se, we have

    \left\{\begin{array}{l}a \cdot x\ +\ b \cdot y\ \equiv\ e\ (\mbox {mod } n) \\<br />
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}<br />
gcd(b,\ n)\\gcd(d,\ m)<br />
\end{array}\!\!\!\begin{array}{l}<br />
\cdot\ y\ \equiv\ b'\cdot e\\\cdot\ y\ \equiv\ d'\cdot f<br />
\end{array}\!\!\!\begin{array}{l}<br />
-\ b'\cdot a\cdot x\\-\ d'\cdot c\cdot x<br />
\end{array}\begin{array}{l}<br />
(\text{mod }n)\\(\text{mod }m)<br />
\end{array}<br />
\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?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by TriKri View Post

    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    Quote Originally Posted by ThePerfectHacker View Post
    Just basically solve it like an ordinary 2x2 system of equations (except for division).
    But can you blend different equations with different modulus?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    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}<br />
    a\cdot x\ \! +\ b\cdot\ \! y\ \equiv\ e\ \ \! (\mbox{mod }n)\\<br />
    c\cdot x\  +\ d\cdot y\ \equiv\ f\ (\mbox{mod }m)<br />
\end{array}\right.

    We can make that

    \left\{\begin{array}{l}<br />
    \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))\\<br />
    \\<br />
    \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))<br />
\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}<br />
    a\cdot x\ \! +\ b\cdot\ \! y\ +\ e\ \ \! \equiv\ 0\ (\mbox{mod }n)\\<br />
    c\cdot x\  +\ d\cdot y\ +\ f\ \equiv\ 0\ (\mbox{mod }n)<br />
\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)\ -\ <br />
\frac{b}{gcd(b,\ d)} \cdot (c\cdot x\ +\ f)<br />
\ \equiv\ 0\ (\mbox{mod }n)

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

    \begin{array}{|c|}\hline\\\displaystyle{<br />
x\ \equiv\ <br />
\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)<br />
}\\\\\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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Senior Member TriKri's Avatar
    Joined
    Nov 2006
    Posts
    358
    Thanks
    1
    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}<br />
    e&\!\!\!\!\!|gcd(a,\ b,\ n&\!\!\!\!\!)\\<br />
    f&\!\!\!\!\!|gcd(c,\ d,\ m&\!\!\!\!\!)<br />
\end{array}\right.<br />

    I hope to get further soon.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Modular Arithmetic
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 24th 2011, 10:43 PM
  2. Replies: 0
    Last Post: February 13th 2011, 11:40 AM
  3. Modular Help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 11th 2010, 03:40 PM
  4. Modular
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: December 1st 2009, 11:16 AM
  5. Modular help
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 5th 2007, 11:53 AM

Search Tags


/mathhelpforum @mathhelpforum