# Thread: What am i doing wrong?

1. ## What am i doing wrong?

Hi,

Im trying to solve the Congruence system:

$\displaystyle \begin{cases} X & \equiv 7 \pmod{17} \\ X & \equiv 9 \pmod{13} \\ X & \equiv 3 \pmod {12} \\ \end{cases}$

My solution looks like this:
First find u and v such that 17u+13v = 1
Quickly calculated to be 4*13-3*17 = 1

Now $\displaystyle \begin{cases}x_{0} & \pmod {17*13} \\ 3 & \pmod {12} \end{cases}$

Where $\displaystyle x_0 = a_2m_1u+a_1m_2v$
This gives $\displaystyle 13*17*4-3*7*13 = 339$

Now we have $\displaystyle \begin{cases} 339 & \pmod {221} \\ 3 &\pmod {12}\end{cases}$

Again calculate u and v such that 221u+12v=1
5*221-92*12 = 1
$\displaystyle x_0 = 3*221*5-92*339*12$

And Finally the general solution is $\displaystyle x = x_0+nm_1m_2$

$\displaystyle {\color{red}\text My solution } x = -370941+2652n$

But the correct answer, according to the book should be $\displaystyle x = 2115 + 2652n$

What am i doing wrong ?

2. Originally Posted by Jones
Im trying to solve the Congruence system:

$\displaystyle \begin{cases} X & \equiv 7 \pmod{17} \\ X & \equiv 9 \pmod{13} \\ X & \equiv 3 \pmod {12} \\ \end{cases}$

My solution looks like this:
First find u and v such that 17u+13v = 1
Quickly calculated to be 4*13-3*17 = 1

Now $\displaystyle \begin{cases}x_{0} & \pmod {17*13} \\ 3 & \pmod {12} \end{cases}$

Where $\displaystyle x_0 = a_2m_1u+a_1m_2v$
This gives $\displaystyle {\color{red}9}*17*4-3*7*13 = 339$
I'm not familiar with that formula for x_0, but it gives the wrong answer: 339 is not congruent to 7 mod 17, nor to 9 mod 13. The smallest number that does have these properties is 126, and the next one is 347.

3. Originally Posted by Opalg
I'm not familiar with that formula for x_0, but it gives the wrong answer: 339 is not congruent to 7 mod 17, nor to 9 mod 13. The smallest number that does have these properties is 126, and the next one is 347.
Hmm, ok.

How would you do?

4. There may be more systematic ways of doing it, but here's how I would go about it.

We want to solve the congruences $\displaystyle \begin{cases}x & \equiv 7\!\!\pmod{17} \\ x& \equiv 9\!\! \pmod{13}\end{cases}$. That means that x is a multiple of 17, plus 7; and a multiple of 13, plus 9. Therefore $\displaystyle x = 17p+7=13q+9$ (for some integers p and q), from which $\displaystyle 13q-17p = 7-9=-2$.

But we know that 13*4 - 17*3=1. Multiply that by -2 to get 13*(-8) - 17*(-6)=-2. Therefore one solution for p and q is q=-8, p=-6. The corresponding value of x is x=-95 (=13*(-8)+9). However, we can add any multiple of 13*17=221 to that, and get another solution for x. It's usually convenient to work with the smallest positive solution, so we'll take x=-95+221=126.

To complete the solution, we need to solve the congruences $\displaystyle \begin{cases}x&\equiv 126 \!\! \pmod {221} \\ x&\equiv 3 \!\!\pmod {12}\end{cases}$. Use the same procedure here. The equations $\displaystyle x = 221p + 126 = 12q + 3$ tell us that $\displaystyle 221p - 12q = 3-126=-123$. But we know that 221*5 - 12*92 = 1. Multiply by -123 to get 221*(-615) - 12*(-11316) = -123. So we can take p=-615, giving x=221*(-615)+126=-135789. But we can adjust this by adding any multiple of 12*221=2652, so a better solution would be x=-135789+52*2652=2115.

That gives the answer you want: z = 2115 + 2652n.

5. Originally Posted by Opalg
There may be more systematic ways of doing it, but here's how I would go about it.

We want to solve the congruences $\displaystyle \begin{cases}x & \equiv 7\!\!\pmod{17} \\ x& \equiv 9\!\! \pmod{13}\end{cases}$. That means that x is a multiple of 17, plus 7; and a multiple of 13, plus 9. Therefore $\displaystyle x = 17p+7=13q+9$ (for some integers p and q), from which $\displaystyle 13q-17p = 7-9=-2$.

But we know that 13*4 - 17*3=1. Multiply that by -2 to get 13*(-8) - 17*(-6)=-2. Therefore one solution for p and q is q=-8, p=-6. The corresponding value of x is x=-95 (=13*(-8)+9). However, we can add any multiple of 13*17=221 to that, and get another solution for x. It's usually convenient to work with the smallest positive solution, so we'll take x=-95+221=126.

To complete the solution, we need to solve the congruences $\displaystyle \begin{cases}x&\equiv 126 \!\! \pmod {221} \\ x&\equiv 3 \!\!\pmod {12}\end{cases}$. Use the same procedure here. The equations $\displaystyle x = 221p + 126 = 12q + 3$ tell us that $\displaystyle 221p - 12q = 3-126=-123$. But we know that 221*5 - 12*92 = 1. Multiply by -123 to get 221*(-615) - 12*(-11316) = -123. So we can take p=-615, giving x=221*(-615)+126=-135789. But we can adjust this by adding any multiple of 12*221=2652, so a better solution would be x=-135789+52*2652=2115.

That gives the answer you want: z = 2115 + 2652n.
Thank you sweetheart

6. Originally Posted by Opalg
I'm not familiar with that formula for x_0, but it gives the wrong answer: 339 is not congruent to 7 mod 17, nor to 9 mod 13. The smallest number that does have these properties is 126, and the next one is 347.
Hi,

I mixed up the formula. It should be: [Math] 7*13*4-3*9*17[/tex]
which is $\displaystyle -95 \pmod{221} \longrightarrow 126 \pmod{221}$