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
    N/A

    3. The attempt at a solution

    logico3.jpg
     
  2. jcsd
  3. Sep 5, 2011 #2

    dynamicsolo

    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

    dynamicsolo

    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