Re: Reduced residue system modulo n prime p.

Saysero <saysero@xxxxxxxxx> wrote:

A book I am reading contains the following problem:
"If (r_1),...,(r_p) is any reduced residue system modulo n prime p,
prove that Prod{(r_j) | 1<=j<=p-1} is congruent to -1 modulo p."
What is "reduced residue system modulo n prime p"? What is the
difference between "reduced residue system modulo n prime p" and
normal reduced residue system modulo n?

To reduce a complete residue system simply select only those
elements coprime to the modulus, i.e. the invertibles (mod p)
Thus when the modulus p is prime you simply omit zero (mod p).

The problem is solved in exactly the same way as the additive
version you posted yesterday [1], namely, pair each element
with its inverse, i.e. exploit the INVOLUTION n -> 1/n. Again
see my prior posts [2] for more on the power of involutions.
This widely-known result is commonly called Wilson's Theorem.

--Bill Dubuque

[1] http://google.com/groups?selm=y8zej752cni.fsf%40nestle.csail.mit.edu
[2] http://google.com/groups/search?q=group:*math*+dubuque+wgd+involutions
.

Relevant Pages