I'm having a hard time showing this congruence has a unique solution modulo p.

[jdinatale]

Homework Statement

Prove that if p is a prime and a, b \in \mathbf{Z} with a \not \cong 0 \mod p, then ax \cong b \mod p has a unique solution modulo p.

I'm having a hard time proving there exists only one solution by using a contradiction.

But my biggest problem is that I don't understand why this statement should have a unique solution modulo p. For example, let a = 3, b = 2, and p = 2. Then 3x \cong 2 \mod 2 has multiple solutions. (x = 2,4,6,...) And that's just one example. Or does the "unique modulo p, mean that you take all of the solutions, and apply mod p to them and that is unique? For example (x = 2,4,6,...) mod p = 0.

Homework Equations

N/A

The Attempt at a Solution

 

[dynamicsolo]

Referring to your example, don't forget that for modulo 2 arithmetic, the only numbers are 0 and 1. So all the solutions you give (2, 4, 6, ...) are all "0" in mod 2.

In regards to your equation 3x \equiv 2 (mod 2), you are "allowed" to have the multiplicative factor be a number not in the system, but your equivalence is really 3x \equiv 0 (mod 2).

 

[jdinatale]

Referring to your example, don't forget that for modulo 2 arithmetic, the only numbers are 0 and 1. So all the solutions you give (2, 4, 6, ...) are all "0" in mod 2.

In regards to your equation 3x \equiv 2 (mod 2), you are "allowed" to have the multiplicative factor be a number not in the system, but your equivalence is really 3x \equiv 0 (mod 2).

Thank you, I now understand that. But I'm still have trouble devising a contradiction based on the knowledge that \frac{r + b}{a} and \frac{s + b}{a} are possible solutions. Since r and s are arbitrary integers, it's very difficult for me to manipulate them.

 

[dynamicsolo]

I think you're making trouble for yourself in that last statement, because indeed r and s can be any integers. You may have better luck if you look at differences, since (r - s) is an integer and all integer multiples of p are equivalent to 0 (mod p). So what is x - y , and what does that mean in modular arithmetic? [EDIT: oh yes, the requirement that p be a prime number is important in the argument.]

[Keep in mind that, in modular arithmetic, the only numbers are 0, 1, ... , (p-1) . So "a unique solution" means that there are not two possible results from that set, not that there is only a single answer in Z .]