Solving a System of Congruences Using Chinese Remainder Theorem

[Hernaner28]

Homework Statement

Solve the following system:

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

Homework Equations

Chinese remainder theorem.

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}}<br /> x\equiv -1\left( \bmod 2 \right) \\<br /> x\equiv -1\left( \bmod 3 \right) \\<br /> x\equiv -1\left( \bmod 4 \right) \\<br /> x\equiv -1\left( \bmod 5 \right) \\<br /> x\equiv -1\left( \bmod 6 \right) \\<br /> x\equiv -1\left( \bmod 7 \right) \\<br /> x\equiv -1\left( \bmod 8 \right) \\<br /> x\equiv -1\left( \bmod 9 \right) \\<br /> \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!

 

[STEMucator]

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

 

[Hernaner28]

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

What do you suggest? THanks!

 

[STEMucator]

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

What do you suggest? THanks!

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.

 

[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

 

[STEMucator]

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

Thanks

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.

 

[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!

 

[STEMucator]

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!

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.

 

[Dick]

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!

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.

 

[Hernaner28]

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