# Prove that the product of coprimes must be congruent to $-1$ or $1 \pmod{m}$

I can't figure this problem out.

Let $b_1, b_2, \cdots, b_{\phi(m)}$ be the integers between $1$ and $m$ that are relatively prime to $m$. $B$ is the product of these integers. Prove that either $B$ is congruent to $1$ or $B$ is congruent to $-1 \pmod{m}$. Could you give me some hint where to start?

EDIT: Please avoid use of group theory. I am an undergrad in my first semester of number theory.

-
To my eye it seems like this question has been asked over and over again on this site recently. But perhaps this only comes by viewing the questions in the group-theoretic language (as Bill Dubuque has repeatedly, and correctly, done) -- does someone know if this exact question has actually been asked already? –  Pete L. Clark Feb 27 '11 at 1:56
Yes, it has. I've mentioned the group-theoretic viewpoint many times here, see e.g. this answer. Alas, the mods never close true duplicates, only misperceived ones. The logic escapes me. –  Bill Dubuque Feb 27 '11 at 2:21

The numbers $b_i$ you have are precisely the invertible elements modulo $m$, then you can pair them up with their inverses, which are also among the $b_i$. I think that this may help you figure out the rest. Try some numerical examples first so that you can see what's actually going on.

-
How can you pair them up with their inverses? Inverse of 7, for example, is 1/7, which is not an integer. I apologize if this is a stupid question. –  user7435 Feb 27 '11 at 1:51
@Ross: if $7$ is relatively prime to $m$, then there exists an integer $a$ such that $7a \equiv 1 \pmod m$. Thus $a$ can be thought of as the inverse of $7$ modulo m. If you are willing to think of the set of reduced residue classes mod $m$ as a group under multiplication, then this is very natural. If you have no familiarity with group theory, you should probably edit your question to say so, because to someone who does know group theory it is very tempting to answer your question using group-theoretic language. –  Pete L. Clark Feb 27 '11 at 1:52
Well for instance consider the case of $m = 5$. In this case you have $1, 2, 3, 4$ relatively prime to $5$. Then in the product $B = 1 \cdot 2 \cdot 3 \cdot 4$ you can regroup them as $B = 1 \cdot (2 \cdot 3) \cdot 4$ because $2 \cdot 3 \equiv 6 \equiv 1$ modulo $5$. But note that $4$ has no other number to group it with, and this is because it is its own inverse modulo $5$, since $4 \cdot 4 \equiv 16 \equiv 1$. Then this will remain in the product so $B = 4 \equiv -1$ modulo $5$. –  Adrián Barquero Feb 27 '11 at 1:54
Okay, so you have one pair that is congruent to -1 mod m, and one pair that is congruent to 1 mod m. This means that overall, your product would be congruent to 1*(-1) mod m, = -1, correct? If these pairs always exist, how would I prove this in the general case? –  user7435 Feb 27 '11 at 1:57
@Ross Well yes, in general you'll get some products $a \cdot b \equiv 1 \pmod{m}$ that will result from the groupings, but some other elements will still remain in the product because they're their own inverse, just as $4$ in the case $m = 5$. –  Adrián Barquero Feb 27 '11 at 2:02

The result in question is a generalization of Wilson's Theorem which was established by Gauss in his Disquisitiones Arithmeticae. This paper of C.S. Dalawat gives a nice treatment of this question and its number field analogues, suitable for students having taken a basic course in graduate level algebraic number theory.

(In the section on the Chinese Remainder Theorem in my commutative algebra notes, I pose this result as a problem and suggest that the reader try to prove a function field analogue of Dalawat's results. It seems like this should be rather straightforward, but I haven't actually tried it myself...)

Added: I decided that the group-theoretic version of Wilson's Theorem should appear in my handout on commutative groups, which is an algebraic supplement to notes for an advanced undergraduate number theory course I have taught twice at UGA. (It may help to explain that the prerequisite for this course is one semester of abstract algebra, but the standard first semester algebra course at UGA does not include any treatment of groups whatsoever!) So I wrote it up and included as an application the proof of Gauss's Theorem that the OP is asking about.

(I realize that by using a little group theory I am not meeting the request of the OP. Sorry about that. After thinking about it a little more, it is not so obvious to me how to remove the group theory from the argument! One could look in Gauss's Disquisitiones Arithmeticae...but I don't recommend that. Those who have read this book closely tell me that it shows that Gauss most definitely knew about finite commutative groups when he wrote it -- he just doesn't use any explicitly group-theoretic language. This makes some of his arguments rather difficult to read.)

Then I got curious and searched on MathSciNet for the sources for this folkloric "Wilson's Theorem in a Finite Commutative Group". My search began very auspiciously: here is a 1903 paper by the early American group theorist G.A. Miller which proves the result. In fact, comparing my two-page writeup to Miller's two-and-a-half-page paper I found the resemblance to be uncanny. The only significant difference is that he does not mention Gauss at all (nor in fact does he reference anything that does not appear in an American journal; perhaps he was making a point by doing so).

What about after 1903? The result appears in the middle of a long, strange 1958 Monthly article of Vandiver and Weaver. (Check out MathReview MR0105386 for a bemused and somewhat critical review; my reaction was similar.) And then it appears (though it is not stated as a theorem or given a name) in the first paragraph of Dalawat's 2009 paper linked to above. This note of B. Sury gives an interesting partial generalization to finite noncommutative groups (in which case one must consider the issue of all possible ways to take the product, making the problem significantly more complicated). Also Bill Dubuque has written informally on this subject several times in recent years. And that's all I found!

-
Waaaay over my head. I'm a first semester undergrad in this, and really bad at number theory anyway. –  user7435 Feb 27 '11 at 2:07
It's worth warning readers that Dalawat's paper will be mostly incomprehensible to anyone lacking strong knowledge of algebraic number theory. I hesitated to mention group theoretic generalizations - let alone generalizations to algebraic number fields. –  Bill Dubuque Feb 27 '11 at 2:07
@Bill: I agree, and I tried to do so with the phrasing "suitable for students having taken a basic course in graduate level algebraic number theory". (Although in fact the proof of Gauss's Theorem outlined in Section 2 should be accessible to undergraduates with a good background in group theory.) –  Pete L. Clark Feb 27 '11 at 2:20
@Ross: I sympathize. As I mentioned in a comment to Adrian's answer, I suggest that you edit your question to specifically indicate that you want a solution that avoids all use of group theory. –  Pete L. Clark Feb 27 '11 at 2:21
Thanks. I missed your first comment. Edited the question. –  user7435 Feb 27 '11 at 2:25

HINT $\$ It's a special case of Wilson's theorem for groups, i.e. exploit the innate inversion symmetry to pair up inverses - see my answer here.

-