remainder of the product of the relatively prime numbers

**whodsow** · May 28th 2009, 04:59 AM

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.

**Media_Man** · May 28th 2009, 07:06 AM

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?

**Media_Man** · May 28th 2009, 07:42 AM

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)$

**Media_Man** · May 28th 2009, 08:48 AM

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.

**whodsow** · May 29th 2009, 07:26 AM

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.

**whodsow** · May 29th 2009, 10:30 AM

Thread: remainder of the product of the relatively prime numbers

LinkBack

Thread Tools

Display

remainder of the product of the relatively prime numbers

Getting started...

Reading up...

Gaaaaahhh!

Similar Math Help Forum Discussions

Using the fact that a pair of numbers is relatively prime to prove that one is prime

Show that every positive number n can be represented as a product of prime numbers.

[SOLVED] Remainder when large numbers divided

Finding remainder in non-prime congruence

Product of two prime cycles

Search Tags