Facebook Page
Twitter
RSS
+ Reply to Thread
Page 2 of 3 FirstFirst 123 LastLast
Results 11 to 20 of 23
  1. MHB Master
    MHB Site Helper
    MHB Math Helper
    evinda's Avatar
    Status
    Offline
    Join Date
    Apr 2013
    Posts
    3,226
    Thanks
    3,187 times
    Thanked
    966 times
    Awards
    MHB Model User Award (2016)  

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

    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. 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,357
    Thanks
    4,304 times
    Thanked
    11,953 times
    Thank/Post
    1.880
    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)
    #12
    Quote Originally Posted by evinda View Post
    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$.

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

MHB Model User Award (2014)
    #13 Thread Author
    Quote Originally Posted by I like Serena View Post
    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. 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,357
    Thanks
    4,304 times
    Thanked
    11,953 times
    Thank/Post
    1.880
    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)
    #14
    Quote Originally Posted by evinda View Post
    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?

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

MHB Model User Award (2014)
    #15 Thread Author
    Quote Originally Posted by I like Serena View Post
    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. 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,357
    Thanks
    4,304 times
    Thanked
    11,953 times
    Thank/Post
    1.880
    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)
    #16
    Quote Originally Posted by evinda View Post
    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?

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

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

    Quote Originally Posted by I like Serena View Post
    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. 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,357
    Thanks
    4,304 times
    Thanked
    11,953 times
    Thank/Post
    1.880
    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)
    #18
    Quote Originally Posted by evinda View Post
    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?

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

MHB Model User Award (2014)
    #19 Thread Author
    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. 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,357
    Thanks
    4,304 times
    Thanked
    11,953 times
    Thank/Post
    1.880
    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)
    #20
    Erm... this is bit much...
    Starting somewhere, what happened to $b_1$ and $b_{\phi(m)}$?

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