Proving the Inverse Element in Modulo Multiplication?

[ForMyThunder]

This is a simple question from Groups and their Graphs by Grossman and Magnus that I just can't figure out:

Consider the set {1, 2, 3,..., p-1} where p is a prime number, with binary operation "multiplication modulo p." Show that for any element x of the set there is an element y of the set such that xy \equiv 1 (mod p).

I've gotten as far as having to show that x|(np+1) for some integer n.

 

[ThirstyDog]

To understand this try considering Linear Diophantine equations modulo p.

Note: gcd(x,p) = 1 for all 0 < x < p.

 

[matt grime]

In addition to using those facts from basic number theory, you might want to consider this idea, which is useful in general for understanding groups.Fix x. Suppose that {xy : y in {1,..,p-1}} doesn't contain 1. What can you say about its size? What does this imply by the pigeon hole principle? Mulitplication by a group element is an injective and surjective operation, and in fact 1 is not important, you could pick any z in 1,..,p-1 and for each x there is a y with xy=z.

 

[HallsofIvy]

Very nice, matt. That is clearly the way to go.

 

[ThirstyDog]

Very nice, matt. That is clearly the way to go.

Matt provides a nice statement which is conceptually useful in terms of groups but it doesn't answer the actual question. It assumes that the binary operation (along with the associated set) satisfy the group axioms. In which case it must be that every element x has an inverse.

It appeared to me that the goal of the question was to show that every element had an inverse along the way to proving it formed a group.

 

[matt grime]

I think you misunderstood me. I don't assume an inverse at all. The only assumption I make is that one has shown (or takes for granted) that multiplication is associative. If you follow through you will *prove* that every element has an inverse.

Your method is to invoke Euclid's algorithm. Mine is to use another fact from number theory. Let me explain it in full. Note that since p is prime p divides x(y-z) iff p divides x or p divides y-z, whence, by the pigeon hole principle it follows that given x, then xy=1 for _some_ y in {1,..,p-1}. Or in more words, if we fix x and let y vary over 1 to p-1, then the product xy varies over 1 to p-1 in some order (and in particular xy=1 for some choice of y).Thus we have just proved that it is a group operation. I have assumed nothing.

The reason this is nice is actually there is nothing special about 1 (though you can say the same for the Euclidean method), and it also highlights a technique which is quite useful: if you have some linear structure (addition), then showing two things are equal is the same as showing something else equals 0.

 

[ThirstyDog]

Ok. I interpreted what you said as multiplication by a group element is injective and surjective (hence invertible) thus proving 1 must lay in the set you defined, rather than you proving it is injective and hence invertible.

 

[HallsofIvy]

No, he is not saying that. He is simply saying that the set {0, 2, 3,..., p-1} is smaller than the set {0, 1, 2, 3, ..., p-1} so if xy is never equal to 1, there must exist two different values y1 and y2 such that xy1= xy2 (mod p) (they go into the same pigeon hole). That means that x(y1- y2)= ny1- ny2= 0 (mod p) so that x and (y1- y2) are factors of p.