Solving this congruence for all values of x

**Timbuk2**

I have the following congruence:

[latex] 9x \equiv 12 (mod 15)[/latex]

OK, so that seems fine. The gcd(9,15) is 3, and 3 divides 12 so there should be three mutually incongruent solutions.

I'm not going to post up everything I did, because it's quite long, but I used Euclid's Algorithm to express the gcd(12, 15) in the form

gcd(12,15) = s(12) + w(15), and I evaluated s to be 2.

The first solution is given by
[latex]x_0 = \displaystyle s(\frac{12}{gcd(9,15)})[/latex], which gives me 8.

To find the next solutions, I use the fact that every solution looks like

[latex] x = x_0 - y(\frac{15}{gcd(9,15)})[/latex], y = 1, ..., gcd(9,15)-1 (in this case, y is 1 and 2).

Putting in y=1 and y=2, I get two more solutions, 3 and -2.

Is this correct? The -2 looks wrong, even though it technically works.
But putting the congruence into this website, http://www.math.temple.edu/~renault/cryptology/congruences.html
gives 13, 8 and 3 as the answers. How did they get 13? Did I go wrong somewhere?

Sorry for the long post and the sloppy notation.

MathsManiac

When you're operating mod 15, then -2 and 13 are the same thing.

So your answers are consistent with the ones given on the website.

Does that answer your question?

**Timbuk2**

MathsManiac wrote: »

When you're operating mod 15, then -2 and 13 are the same thing.

So your answers are consistent with the ones given on the website.

Does that answer your question?

Thank you! I should have realised that!

That answers my question perfectly, thanks! I'm relieved - I thought I had gone seriously wrong somewhere, because I expected 13 to be my first value.

LeixlipRed

Remember a congruence like this is a linear diophantine equation. So if the gcd divides into the remainder that means there's infinitely many solutions to the LDE and a finite number of these solutions that lie inside the "window" of our mod n.