1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: System of congruences

  1. Apr 23, 2013 #1
    1. The problem statement, all variables and given/known data
    Solve the following system:

    [tex] \displaystyle \left\{ \begin{array}{*{35}{l}}
    x\equiv 1\left( \bmod 2 \right) \\
    x\equiv 2\left( \bmod 3 \right) \\
    x\equiv 3\left( \bmod 4 \right) \\
    x\equiv 4\left( \bmod 5 \right) \\
    x\equiv 5\left( \bmod 6 \right) \\
    x\equiv 6\left( \bmod 7 \right) \\
    x\equiv 7\left( \bmod 8 \right) \\
    x\equiv 8\left( \bmod 9 \right) \\
    \end{array} \right.[/tex]

    2. Relevant equations
    Chinese remainder theorem.

    3. The attempt at a solution

    Well, what I did was to substract the module in each equation, so now I have:

    [tex] \displaystyle \left\{ \begin{array}{*{35}{l}}
    x\equiv -1\left( \bmod 2 \right) \\
    x\equiv -1\left( \bmod 3 \right) \\
    x\equiv -1\left( \bmod 4 \right) \\
    x\equiv -1\left( \bmod 5 \right) \\
    x\equiv -1\left( \bmod 6 \right) \\
    x\equiv -1\left( \bmod 7 \right) \\
    x\equiv -1\left( \bmod 8 \right) \\
    x\equiv -1\left( \bmod 9 \right) \\
    \end{array} \right.[/tex]

    Now, if I try to solve one equation and then replace in the next it would be a tedious work to do. I've seen chinese remainder theorem but it doesn't help me, or at least I don't realize. What can I do next to simplify this system?

  2. jcsd
  3. Apr 23, 2013 #2


    User Avatar
    Homework Helper

    Are you familiar with the linear congruence theorem?

    Suppose ##a,b,n \in \mathbb{Z}, \space n>0##

    Then ##ax \equiv bmodn \space## has a solution for x ##⇔ gcd(a,n)|b##.
  4. Apr 23, 2013 #3
    Yes. That follows from the solutions for the linear diophantine equations.

    What do you suggest? THanks!
  5. Apr 23, 2013 #4


    User Avatar
    Homework Helper

    With multiple applications of the theorem, you will be able to solve your system. Are you also familiar with the Extended Euclidean algorithm? It is also very important for solving linear congruences.
  6. Apr 23, 2013 #5
    Yes. I know how to solve this kind of systems. To do that I always use the extended euclidean algorithm to compute the inverse of a (in the equation you wrote). But in this particular problem I have 8 equations and it would be tedious to solve one, and then replace it in the next, and then again same thing until I get to the solution.
    I wonder if there's something I can do to simplify the system (e.g. remove redundant equations or change something).

  7. Apr 23, 2013 #6


    User Avatar
    Homework Helper

    Hmm I wouldn't be familiar with any methods beyond the theorem and the algorithm. Sure it's cumbersome, but if it's for a homework assignment or something, I'm sure it's intended to get you used to calculating quickly and to hammer the concepts in ( So I can understand why it's so long ).

    EDIT : You could write out each relation as a set and then take the intersection of your set to be the solution x as well? Otherwise I think multiple substitutions is the only way.
  8. Apr 23, 2013 #7
    I've looked at the solution and the next step was to say that system is equivalent to:

    [tex] \displaystyle x\equiv -1\left( \bmod {{3}^{2}}\cdot {{2}^{3}}\cdot 7\cdot 5 \right)[/tex]

    which is a piece of cake. Even so, I do not understand what was done there. It's not the factorization of 9x8x7x6x5x2 . What is it then?

  9. Apr 23, 2013 #8


    User Avatar
    Homework Helper

    Yes that is the case. x = 2519 is the solution to your system.

    The way it was obtained more than likely was multiple applications of the E.E.A. The set intersecton idea I wrote out in my last post works, but is probably better for smaller systems of equations unless you can see the pattern ahead of time.
    Last edited: Apr 23, 2013
  10. Apr 23, 2013 #9


    User Avatar
    Science Advisor
    Homework Helper

    It's the least common multiple of 2,3,4,5,6,7,8,9. Any common multiple would work, but the least one will give you the smallest solution.
  11. Apr 23, 2013 #10
    Ahh I see, that's it, the least common multiple. Thanks both!!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted