# Thread: Product of integers that are relatively prime to m

Originally Posted by I like Serena

Suppose we have a $b_i$ such that it is its own inverse.
That is, $b_i^2 = 1 \pmod m$.
Can we pair it with another number that is also its own inverse?
How does that work out in the examples?
You mean that if $b_j^2 \equiv 1 \pmod m, i \neq j$, to find the product $b_i \cdot b_j \pmod{m}$ ?

2. Originally Posted by evinda
You mean that if $b_j^2 \equiv 1 \pmod m, i \neq j$, to find the product $b_i \cdot b_j \pmod{m}$ ?
Yes.
And perhaps we can be a bit 'smart' about selecting $j$.

Originally Posted by I like Serena
Yes.
And perhaps we can be a bit 'smart' about selecting $j$.
For $m=8$ the product will be $1 \cdot 3 \cdot 5 \cdot 7 \equiv 1 \pmod{8}$ and for $m=10$ it will be $1 \cdot 9 \pmod{10} \equiv -1 \pmod{10}$.

So we don't take all the numbers of which the inverses are the numbers itselves? How can we choose $j$ ?

4. Originally Posted by evinda
For $m=8$ the product will be $1 \cdot 3 \cdot 5 \cdot 7 \equiv 1 \pmod{8}$ and for $m=10$ it will be $1 \cdot 9 \pmod{10} \equiv -1 \pmod{10}$.

So we don't take all the numbers of which the inverses are the numbers itselves? How can we choose $j$ ?
For $m=10$, we have $1\cdot 3\cdot 7\cdot 9 \equiv (3 \cdot 3^{-1}) \cdot (1\cdot -1) \equiv 1 \cdot -1 \equiv -1$.
And for $m=8$, we have $1\cdot 3\cdot 5\cdot 7 \equiv (1 \cdot -1) \cdot (3 \cdot -3) \equiv -1 \cdot -1 \equiv 1$.
Is there a pattern that we can exploit?

Originally Posted by I like Serena
For $m=10$, we have $1\cdot 3\cdot 7\cdot 9 \equiv (3 \cdot 3^{-1}) \cdot (1\cdot -1) \equiv 1 \cdot -1 \equiv -1$.
And for $m=8$, we have $1\cdot 3\cdot 5\cdot 7 \equiv (1 \cdot -1) \cdot (3 \cdot -3) \equiv -1 \cdot -1 \equiv 1$.
Is there a pattern that we can exploit?
We have the following:

$m=8=4\cdot 2$ :

$1\cdot 3\cdot 5\cdot 7 \equiv 1\cdot 3\cdot (-3)\cdot (-1) \equiv (-1^2)\cdot (-3^2)\equiv (-1) \cdot (-1) \equiv 1$

$m=10=2\cdot 5$ :

$1\cdot 3\cdot 7\cdot 9 \equiv 1\cdot 3\cdot 3^{-1}\cdot(-1) \equiv -1^2\cdot (3\cdot 3^{-1}) \equiv (-1) \cdot 1 \equiv -1$

$m=12=4\cdot 3$ :

$1\cdot 5\cdot 7\cdot 11 \equiv 1\cdot 5\cdot (-5)\cdot (-1) \equiv (-1) \cdot (-1) \equiv 1$

$m=14=2\cdot 7$ :

$1\cdot 3\cdot 5\cdot 9\cdot 11\cdot 13 \equiv 1\cdot 3\cdot 3^{-1}\cdot 9\cdot 9^{-1}\cdot (-1) \equiv (-1^2)\cdot (3\cdot 3^{-1})\cdot (9\cdot 9^{-1})\equiv (-1)\cdot 1\cdot 1\equiv -1$

$m=16=4\cdot 4$ :

$1\cdot 3\cdot 5\cdot 7\cdot 9\cdot 11\cdot 13\cdot 15 \equiv 1\cdot 3\cdot 5\cdot 7\cdot (-7)\cdot 3^{-1}\cdot 5^{-1}\cdot (-1) \equiv (-1^2) \cdot (3\cdot 3^{-1})\cdot (5\cdot 5^{-1})\cdot (7\cdot (-7))\equiv (-1)\cdot 1\cdot 1\cdot (-1)\equiv 1$

Does it hold in the general case that when $m$ is a multiple of $4$ the result is $1$ and when $m$ is a multiple of $2$ but not of $4$ the result is $-1$?

6. Originally Posted by evinda
Does it hold in the general case that when $m$ is a multiple of $4$ the result is $1$ and when $m$ is a multiple of $2$ but not of $4$ the result is $-1$?
Let's check.
For $m=4$ we have $1\cdot 3\equiv 1 \cdot -1 \equiv -1$.
No, I don't think it holds.

Still, isn't there a pattern that we can either pair a number with its multiplicative inverse, or we can pair it with its additive inverse?
Is that always possible?
And can we always tell what the product will be of such a pair?

Originally Posted by I like Serena
Let's check.
For $m=4$ we have $1\cdot 3\equiv 1 \cdot -1 \equiv -1$.
No, I don't think it holds.
I see...

Originally Posted by I like Serena
Still, isn't there a pattern that we can either pair a number with its multiplicative inverse, or we can pair it with its additive inverse?
Is that always possible?
And can we always tell what the product will be of such a pair?
I can't think of a pattern... Could you give me a hint?

8. Originally Posted by evinda
I can't think of a pattern... Could you give me a hint?
First things first, can we conclude that the product B will always be either +1 or -1?
That was after all the first question in the OP.
Can we prove it?

I have thought the following:

We want to examine the product $B=b_1 b_2 \cdots b_{\phi(m)}$.

If $\exists j \in \{2, \ldots , \phi(m)-1\}$ such that $b_j^{-1}\not\equiv b_j\mod m$ then at the product $b_2\cdot \ldots \cdot b_{\phi(m)-1}$ there is a pair such that their product is equal to $1$.

Let $b_k$ be the modular inverse of $b_j$, i.e., $b_j^{-1}\equiv b_k\mod m$.

We get that \begin{align*}b_2\cdot b_3 \cdot \ldots \cdot b_j\cdot \ldots b_k\cdot \ldots \cdot b_{\phi(m)-1}&\equiv b_2\cdot b_3 \cdot \ldots \cdot b_j\cdot \ldots b_j^{-1}\cdot \ldots \cdot b_{\phi(m)-1} \\ & \equiv b_2\cdot b_3 \cdot \ldots \cdot (b_j\cdot b_j^{-1})\cdot \ldots \cdot b_{\phi(m)-1} \\ & \equiv b_2\cdot b_3 \cdot \ldots \cdot 1\cdot \ldots \cdot b_{\phi(m)-1}\end{align*}

If $\exists r\in \{2, \ldots , \phi(m)-1\}$ such that $b_r^{-1}\equiv b_r\mod m$ then we have that $b_r^2\equiv 1\mod m$.

In this case we cannot find two different factors of the product, $b_i$ and $b_r$ with $i\neq r$, such that their product is equal to $1$.

We define $n:=m-b_r$ and we get $n\equiv -b_r\mod m$.

It holds that $(n,m)=(-b_r,m)=(b_r,m)=1$, i.e., $n$ and $m$ are comprime, so $n$ is one of the $b_i$'s with $i\neq r$, i.e., $n:=b_i$.

So, we get that

\begin{align*}b_2\cdot b_3 \cdot \ldots \cdot b_r\cdot \ldots b_i\cdot \ldots \cdot b_{\phi(m)-1}&\equiv b_2\cdot b_3 \cdot \ldots \cdot b_r\cdot \ldots (-b_r)\cdot \ldots \cdot b_{\phi(m)-1} \\ & \equiv b_2\cdot b_3 \cdot \ldots \cdot (-b_r^2)\cdot \ldots \cdot b_{\phi(m)-1} \\ & \equiv b_2\cdot b_3 \cdot \ldots \cdot (-1)\cdot \ldots \cdot b_{\phi(m)-1}\end{align*}

Continuing in the same way , the product $b_2 b_3 \cdots b_{\phi(m)-1}$ will be equal either to $1$ or to $-1$.

So $B=1 \cdot b_2 \cdots b_{\phi(m)-1} (m-1) \equiv -1 \cdot b_2 \cdots b_{\phi(m)-1} \equiv \pm 1 \pmod{m}$.

Am I right?

10. Erm... this is bit much...
Starting somewhere, what happened to $b_1$ and $b_{\phi(m)}$?