Re: Reduced residue system modulo n prime p.

On Jun 11, 11:14 pm, Bill Dubuque <w...@xxxxxxxxxxxxxxxxxxxx> wrote:
Saysero <says...@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).

I know what reduced residue system is. If n=10 than one of the reduced
residue systems is {1,3,7,9}, right?
What I do not understand is what is "reduced residue system modulo n
prime p". Since my English is not very good and since it's grammar is
a lot different than of my native language I find this statement very
confusing. Is it reduced residue systems which is again reduced so
that every of its members is relatively prime to p? For example if
n=10 and p=3 than, how I understand what is said, the system they are
talking about is {1,7}. This, however, cannot be right because 7 is
not congruent to -1 modulo 3. So do they mean only that p is a prime
and nothing more?

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.

Isn't Wilson's Theorem something like (p-1)! is congruent to -1 modulo
p?
If 2<=j<=p-2 then there is 2<=i<=p-2 such that ij is congruent to 1
modulo p. Adding 1(p-1) is congruent to -1 modulo p one proves this
theorem. I think I could do something similar in this problem just I
do not understand it because of the (for me) confusing way it is
written.

--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
Quantcast