# 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 $\displaystyle 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, $\displaystyle \varphi(m)$ is the number of integers between 1 and m that are relatively prime to m, and let $\displaystyle B = b_1b_2b_3{\cdots}b_{\varphi(m)}$ be their product.
Please find a pattern for when $\displaystyle B\equiv1 ({\bmod}\ m)$ and when $\displaystyle B\equiv-1 ({\bmod}\ m)$.
Thanks and Regards.

2. ## Getting started...

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

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

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

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

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

Now, which is which? Overwhelmingly, $\displaystyle B_m\equiv-1(\bmod m)$, the exceptions being $\displaystyle 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 $\displaystyle n$ pairs of self-inverses, $\displaystyle B_m=(ab)_1(ab)_2...(ab)_n$ . For $\displaystyle B_m\equiv+1(\bmod m)$, there must be an even number of pairs $\displaystyle 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 $\displaystyle 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 $\displaystyle 7^n\equiv 1,7,5,13,3,21,15,17,9,19$, for $\displaystyle n=0,1,2,...,\phi(m)-1$. Since $\displaystyle 7^a7^b=7^{a+b}$, then $\displaystyle 7^a7^b\equiv 1$ if and only if $\displaystyle a+b$ is a multiple of $\displaystyle \phi(m)$. Therefore $\displaystyle 1\equiv7^0$ and $\displaystyle 21\equiv7^5$ is the only self-inverse modulo $\displaystyle 22$. Generalizing, if $\displaystyle m$ has a primitive root $\displaystyle p$, then $\displaystyle p^0$ and $\displaystyle p^{\phi(m)/2}$ are the only self-inverses modulo $\displaystyle m$.

Therefore, if m has a primitive root, its only self-inverses are the trivial 1 and m-1, whose product is -1, so $\displaystyle B_m\equiv-1$. So if $\displaystyle 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: $\displaystyle 8,12,15,16,20,21,...$ But $\displaystyle B_{20}$ and $\displaystyle B_{21}$ are the first examples of numbers in this sequence for which $\displaystyle B_m\equiv-1(\bmod m)$

4. ## Gaaaaahhh!

I made an error in calculation. $\displaystyle B_{20}$ and $\displaystyle B_{21}$ are in fact $\displaystyle \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. $\displaystyle B_{20}$ and $\displaystyle B_{21}$ are in fact $\displaystyle \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, $\displaystyle p^n$ or $\displaystyle 2p^n$, which p is an odd prime, there must be $\displaystyle B\equiv-1({\bmod}\ m)$, since there is no other one satisfies the congruence $\displaystyle x^2\equiv1({\bmod}\ m)$, excepting 1 and m - 1, I can not prove $\displaystyle B\equiv1({\bmod}\ m)$ when m is other integers.