Product of integers that are relatively prime to m

[evinda]

Hello! (Wave)Let $b_1< b_2< \dots< b_{\phi(m)}$ be the integers between $1$ and $m$ that are relatively prime to $m$ (including 1), and let $B=b_1 b_2 b_3 \cdots b_{\phi(m)}$ be their product.
I want to show that either $B \equiv 1 \pmod{m}$ or $B \equiv -1 \pmod{m}$ .
Also I want to find a pattern for when $B$ is equal to $+1 \pmod{m}$ and when it is equal to $-1 \pmod{m}$.I have thought the following:

We have that $(b_i, m)=1, \forall i=1, \dots, \phi(m)$.
So there are $x_i, y_i \in \mathbb{Z}$ such that $x_i b_i+ y_i m=1$.

Then we have that $x_1 \cdot x_2 \cdots x_{\phi(m)} \cdot b_1 \cdot b_2 \cdots b_{\phi(m)} \equiv 1 \pmod{m} \Rightarrow x_1 \cdot x_2 \cdots x_{\phi(m)} \cdot B \equiv 1 \pmod{m}$.

So we need to show that $x_1 \cdot x_2 \cdots x_{\phi(m)} \equiv \pm 1 \pmod{m}$. How can we show this?

 

[I like Serena]

Hello! (Wave)Let $b_1< b_2< \dots< b_{\phi(m)}$ be the integers between $1$ and $m$ that are relatively prime to $m$ (including 1), and let $B=b_1 b_2 b_3 \cdots b_{\phi(m)}$ be their product.
I want to show that either $B \equiv 1 \pmod{m}$ or $B \equiv -1 \pmod{m}$ .
Also I want to find a pattern for when $B$ is equal to $+1 \pmod{m}$ and when it is equal to $-1 \pmod{m}$.I have thought the following:

We have that $(b_i, m)=1, \forall i=1, \dots, \phi(m)$.
So there are $x_i, y_i \in \mathbb{Z}$ such that $x_i b_i+ y_i m=1$.

Then we have that $x_1 \cdot x_2 \cdots x_{\phi(m)} \cdot b_1 \cdot b_2 \cdots b_{\phi(m)} \equiv 1 \pmod{m} \Rightarrow x_1 \cdot x_2 \cdots x_{\phi(m)} \cdot B \equiv 1 \pmod{m}$.

So we need to show that $x_1 \cdot x_2 \cdots x_{\phi(m)} \equiv \pm 1 \pmod{m}$. How can we show this?

Hey evinda! (Smile)

Don't these numbers form a multiplicative group?
If so, can we find a unique and different inverse for each of the elements?

 

[evinda]

Don't these numbers form a multiplicative group?

To show this, we set $S:=\{ b_1, b_2, \dots, b_{\phi(m)} \}$.

Since $(1,m)=1$, $1$ is an element of $S$.

Then we pick an arbitrary $b_i$ , where $i \in \{1,2, \dots, \phi(m) \}$ and we want to find its inverse.

Since $(b_i,m)=1$ we have that there is some $x_i \in \mathbb{Z}$ such that $x_i b_i \equiv 1 \pmod{m}$ for some $x_i \in \mathbb{Z}$.

So now we want to show that $x_i$ is relatively prime to $m$.

This is implied from the fact that all the numbers that have an inverse are relatively prime to $m$.

So $x_i$ will be equal to one of the $b_1, b_2, \dots, b_{\phi(m)}$.

Is this right?

If so, can we find a unique and different inverse for each of the elements?

In order to show this, we suppose that $x_i b_i \equiv 1 \pmod{m}$ and $x_i b_j \equiv 1 \pmod{m}$.

So $(x_i b_i-x_i b_j) \equiv 0 \pmod{m} \Rightarrow m \mid x_i (b_i-b_j)$.

Since $(m,x_i)=1$ , it must hold that $b_i-b_j \equiv 0 \pmod{m}$, i.e. $b_i \equiv b_j \pmod{m}$.

Since $1 \leq b_i, b_j \leq m$, it follows that $b_i=b_j$.

So each element of the set $S$ has a different inverse.

Am I right? (Thinking)

 

[I like Serena]

So now we want to show that $x_i$ is relatively prime to $m$.

This is implied from the fact that all the numbers that have an inverse are relatively prime to $m$.

How so?

Btw, don't we have that $b_i^{\phi(m)}\equiv 1 \pmod m$?
Can we deduce what the inverse is from that?

In order to show this, we suppose that $x_i b_i \equiv 1 \pmod{m}$ and $x_i b_j \equiv 1 \pmod{m}$.

So $(x_i b_i-x_i b_j) \equiv 0 \pmod{m} \Rightarrow m \mid x_i (b_i-b_j)$.

Since $(m,x_i)=1$ , it must hold that $b_i-b_j \equiv 0 \pmod{m}$, i.e. $b_i \equiv b_j \pmod{m}$.

Since $1 \leq b_i, b_j \leq m$, it follows that $b_i=b_j$.

So each element of the set $S$ has a different inverse.

Am I right? (Thinking)

Let's pick a couple of examples.
How about $m=8$ and $m=10$?
Which numbers do we have? And what are the respective inverses? Are they distinct? (Wondering)
And while we're at it, what is the product?

 

[evinda]

How so?

Btw, don't we have that $b_i^{\phi(m)}\equiv 1 \pmod m$?
Can we deduce what the inverse is from that?

From the fact that $b_i^{\phi(m)}\equiv 1 \pmod m$, we have that $b_i \cdot b_i^{\phi(m)-1} \equiv 1 \pmod m$.
So the inverse of $b_i$ $\pmod{m}$ is $b_i^{\phi(m)-1}$.
Right?

Let's pick a couple of examples.
How about $m=8$ and $m=10$?
Which numbers do we have? And what are the respective inverses? Are they distinct? (Wondering)
And while we're at it, what is the product?

For $m=8$, we have the numbers $1,3,5,7$. Their inverses are respectively $1,3,5,7$.
For $m=10$, we have the numbers $1,3,7,9$. Their inverses are respectively $1,7,3,9$.

We see that the inverses are distinct.

We see that $1 \cdot 3 \cdot 5 \cdot 7 \equiv 1 \pmod{8}$ and $1 \cdot 3 \cdot 7 \cdot 9 \equiv -1 \pmod{10}$.

 

[I like Serena]

From the fact that $b_i^{\phi(m)}\equiv 1 \pmod m$, we have that $b_i \cdot b_i^{\phi(m)-1} \equiv 1 \pmod m$.
So the inverse of $b_i$ $\pmod{m}$ is $b_i^{\phi(m)-1}$.
Right?

Right.

For $m=8$, we have the numbers $1,3,5,7$. Their inverses are respectively $1,3,5,7$.
For $m=10$, we have the numbers $1,3,7,9$. Their inverses are respectively $1,7,3,9$.

We see that the inverses are distinct.

We see that $1 \cdot 3 \cdot 5 \cdot 7 \equiv 1 \pmod{8}$ and $1 \cdot 3 \cdot 7 \cdot 9 \equiv -1 \pmod{10}$.

With $m=8$ we have that $3^{-1}\equiv 3 \pmod 8$.
What I meant is that $3^{-1}=3$ is not distinct from $3$.
Otherwise we can find the product by pairing each number with its inverse.
What would the product be then? (Wondering)

However, we can't do that when the inverse is the same number as the original number. (Thinking)

 

[evinda]

With $m=8$ we have that $3^{-1}\equiv 3 \pmod 8$.
What I meant is that $3^{-1}=3$ is not distinct from $3$.

(Nod)

Otherwise we can find the product by pairing each number with its inverse.
What would the product be then? (Wondering)

Which product do you mean?

 

[I like Serena]

Which product do you mean?

The product defined as B in the problem statement. (Thinking)

 

[evinda]

Otherwise we can find the product by pairing each number with its inverse.
What would the product be then? (Wondering)

The product will be equal to $1$ in such a case.

However, we can't do that when the inverse is the same number as the original number. (Thinking)

Yes. What can we do in this case? (Thinking)

 

[I like Serena]

The product will be equal to $1$ in such a case.

Indeed.

Yes. What can we do in this case?

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? (Thinking)

 

[evinda]

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? (Thinking)

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}$ ?

 

[I like Serena]

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$. (Thinking)

 

[evinda]

Yes.
And perhaps we can be a bit 'smart' about selecting $j$. (Thinking)

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

 

[I like Serena]

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? (Wondering)

 

[evinda]

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? (Wondering)

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

 

[I like Serena]

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. (Worried)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? (Wondering)

 

[evinda]

Let's check.
For $m=4$ we have $1\cdot 3\equiv 1 \cdot -1 \equiv -1$.
No, I don't think it holds. (Worried)

I see... (Nod)

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? (Wondering)

I can't think of a pattern... (Sweating) Could you give me a hint?

 

[I like Serena]

I can't think of a pattern... (Sweating) 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? (Wondering)

 

[evinda]

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?

 

[I like Serena]

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

 

[evinda]

Starting somewhere, what happened to $b_1$ and $b_{\phi(m)}$? (Wondering)

$b_1$ is always $1$ and $b_{\phi(m)}$ is always equal to $m-1$.

 

[I like Serena]

$b_1$ is always $1$ and $b_{\phi(m)}$ is always equal to $m-1$.

Ah, okay. Perhaps it'd be useful to mention that. (Angel)
In particular it means that whatever $m$ is, 1 and -1 will always be their own inverse, and they will from a pair that are additive inverses.
(Assuming $m>2$.)

Otherwise, it seems your proof is correct. (Happy)

 

[evinda]

Ah, okay. Perhaps it'd be useful to mention that. (Angel)

Yes, I agree... (Nod) (Blush)

In particular it means that whatever $m$ is, 1 and -1 will always be their own inverse, and they will from a pair that are additive inverses.
(Assuming $m>2$.)

(Nod)

Otherwise, it seems your proof is correct. (Happy)

Nice... Thank you! (Clapping)