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

1. Hello!!!

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?

2. Originally Posted by evinda
Hello!!!

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!!

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

Originally Posted by I like Serena
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?

Originally Posted by I like Serena

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?

4. Originally Posted by evinda
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?

Originally Posted by evinda
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?
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?
And while we're at it, what is the product?

Originally Posted by I like Serena
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?

Originally Posted by I like Serena
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?
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}$.

6. Originally Posted by evinda
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.

Originally Posted by evinda
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?

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

Originally Posted by I like Serena

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

Originally Posted by I like Serena

Otherwise we can find the product by pairing each number with its inverse.
What would the product be then?
Which product do you mean?

8. Originally Posted by evinda
Which product do you mean?
The product defined as B in the problem statement.

Originally Posted by I like Serena
Otherwise we can find the product by pairing each number with its inverse.
What would the product be then?
The product will be equal to $1$ in such a case.

Originally Posted by I like Serena
However, we can't do that when the inverse is the same number as the original number.
Yes. What can we do in this case?

10. Originally Posted by evinda
The product will be equal to $1$ in such a case.
Indeed.

Originally Posted by evinda
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?