Thread: What am i doing wrong?

Hi,

Im trying to solve the Congruence system:



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 [LaTeX ERROR: Convert failed]

Where [LaTeX ERROR: Convert failed]
This gives [LaTeX ERROR: Convert failed]

Now we have [LaTeX ERROR: Convert failed]

Again calculate u and v such that 221u+12v=1
5*221-92*12 = 1
[LaTeX ERROR: Convert failed]

And Finally the general solution is [LaTeX ERROR: Convert failed]

[LaTeX ERROR: Convert failed]

But the correct answer, according to the book should be [LaTeX ERROR: Convert failed]

What am i doing wrong ?

Originally Posted by Jones

Im trying to solve the Congruence system:



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

Where
This gives

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.

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?

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

We want to solve the congruences . That means that x is a multiple of 17, plus 7; and a multiple of 13, plus 9. Therefore (for some integers p and q), from which .

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 . Use the same procedure here. The equations tell us that . 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.

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 . That means that x is a multiple of 17, plus 7; and a multiple of 13, plus 9. Therefore (for some integers p and q), from which .

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 . Use the same procedure here. The equations tell us that . 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

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