• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter jdinatale
  • Start date
  • #1
155
0

Homework Statement


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.


Homework Equations


N/A

The Attempt at a Solution



logico3.jpg
 

Answers and Replies

  • #2
dynamicsolo
Homework Helper
1,648
4
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).
 
  • #3
155
0
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).
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.
 
  • #4
dynamicsolo
Homework Helper
1,648
4
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:

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

  • Last Post
Replies
4
Views
3K
Replies
2
Views
1K
  • Last Post
Replies
3
Views
1K
Replies
1
Views
1K
  • Last Post
Replies
1
Views
4K
Replies
0
Views
9K
Replies
4
Views
3K
Top