# Thread: remainder of the product of the relatively prime numbers

1. ## remainder of the product of the relatively prime numbers

Hi all, I had a problem, pls help me.
Let $b_1 < b_2 < \cdots < b_{\varphi(m)}$ be the integers between 1 and m that are relatively prime to m (including 1), of course, $\varphi(m)$ is the number of integers between 1 and m that are relatively prime to m, and let $B = b_1b_2b_3{\cdots}b_{\varphi(m)}$ be their product.
Please find a pattern for when $B\equiv1 ({\bmod}\ m)$ and when $B\equiv-1 ({\bmod}\ m)$.
Thanks and Regards.

2. ## Getting started...

Define $B_m$="the product of the totatives of m"= $\prod_{(k,m)=1}k$ as per your statement.

It is known that $k$ has an inverse modulo $m$ iff $(k,m)=1$, therefore, every $k$ in the above product is either it's own inverse, $k^2\equiv1(\bmod m)$, or can be "matched" with its inverse $kk^{-1}\equiv1(\bmod m)$

The "matched" factors disappear from the product, so $B_m=\prod_{k^2\equiv1}k$ which is always inclusive of $1$ and $m-1$ (do you see why?)

Also, since $\phi(m)$ is always even, and we've removed an even number of factors, there are always an even number of $k$'s which are their own inverse modulo $m$, for any $m$.

So, what is the product of these self-inverses? Well, if a and b are both self-inverses then $a^2b^2=(ab)^2\equiv1(\bmod m)$, so $ab\equiv\pm1(\bmod m)$. This proves that $B_m\equiv\pm1(\bmod m)$ for all $m$.

Now, which is which? Overwhelmingly, $B_m\equiv-1(\bmod m)$, the exceptions being $m=8,12,15,16,18,24,...$ I am having difficulty picking out a pattern in this sequence, and I don't believe any kind of formula can express it. However, we've shown that our product is the product of $n$ pairs of self-inverses, $B_m=(ab)_1(ab)_2...(ab)_n$ . For $B_m\equiv+1(\bmod m)$, there must be an even number of pairs $ab\equiv-1(\bmod m)$

This is getting somewhat beyond me, here. Are there any known rules dictating the square roots of 1 modulo m?

Always learning new stuff

If $m$ has a primitive root, then all totatives of m can be expressed as powers of that root. For example, the first primitive root of 22 is 7, and $7^n\equiv 1,7,5,13,3,21,15,17,9,19$, for $n=0,1,2,...,\phi(m)-1$. Since $7^a7^b=7^{a+b}$, then $7^a7^b\equiv 1$ if and only if $a+b$ is a multiple of $\phi(m)$. Therefore $1\equiv7^0$ and $21\equiv7^5$ is the only self-inverse modulo $22$. Generalizing, if $m$ has a primitive root $p$, then $p^0$ and $p^{\phi(m)/2}$ are the only self-inverses modulo $m$.

Therefore, if m has a primitive root, its only self-inverses are the trivial 1 and m-1, whose product is -1, so $B_m\equiv-1$. So if $B_m=+1$, m does not have a primitive root. However the converse is not true.

The first few numbers lacking a primitive root are: $8,12,15,16,20,21,...$ But $B_{20}$ and $B_{21}$ are the first examples of numbers in this sequence for which $B_m\equiv-1(\bmod m)$

4. ## Gaaaaahhh!

I made an error in calculation. $B_{20}$ and $B_{21}$ are in fact $\equiv+1$ and the converse of the above theorem is in fact true (I just haven't yet worked out the proof.) Your problem has to do with a generalization of Wilson's Theorem: Wilson's Theorem -- from Wolfram MathWorld

It sucks to be wrong, but I think I got pretty far.

5. Originally Posted by Media_Man
I made an error in calculation. $B_{20}$ and $B_{21}$ are in fact $\equiv+1$ and the converse of the above theorem is in fact true (I just haven't yet worked out the proof.) Your problem has to do with a generalization of Wilson's Theorem: Wilson's Theorem -- from Wolfram MathWorld

It sucks to be wrong, but I think I got pretty far.
Thank you spending so much time to do me a big favor, I'm so glad getting it, but I can not prove completely Gauss's generalization of Wilson's theorem.
I only proved:
if m = 4, $p^n$ or $2p^n$, which p is an odd prime, there must be $B\equiv-1({\bmod}\ m)$, since there is no other one satisfies the congruence $x^2\equiv1({\bmod}\ m)$, excepting 1 and m - 1, I can not prove $B\equiv1({\bmod}\ m)$ when m is other integers.