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!

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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook