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.
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!
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.
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.
The other answers are not simple. Here is a simple proof:
Let $0 < x < m$, $\gcd(x,m)=1$, let $x'$ be the inverse of $x$, ie $x\cdot x'=1$ (such a number exists since $gcd(x,m)=1$).
If $x!=x'$, then $x\cdot x'=1$ else $x\cdot(m-x)=-x\cdot x=-1$ since $x=x'$ and $x\cdot x'=1$.
Note : if $\gcd(x,m)=1$, then $\gcd(m-x,m)=1$ trivially. Let $y(x)=x'$ if $x'!=x$ else $y(x)=m-x$.
Note : $y$ is trivially a bijective function with symmetric domain, range $x\cdot y=\pm 1$.
To compute $\prod \lbrace x | \gcd(x,m)=1\rbrace $, reduce subset $\lbrace x, y(x)\rbrace $ in $\lbrace x | \gcd(x,m)=1\rbrace$ to $\pm 1$ the product of $\pm 1 = \pm 1 \mod m$.
