[number theory] product of co primes congruent to 1 (mod m)

[RossH]

Homework Statement

Let b1 through b_phi(m) be integers between 1 and m that are coprime to m. Let B be the product of these integers. Show that B must be congruent to 1 or -1 (mod m)

Homework Equations

None.

The Attempt at a Solution

Well, I know that the quantity B appears during the proof of Euler's formula. That is, that a^phi(m) is congruent to 1 (mod m). So I probably have to work from there somehow. I have looked at Wilson's theorem, Euler's theorem, and Fermat's little Theorem. I'm not really sure where to go from here.

 

[micromass]

Can't you apply a proof which is similar to the proof of Wilson's theorem?

 

[RossH]

Can't you apply a proof which is similar to the proof of Wilson's theorem?

There is no requirement that m be a prime number. That's where I'm confused.

 

[micromass]

Allright, can you write the proof to Wilson's theorem here?? Then we can see if the proof is adaptable or not... (in fact: this theorem is a generalization of Wilson's theorem for non-primes, so I suspect that an analogous proof should do)

 

[RossH]

Allright, can you write the proof to Wilson's theorem here?? Then we can see if the proof is adaptable or not... (in fact: this theorem is a generalization of Wilson's theorem for non-primes, so I suspect that an analogous proof should do)

Okay, this is how I understand the proof:

To be proved: n>1 is prime iff (n-1)! is congruent to -1 (mod n)
This must be true for 2.
For all integers n>2 in m there exists b in m such that ab is congruent to 1 (mod n).
This b is unique (mod n) [I'm not sure why] and because n is prime, a is congruent to b iff a is 1 or n-1.

So it seems to me that this means that the numbers can be grouped into pairs, where each one will have a pair (b). a*b will always be congruent to 1 based on the number of pairs because n must be odd. No a will have the same pair so this modulus can be raised to an even power, to get 1 [I'm not quite sure why this works].

At least, this is my cursory understanding of the proof.

 

[micromass]

Good, now we're going to try to adapt this proof so that it works in this case.

Take b_1,...,b_{\phi(m)} the integers coprime to m. Our goal is to group them in pairs so that they cancel out.

Try to show the following: if b is coprime to m, then there is a unique a such that ab=1 (mod m). Furthermore, a is also coprime to m.