1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Sep 5, 2011 #1
    1. The problem statement, all variables and given/known data
    Prove that if [itex]p[/itex] is a prime and [itex]a, b \in \mathbf{Z}[/itex] with [itex]a \not \cong 0 \mod p[/itex], then [itex]ax \cong b \mod p[/itex] has a unique solution modulo [itex]p[/itex].

    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 [itex]3x \cong 2 \mod 2[/itex] 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.

    2. Relevant equations

    3. The attempt at a solution

  2. jcsd
  3. Sep 5, 2011 #2


    User Avatar
    Homework Helper

    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 [itex]3x \equiv 2 [/itex] (mod 2), you are "allowed" to have the multiplicative factor be a number not in the system, but your equivalence is really [itex]3x \equiv 0 [/itex] (mod 2).
  4. Sep 5, 2011 #3
    Thank you, I now understand that. But I'm still have trouble devising a contradiction based on the knowledge that [itex]\frac{r + b}{a}[/itex] and [itex]\frac{s + b}{a}[/itex] are possible solutions. Since r and s are arbitrary integers, it's very difficult for me to manipulate them.
  5. Sep 5, 2011 #4


    User Avatar
    Homework Helper

    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 .]
    Last edited: Sep 5, 2011
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook