# Homework Help: System of congruences

1. Apr 23, 2013

### Hernaner28

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

$$\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.$$

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:

$$\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.$$

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?

Thanks!

2. Apr 23, 2013

### Zondrina

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

3. Apr 23, 2013

### Hernaner28

Yes. That follows from the solutions for the linear diophantine equations.

What do you suggest? THanks!

4. Apr 23, 2013

### Zondrina

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.

5. Apr 23, 2013

### Hernaner28

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

Thanks

6. Apr 23, 2013

### Zondrina

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.

7. Apr 23, 2013

### Hernaner28

I've looked at the solution and the next step was to say that system is equivalent to:

$$\displaystyle x\equiv -1\left( \bmod {{3}^{2}}\cdot {{2}^{3}}\cdot 7\cdot 5 \right)$$

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?

Thanks!

8. Apr 23, 2013

### Zondrina

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
9. Apr 23, 2013

### Dick

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.

10. Apr 23, 2013

### Hernaner28

Ahh I see, that's it, the least common multiple. Thanks both!!