Facebook Page
Twitter
RSS
+ Reply to Thread
Page 1 of 3 123 LastLast
Results 1 to 10 of 23
  1. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,256
    Thanks
    3,213 times
    Thanked
    972 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #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. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    I like Serena's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    6,537
    Thanks
    4,406 times
    Thanked
    12,271 times
    Thank/Post
    1.877
    Awards
    MHB Model Helper Award (2016)  

MHB Best Ideas (2016)  

MHB LaTeX Award (2016)  

MHB Calculus Award (2014)  

MHB Discrete Mathematics Award (Jul-Dec 2013)
    #2
    Quote Originally Posted by evinda View Post
    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?

  3. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,256
    Thanks
    3,213 times
    Thanked
    972 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #3 Thread Author
    Quote Originally Posted by I like Serena View Post
    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?

    Quote Originally Posted by I like Serena View Post

    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. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    I like Serena's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    6,537
    Thanks
    4,406 times
    Thanked
    12,271 times
    Thank/Post
    1.877
    Awards
    MHB Model Helper Award (2016)  

MHB Best Ideas (2016)  

MHB LaTeX Award (2016)  

MHB Calculus Award (2014)  

MHB Discrete Mathematics Award (Jul-Dec 2013)
    #4
    Quote Originally Posted by evinda View Post
    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?


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

  5. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,256
    Thanks
    3,213 times
    Thanked
    972 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #5 Thread Author
    Quote Originally Posted by I like Serena View Post
    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?

    Quote Originally Posted by I like Serena View Post
    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. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    I like Serena's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    6,537
    Thanks
    4,406 times
    Thanked
    12,271 times
    Thank/Post
    1.877
    Awards
    MHB Model Helper Award (2016)  

MHB Best Ideas (2016)  

MHB LaTeX Award (2016)  

MHB Calculus Award (2014)  

MHB Discrete Mathematics Award (Jul-Dec 2013)
    #6
    Quote Originally Posted by evinda View Post
    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.


    Quote Originally Posted by evinda View Post
    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.

  7. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,256
    Thanks
    3,213 times
    Thanked
    972 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #7 Thread Author
    Quote Originally Posted by I like Serena View Post

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


    Quote Originally Posted by I like Serena View Post

    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. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    I like Serena's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    6,537
    Thanks
    4,406 times
    Thanked
    12,271 times
    Thank/Post
    1.877
    Awards
    MHB Model Helper Award (2016)  

MHB Best Ideas (2016)  

MHB LaTeX Award (2016)  

MHB Calculus Award (2014)  

MHB Discrete Mathematics Award (Jul-Dec 2013)
    #8
    Quote Originally Posted by evinda View Post
    Which product do you mean?
    The product defined as B in the problem statement.

  9. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,256
    Thanks
    3,213 times
    Thanked
    972 times
    Awards
    MHB Model User Award (2016)  

MHB Model User Award (2014)
    #9 Thread Author
    Quote Originally Posted by I like Serena View Post
    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.

    Quote Originally Posted by I like Serena View Post
    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. MHB Seeker
    MHB Global Moderator
    MHB Math Scholar
    MHB Coder
    I like Serena's Avatar
    Status
    Offline
    Join Date
    Mar 2012
    Location
    Netherlands
    Posts
    6,537
    Thanks
    4,406 times
    Thanked
    12,271 times
    Thank/Post
    1.877
    Awards
    MHB Model Helper Award (2016)  

MHB Best Ideas (2016)  

MHB LaTeX Award (2016)  

MHB Calculus Award (2014)  

MHB Discrete Mathematics Award (Jul-Dec 2013)
    #10
    Quote Originally Posted by evinda View Post
    The product will be equal to $1$ in such a case.
    Indeed.

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

Similar Threads

  1. Product of seven integers
    By Evgeny.Makarov in forum Challenge Questions and Puzzles
    Replies: 6
    Last Post: February 10th, 2017, 18:00
  2. Properties of gcd's and relatively prime integers
    By Kiwi in forum Linear and Abstract Algebra
    Replies: 2
    Last Post: August 14th, 2015, 02:18
  3. Product of three integers
    By anemone in forum Challenge Questions and Puzzles
    Replies: 1
    Last Post: March 12th, 2014, 12:46
  4. Product of two integers
    By anemone in forum Challenge Questions and Puzzles
    Replies: 4
    Last Post: January 15th, 2014, 12:14
  5. Fractals in relatively prime integers
    By Gerasimov in forum Number Theory
    Replies: 4
    Last Post: September 19th, 2013, 16:21

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
Math Help Boards