Cycle structure of the permutation $x mapsto p·xoperatorname{mod}q$ for coprime $p,q$












1












$begingroup$


Let $[q] = {0,dots,q-1}$, $p < q$.



Consider the function $mathbf{p}: [q] rightarrow [q]$ which sends $x mapsto p·xoperatorname{mod}q$, i.e. the multiplication by $p$ modulo $q$ on $[q]$.



One finds that when $p$ and $q$ are coprime, $mathbf{p}$ is a permutation of $[q]$ with $mathbf{p}(0) = 0$.



Each such permutation – depending solely on $p$ and $q$ – has a specific cycle spectrum: $n_m$ cycles of length $m$.




How do I calculate the possible cycle lengths $m$ and their
corresponding numbers $n_m$ just by looking at $p$ and $q$?











share|cite|improve this question











$endgroup$

















    1












    $begingroup$


    Let $[q] = {0,dots,q-1}$, $p < q$.



    Consider the function $mathbf{p}: [q] rightarrow [q]$ which sends $x mapsto p·xoperatorname{mod}q$, i.e. the multiplication by $p$ modulo $q$ on $[q]$.



    One finds that when $p$ and $q$ are coprime, $mathbf{p}$ is a permutation of $[q]$ with $mathbf{p}(0) = 0$.



    Each such permutation – depending solely on $p$ and $q$ – has a specific cycle spectrum: $n_m$ cycles of length $m$.




    How do I calculate the possible cycle lengths $m$ and their
    corresponding numbers $n_m$ just by looking at $p$ and $q$?











    share|cite|improve this question











    $endgroup$















      1












      1








      1


      0



      $begingroup$


      Let $[q] = {0,dots,q-1}$, $p < q$.



      Consider the function $mathbf{p}: [q] rightarrow [q]$ which sends $x mapsto p·xoperatorname{mod}q$, i.e. the multiplication by $p$ modulo $q$ on $[q]$.



      One finds that when $p$ and $q$ are coprime, $mathbf{p}$ is a permutation of $[q]$ with $mathbf{p}(0) = 0$.



      Each such permutation – depending solely on $p$ and $q$ – has a specific cycle spectrum: $n_m$ cycles of length $m$.




      How do I calculate the possible cycle lengths $m$ and their
      corresponding numbers $n_m$ just by looking at $p$ and $q$?











      share|cite|improve this question











      $endgroup$




      Let $[q] = {0,dots,q-1}$, $p < q$.



      Consider the function $mathbf{p}: [q] rightarrow [q]$ which sends $x mapsto p·xoperatorname{mod}q$, i.e. the multiplication by $p$ modulo $q$ on $[q]$.



      One finds that when $p$ and $q$ are coprime, $mathbf{p}$ is a permutation of $[q]$ with $mathbf{p}(0) = 0$.



      Each such permutation – depending solely on $p$ and $q$ – has a specific cycle spectrum: $n_m$ cycles of length $m$.




      How do I calculate the possible cycle lengths $m$ and their
      corresponding numbers $n_m$ just by looking at $p$ and $q$?








      number-theory permutations coprime permutation-cycles






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Dec 7 '18 at 11:33







      Hans Stricker

















      asked Dec 5 '18 at 17:54









      Hans StrickerHans Stricker

      6,19843988




      6,19843988






















          2 Answers
          2






          active

          oldest

          votes


















          1












          $begingroup$

          Let $H_q = { p^n bmod q,n ge 0}$, it contains $|H_q| = $ "the order of $pbmod q$" elements.




          • Assume $gcd(a,q)=1$ then $a in (mathbb{Z}/qmathbb{Z})^times$ so $|aH_q| = |H_q|$


          • Otherwise let $g = gcd(a,q)$. Then $frac{a}{g} in (mathbb{Z}/qmathbb{Z})^times$ and $|a H_q|= |g frac{a}{g} H_q|=|g H_q| = |g H_{frac{q}{g}}| = |H_{frac{q}{g}}|$


          • Thus for each $d = frac{q}{g} | q$ there are $frac{varphi(d)}{|H_{d}|}$ cycles of length $|H_{d}| = $ the order of $p bmod d$


          • To know the order of each $p bmod d$, you can factorize $q = prod_j p_j^{e_j}$ and compute the order of $p bmod p_j^m,m le e_j$, then $|H_{prod_j p_j^{m_j}}|$ is the $lcm$ of the $|H_{p_j^{m_j}}|$







          share|cite|improve this answer











          $endgroup$













          • $begingroup$
            Would you mind to help me to align your answer with the special case 49:243 as depicted in my question? (It's not too obvious how to start off.)
            $endgroup$
            – Hans Stricker
            Dec 6 '18 at 17:04










          • $begingroup$
            wolframalpha.com/input/… and $varphi(3^n) = 2.3^{n-1}$ @HansStricker
            $endgroup$
            – reuns
            Dec 6 '18 at 17:08












          • $begingroup$
            This looks promising, but (i) What does $2.3^{n-1}$ mean? Should it be $2cdot 3^{n-1}$? and (ii) I'm looking for an expression with a variable which I can set to $243$. (Actually I see only a variable which I can set to $49$. And $243$ comes only in the result.)
            $endgroup$
            – Hans Stricker
            Dec 6 '18 at 17:24












          • $begingroup$
            $3^n$ are the divisors of $243$ and $varphi$ is the Euler totient. Do you understand how multiplication by 49 acts on the group of integers coprime with $243$ ? @HansStricker
            $endgroup$
            – reuns
            Dec 6 '18 at 17:28










          • $begingroup$
            I know the symbol and meaning of the Euler totient. And now I see: $3^1 = 3$, $3^2=9$, $3^3 = 27$, $3^4 = 81$, $3^5 = 243$ are exactly the divisors of $243$. That's interesting enough, I was not aware of.
            $endgroup$
            – Hans Stricker
            Dec 6 '18 at 17:31





















          1












          $begingroup$

          Having digested and finally understood user reuns' answer, let me share some visual examples:



          enter image description here



          enter image description here



          enter image description here






          share|cite|improve this answer









          $endgroup$













            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "69"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: true,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            noCode: true, onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3027415%2fcycle-structure-of-the-permutation-x-mapsto-p-x-operatornamemodq-for-coprim%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            2 Answers
            2






            active

            oldest

            votes








            2 Answers
            2






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            1












            $begingroup$

            Let $H_q = { p^n bmod q,n ge 0}$, it contains $|H_q| = $ "the order of $pbmod q$" elements.




            • Assume $gcd(a,q)=1$ then $a in (mathbb{Z}/qmathbb{Z})^times$ so $|aH_q| = |H_q|$


            • Otherwise let $g = gcd(a,q)$. Then $frac{a}{g} in (mathbb{Z}/qmathbb{Z})^times$ and $|a H_q|= |g frac{a}{g} H_q|=|g H_q| = |g H_{frac{q}{g}}| = |H_{frac{q}{g}}|$


            • Thus for each $d = frac{q}{g} | q$ there are $frac{varphi(d)}{|H_{d}|}$ cycles of length $|H_{d}| = $ the order of $p bmod d$


            • To know the order of each $p bmod d$, you can factorize $q = prod_j p_j^{e_j}$ and compute the order of $p bmod p_j^m,m le e_j$, then $|H_{prod_j p_j^{m_j}}|$ is the $lcm$ of the $|H_{p_j^{m_j}}|$







            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              Would you mind to help me to align your answer with the special case 49:243 as depicted in my question? (It's not too obvious how to start off.)
              $endgroup$
              – Hans Stricker
              Dec 6 '18 at 17:04










            • $begingroup$
              wolframalpha.com/input/… and $varphi(3^n) = 2.3^{n-1}$ @HansStricker
              $endgroup$
              – reuns
              Dec 6 '18 at 17:08












            • $begingroup$
              This looks promising, but (i) What does $2.3^{n-1}$ mean? Should it be $2cdot 3^{n-1}$? and (ii) I'm looking for an expression with a variable which I can set to $243$. (Actually I see only a variable which I can set to $49$. And $243$ comes only in the result.)
              $endgroup$
              – Hans Stricker
              Dec 6 '18 at 17:24












            • $begingroup$
              $3^n$ are the divisors of $243$ and $varphi$ is the Euler totient. Do you understand how multiplication by 49 acts on the group of integers coprime with $243$ ? @HansStricker
              $endgroup$
              – reuns
              Dec 6 '18 at 17:28










            • $begingroup$
              I know the symbol and meaning of the Euler totient. And now I see: $3^1 = 3$, $3^2=9$, $3^3 = 27$, $3^4 = 81$, $3^5 = 243$ are exactly the divisors of $243$. That's interesting enough, I was not aware of.
              $endgroup$
              – Hans Stricker
              Dec 6 '18 at 17:31


















            1












            $begingroup$

            Let $H_q = { p^n bmod q,n ge 0}$, it contains $|H_q| = $ "the order of $pbmod q$" elements.




            • Assume $gcd(a,q)=1$ then $a in (mathbb{Z}/qmathbb{Z})^times$ so $|aH_q| = |H_q|$


            • Otherwise let $g = gcd(a,q)$. Then $frac{a}{g} in (mathbb{Z}/qmathbb{Z})^times$ and $|a H_q|= |g frac{a}{g} H_q|=|g H_q| = |g H_{frac{q}{g}}| = |H_{frac{q}{g}}|$


            • Thus for each $d = frac{q}{g} | q$ there are $frac{varphi(d)}{|H_{d}|}$ cycles of length $|H_{d}| = $ the order of $p bmod d$


            • To know the order of each $p bmod d$, you can factorize $q = prod_j p_j^{e_j}$ and compute the order of $p bmod p_j^m,m le e_j$, then $|H_{prod_j p_j^{m_j}}|$ is the $lcm$ of the $|H_{p_j^{m_j}}|$







            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              Would you mind to help me to align your answer with the special case 49:243 as depicted in my question? (It's not too obvious how to start off.)
              $endgroup$
              – Hans Stricker
              Dec 6 '18 at 17:04










            • $begingroup$
              wolframalpha.com/input/… and $varphi(3^n) = 2.3^{n-1}$ @HansStricker
              $endgroup$
              – reuns
              Dec 6 '18 at 17:08












            • $begingroup$
              This looks promising, but (i) What does $2.3^{n-1}$ mean? Should it be $2cdot 3^{n-1}$? and (ii) I'm looking for an expression with a variable which I can set to $243$. (Actually I see only a variable which I can set to $49$. And $243$ comes only in the result.)
              $endgroup$
              – Hans Stricker
              Dec 6 '18 at 17:24












            • $begingroup$
              $3^n$ are the divisors of $243$ and $varphi$ is the Euler totient. Do you understand how multiplication by 49 acts on the group of integers coprime with $243$ ? @HansStricker
              $endgroup$
              – reuns
              Dec 6 '18 at 17:28










            • $begingroup$
              I know the symbol and meaning of the Euler totient. And now I see: $3^1 = 3$, $3^2=9$, $3^3 = 27$, $3^4 = 81$, $3^5 = 243$ are exactly the divisors of $243$. That's interesting enough, I was not aware of.
              $endgroup$
              – Hans Stricker
              Dec 6 '18 at 17:31
















            1












            1








            1





            $begingroup$

            Let $H_q = { p^n bmod q,n ge 0}$, it contains $|H_q| = $ "the order of $pbmod q$" elements.




            • Assume $gcd(a,q)=1$ then $a in (mathbb{Z}/qmathbb{Z})^times$ so $|aH_q| = |H_q|$


            • Otherwise let $g = gcd(a,q)$. Then $frac{a}{g} in (mathbb{Z}/qmathbb{Z})^times$ and $|a H_q|= |g frac{a}{g} H_q|=|g H_q| = |g H_{frac{q}{g}}| = |H_{frac{q}{g}}|$


            • Thus for each $d = frac{q}{g} | q$ there are $frac{varphi(d)}{|H_{d}|}$ cycles of length $|H_{d}| = $ the order of $p bmod d$


            • To know the order of each $p bmod d$, you can factorize $q = prod_j p_j^{e_j}$ and compute the order of $p bmod p_j^m,m le e_j$, then $|H_{prod_j p_j^{m_j}}|$ is the $lcm$ of the $|H_{p_j^{m_j}}|$







            share|cite|improve this answer











            $endgroup$



            Let $H_q = { p^n bmod q,n ge 0}$, it contains $|H_q| = $ "the order of $pbmod q$" elements.




            • Assume $gcd(a,q)=1$ then $a in (mathbb{Z}/qmathbb{Z})^times$ so $|aH_q| = |H_q|$


            • Otherwise let $g = gcd(a,q)$. Then $frac{a}{g} in (mathbb{Z}/qmathbb{Z})^times$ and $|a H_q|= |g frac{a}{g} H_q|=|g H_q| = |g H_{frac{q}{g}}| = |H_{frac{q}{g}}|$


            • Thus for each $d = frac{q}{g} | q$ there are $frac{varphi(d)}{|H_{d}|}$ cycles of length $|H_{d}| = $ the order of $p bmod d$


            • To know the order of each $p bmod d$, you can factorize $q = prod_j p_j^{e_j}$ and compute the order of $p bmod p_j^m,m le e_j$, then $|H_{prod_j p_j^{m_j}}|$ is the $lcm$ of the $|H_{p_j^{m_j}}|$








            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Dec 5 '18 at 20:39

























            answered Dec 5 '18 at 20:08









            reunsreuns

            20k21148




            20k21148












            • $begingroup$
              Would you mind to help me to align your answer with the special case 49:243 as depicted in my question? (It's not too obvious how to start off.)
              $endgroup$
              – Hans Stricker
              Dec 6 '18 at 17:04










            • $begingroup$
              wolframalpha.com/input/… and $varphi(3^n) = 2.3^{n-1}$ @HansStricker
              $endgroup$
              – reuns
              Dec 6 '18 at 17:08












            • $begingroup$
              This looks promising, but (i) What does $2.3^{n-1}$ mean? Should it be $2cdot 3^{n-1}$? and (ii) I'm looking for an expression with a variable which I can set to $243$. (Actually I see only a variable which I can set to $49$. And $243$ comes only in the result.)
              $endgroup$
              – Hans Stricker
              Dec 6 '18 at 17:24












            • $begingroup$
              $3^n$ are the divisors of $243$ and $varphi$ is the Euler totient. Do you understand how multiplication by 49 acts on the group of integers coprime with $243$ ? @HansStricker
              $endgroup$
              – reuns
              Dec 6 '18 at 17:28










            • $begingroup$
              I know the symbol and meaning of the Euler totient. And now I see: $3^1 = 3$, $3^2=9$, $3^3 = 27$, $3^4 = 81$, $3^5 = 243$ are exactly the divisors of $243$. That's interesting enough, I was not aware of.
              $endgroup$
              – Hans Stricker
              Dec 6 '18 at 17:31




















            • $begingroup$
              Would you mind to help me to align your answer with the special case 49:243 as depicted in my question? (It's not too obvious how to start off.)
              $endgroup$
              – Hans Stricker
              Dec 6 '18 at 17:04










            • $begingroup$
              wolframalpha.com/input/… and $varphi(3^n) = 2.3^{n-1}$ @HansStricker
              $endgroup$
              – reuns
              Dec 6 '18 at 17:08












            • $begingroup$
              This looks promising, but (i) What does $2.3^{n-1}$ mean? Should it be $2cdot 3^{n-1}$? and (ii) I'm looking for an expression with a variable which I can set to $243$. (Actually I see only a variable which I can set to $49$. And $243$ comes only in the result.)
              $endgroup$
              – Hans Stricker
              Dec 6 '18 at 17:24












            • $begingroup$
              $3^n$ are the divisors of $243$ and $varphi$ is the Euler totient. Do you understand how multiplication by 49 acts on the group of integers coprime with $243$ ? @HansStricker
              $endgroup$
              – reuns
              Dec 6 '18 at 17:28










            • $begingroup$
              I know the symbol and meaning of the Euler totient. And now I see: $3^1 = 3$, $3^2=9$, $3^3 = 27$, $3^4 = 81$, $3^5 = 243$ are exactly the divisors of $243$. That's interesting enough, I was not aware of.
              $endgroup$
              – Hans Stricker
              Dec 6 '18 at 17:31


















            $begingroup$
            Would you mind to help me to align your answer with the special case 49:243 as depicted in my question? (It's not too obvious how to start off.)
            $endgroup$
            – Hans Stricker
            Dec 6 '18 at 17:04




            $begingroup$
            Would you mind to help me to align your answer with the special case 49:243 as depicted in my question? (It's not too obvious how to start off.)
            $endgroup$
            – Hans Stricker
            Dec 6 '18 at 17:04












            $begingroup$
            wolframalpha.com/input/… and $varphi(3^n) = 2.3^{n-1}$ @HansStricker
            $endgroup$
            – reuns
            Dec 6 '18 at 17:08






            $begingroup$
            wolframalpha.com/input/… and $varphi(3^n) = 2.3^{n-1}$ @HansStricker
            $endgroup$
            – reuns
            Dec 6 '18 at 17:08














            $begingroup$
            This looks promising, but (i) What does $2.3^{n-1}$ mean? Should it be $2cdot 3^{n-1}$? and (ii) I'm looking for an expression with a variable which I can set to $243$. (Actually I see only a variable which I can set to $49$. And $243$ comes only in the result.)
            $endgroup$
            – Hans Stricker
            Dec 6 '18 at 17:24






            $begingroup$
            This looks promising, but (i) What does $2.3^{n-1}$ mean? Should it be $2cdot 3^{n-1}$? and (ii) I'm looking for an expression with a variable which I can set to $243$. (Actually I see only a variable which I can set to $49$. And $243$ comes only in the result.)
            $endgroup$
            – Hans Stricker
            Dec 6 '18 at 17:24














            $begingroup$
            $3^n$ are the divisors of $243$ and $varphi$ is the Euler totient. Do you understand how multiplication by 49 acts on the group of integers coprime with $243$ ? @HansStricker
            $endgroup$
            – reuns
            Dec 6 '18 at 17:28




            $begingroup$
            $3^n$ are the divisors of $243$ and $varphi$ is the Euler totient. Do you understand how multiplication by 49 acts on the group of integers coprime with $243$ ? @HansStricker
            $endgroup$
            – reuns
            Dec 6 '18 at 17:28












            $begingroup$
            I know the symbol and meaning of the Euler totient. And now I see: $3^1 = 3$, $3^2=9$, $3^3 = 27$, $3^4 = 81$, $3^5 = 243$ are exactly the divisors of $243$. That's interesting enough, I was not aware of.
            $endgroup$
            – Hans Stricker
            Dec 6 '18 at 17:31






            $begingroup$
            I know the symbol and meaning of the Euler totient. And now I see: $3^1 = 3$, $3^2=9$, $3^3 = 27$, $3^4 = 81$, $3^5 = 243$ are exactly the divisors of $243$. That's interesting enough, I was not aware of.
            $endgroup$
            – Hans Stricker
            Dec 6 '18 at 17:31













            1












            $begingroup$

            Having digested and finally understood user reuns' answer, let me share some visual examples:



            enter image description here



            enter image description here



            enter image description here






            share|cite|improve this answer









            $endgroup$


















              1












              $begingroup$

              Having digested and finally understood user reuns' answer, let me share some visual examples:



              enter image description here



              enter image description here



              enter image description here






              share|cite|improve this answer









              $endgroup$
















                1












                1








                1





                $begingroup$

                Having digested and finally understood user reuns' answer, let me share some visual examples:



                enter image description here



                enter image description here



                enter image description here






                share|cite|improve this answer









                $endgroup$



                Having digested and finally understood user reuns' answer, let me share some visual examples:



                enter image description here



                enter image description here



                enter image description here







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered Dec 7 '18 at 11:41









                Hans StrickerHans Stricker

                6,19843988




                6,19843988






























                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Mathematics Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3027415%2fcycle-structure-of-the-permutation-x-mapsto-p-x-operatornamemodq-for-coprim%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    Plaza Victoria

                    Puebla de Zaragoza

                    Change location of user folders through cmd or PowerShell?