How to prove periodicity Modulo b












0












$begingroup$


We have the sequence



$$
x_n=a^n mod{b},
$$
where $a$ and $b$ are positive integers. How to show that it's periodic? It is intuitively clear but I have no clue how to prove it rigorously from first principles...



Thanks in advance






elementary-number-theory discrete-mathematics ring-theory discrete-calculus







share|cite|improve this question









$endgroup$

















    0












    $begingroup$


    We have the sequence



    $$
    x_n=a^n mod{b},
    $$
    where $a$ and $b$ are positive integers. How to show that it's periodic? It is intuitively clear but I have no clue how to prove it rigorously from first principles...



    Thanks in advance






    elementary-number-theory discrete-mathematics ring-theory discrete-calculus







    share|cite|improve this question









    $endgroup$















      0












      0








      0





      $begingroup$


      We have the sequence



      $$
      x_n=a^n mod{b},
      $$
      where $a$ and $b$ are positive integers. How to show that it's periodic? It is intuitively clear but I have no clue how to prove it rigorously from first principles...



      Thanks in advance






      elementary-number-theory discrete-mathematics ring-theory discrete-calculus







      share|cite|improve this question









      $endgroup$




      We have the sequence



      $$
      x_n=a^n mod{b},
      $$
      where $a$ and $b$ are positive integers. How to show that it's periodic? It is intuitively clear but I have no clue how to prove it rigorously from first principles...



      Thanks in advance






      elementary-number-theory discrete-mathematics ring-theory discrete-calculus




      elementary-number-theory discrete-mathematics ring-theory discrete-calculus






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Dec 19 '18 at 8:54









      plus1plus1

      3911




      3911






















          2 Answers
          2






          active

          oldest

          votes


















          0












          $begingroup$

          Note first that periodic here means there are $K$, $P > 0$ such that $a^{i} = a^{i+P}$ for $i > K$.



          One begins with showing that there are $m > n$ such that $a^{m} = a^{n}$. Then for all $i > n$ we have
          $$
          a^{i} = a^{i - n + n} = a^{i - n} a^{n} = a^{i - n} a^{m} =
          a^{i + (m - n)}.
          $$
          So you can take $K = n$ and $P = m - n$.






          share|cite|improve this answer









          $endgroup$





















            -1












            $begingroup$

            Using the fact that
            begin{align}
            a^{varphi(b)}equiv 1 mod b
            end{align}
            and the fact that for any $n$
            begin{align}
            n = varphi(b)k+r
            end{align}
            for some $0leq r<varphi(b)$ we have the desired result. Here $varphi(b)$ is the Euler Totient function.






            share|cite|improve this answer









            $endgroup$









            • 1




              $begingroup$
              @plus1 Even simpler, note that $a^n mod b$ can only take a finite range of values i.e. ${0,1,2,dots,b-1}$ so eventually we have$a^n=a^m mod b$ and so $a^{n-m}=1 mod b$ and the sequence is periodic with a period that is a factor of $n-m$.
              $endgroup$
              – gandalf61
              Dec 19 '18 at 9:33












            • $begingroup$
              Thanks! But isn't there a simpler proof? I am not familiar with the Euler Totient function and it's properties..
              $endgroup$
              – plus1
              Dec 19 '18 at 9:33










            • $begingroup$
              @gandalf61 That only shows that $a^n=a^m mod{b}$ for some m>n. Can you deduce from that that $a^{n+1}=a^{m+1} mod{b}$ and get some kind of induction going ?
              $endgroup$
              – plus1
              Dec 19 '18 at 9:38






            • 1




              $begingroup$
              @gandalf61, take $a = 2$ and $b = 6$. How do you go from $a^{3} equiv a^{1} pmod{b}$ to $a^{4} equiv 1 pmod{b}$?
              $endgroup$
              – Andreas Caranti
              Dec 19 '18 at 9:47






            • 1




              $begingroup$
              @AndreasCaranti yes, I was too hasty. If $a$ does not have an inverse $mod b$ then all we can conclude from the simpler argument is that the sequence is eventually periodic i.e. $a^n=a^m, a^{n+1}=a^{m+1}, a^{n+2}=a^{m+2} dots$
              $endgroup$
              – gandalf61
              Dec 19 '18 at 9:56













            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%2f3046182%2fhow-to-prove-periodicity-modulo-b%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









            0












            $begingroup$

            Note first that periodic here means there are $K$, $P > 0$ such that $a^{i} = a^{i+P}$ for $i > K$.



            One begins with showing that there are $m > n$ such that $a^{m} = a^{n}$. Then for all $i > n$ we have
            $$
            a^{i} = a^{i - n + n} = a^{i - n} a^{n} = a^{i - n} a^{m} =
            a^{i + (m - n)}.
            $$
            So you can take $K = n$ and $P = m - n$.






            share|cite|improve this answer









            $endgroup$


















              0












              $begingroup$

              Note first that periodic here means there are $K$, $P > 0$ such that $a^{i} = a^{i+P}$ for $i > K$.



              One begins with showing that there are $m > n$ such that $a^{m} = a^{n}$. Then for all $i > n$ we have
              $$
              a^{i} = a^{i - n + n} = a^{i - n} a^{n} = a^{i - n} a^{m} =
              a^{i + (m - n)}.
              $$
              So you can take $K = n$ and $P = m - n$.






              share|cite|improve this answer









              $endgroup$
















                0












                0








                0





                $begingroup$

                Note first that periodic here means there are $K$, $P > 0$ such that $a^{i} = a^{i+P}$ for $i > K$.



                One begins with showing that there are $m > n$ such that $a^{m} = a^{n}$. Then for all $i > n$ we have
                $$
                a^{i} = a^{i - n + n} = a^{i - n} a^{n} = a^{i - n} a^{m} =
                a^{i + (m - n)}.
                $$
                So you can take $K = n$ and $P = m - n$.






                share|cite|improve this answer









                $endgroup$



                Note first that periodic here means there are $K$, $P > 0$ such that $a^{i} = a^{i+P}$ for $i > K$.



                One begins with showing that there are $m > n$ such that $a^{m} = a^{n}$. Then for all $i > n$ we have
                $$
                a^{i} = a^{i - n + n} = a^{i - n} a^{n} = a^{i - n} a^{m} =
                a^{i + (m - n)}.
                $$
                So you can take $K = n$ and $P = m - n$.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered Dec 19 '18 at 9:59









                Andreas CarantiAndreas Caranti

                56.6k34395




                56.6k34395























                    -1












                    $begingroup$

                    Using the fact that
                    begin{align}
                    a^{varphi(b)}equiv 1 mod b
                    end{align}
                    and the fact that for any $n$
                    begin{align}
                    n = varphi(b)k+r
                    end{align}
                    for some $0leq r<varphi(b)$ we have the desired result. Here $varphi(b)$ is the Euler Totient function.






                    share|cite|improve this answer









                    $endgroup$









                    • 1




                      $begingroup$
                      @plus1 Even simpler, note that $a^n mod b$ can only take a finite range of values i.e. ${0,1,2,dots,b-1}$ so eventually we have$a^n=a^m mod b$ and so $a^{n-m}=1 mod b$ and the sequence is periodic with a period that is a factor of $n-m$.
                      $endgroup$
                      – gandalf61
                      Dec 19 '18 at 9:33












                    • $begingroup$
                      Thanks! But isn't there a simpler proof? I am not familiar with the Euler Totient function and it's properties..
                      $endgroup$
                      – plus1
                      Dec 19 '18 at 9:33










                    • $begingroup$
                      @gandalf61 That only shows that $a^n=a^m mod{b}$ for some m>n. Can you deduce from that that $a^{n+1}=a^{m+1} mod{b}$ and get some kind of induction going ?
                      $endgroup$
                      – plus1
                      Dec 19 '18 at 9:38






                    • 1




                      $begingroup$
                      @gandalf61, take $a = 2$ and $b = 6$. How do you go from $a^{3} equiv a^{1} pmod{b}$ to $a^{4} equiv 1 pmod{b}$?
                      $endgroup$
                      – Andreas Caranti
                      Dec 19 '18 at 9:47






                    • 1




                      $begingroup$
                      @AndreasCaranti yes, I was too hasty. If $a$ does not have an inverse $mod b$ then all we can conclude from the simpler argument is that the sequence is eventually periodic i.e. $a^n=a^m, a^{n+1}=a^{m+1}, a^{n+2}=a^{m+2} dots$
                      $endgroup$
                      – gandalf61
                      Dec 19 '18 at 9:56


















                    -1












                    $begingroup$

                    Using the fact that
                    begin{align}
                    a^{varphi(b)}equiv 1 mod b
                    end{align}
                    and the fact that for any $n$
                    begin{align}
                    n = varphi(b)k+r
                    end{align}
                    for some $0leq r<varphi(b)$ we have the desired result. Here $varphi(b)$ is the Euler Totient function.






                    share|cite|improve this answer









                    $endgroup$









                    • 1




                      $begingroup$
                      @plus1 Even simpler, note that $a^n mod b$ can only take a finite range of values i.e. ${0,1,2,dots,b-1}$ so eventually we have$a^n=a^m mod b$ and so $a^{n-m}=1 mod b$ and the sequence is periodic with a period that is a factor of $n-m$.
                      $endgroup$
                      – gandalf61
                      Dec 19 '18 at 9:33












                    • $begingroup$
                      Thanks! But isn't there a simpler proof? I am not familiar with the Euler Totient function and it's properties..
                      $endgroup$
                      – plus1
                      Dec 19 '18 at 9:33










                    • $begingroup$
                      @gandalf61 That only shows that $a^n=a^m mod{b}$ for some m>n. Can you deduce from that that $a^{n+1}=a^{m+1} mod{b}$ and get some kind of induction going ?
                      $endgroup$
                      – plus1
                      Dec 19 '18 at 9:38






                    • 1




                      $begingroup$
                      @gandalf61, take $a = 2$ and $b = 6$. How do you go from $a^{3} equiv a^{1} pmod{b}$ to $a^{4} equiv 1 pmod{b}$?
                      $endgroup$
                      – Andreas Caranti
                      Dec 19 '18 at 9:47






                    • 1




                      $begingroup$
                      @AndreasCaranti yes, I was too hasty. If $a$ does not have an inverse $mod b$ then all we can conclude from the simpler argument is that the sequence is eventually periodic i.e. $a^n=a^m, a^{n+1}=a^{m+1}, a^{n+2}=a^{m+2} dots$
                      $endgroup$
                      – gandalf61
                      Dec 19 '18 at 9:56
















                    -1












                    -1








                    -1





                    $begingroup$

                    Using the fact that
                    begin{align}
                    a^{varphi(b)}equiv 1 mod b
                    end{align}
                    and the fact that for any $n$
                    begin{align}
                    n = varphi(b)k+r
                    end{align}
                    for some $0leq r<varphi(b)$ we have the desired result. Here $varphi(b)$ is the Euler Totient function.






                    share|cite|improve this answer









                    $endgroup$



                    Using the fact that
                    begin{align}
                    a^{varphi(b)}equiv 1 mod b
                    end{align}
                    and the fact that for any $n$
                    begin{align}
                    n = varphi(b)k+r
                    end{align}
                    for some $0leq r<varphi(b)$ we have the desired result. Here $varphi(b)$ is the Euler Totient function.







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered Dec 19 '18 at 9:03









                    Jacky ChongJacky Chong

                    19k21129




                    19k21129








                    • 1




                      $begingroup$
                      @plus1 Even simpler, note that $a^n mod b$ can only take a finite range of values i.e. ${0,1,2,dots,b-1}$ so eventually we have$a^n=a^m mod b$ and so $a^{n-m}=1 mod b$ and the sequence is periodic with a period that is a factor of $n-m$.
                      $endgroup$
                      – gandalf61
                      Dec 19 '18 at 9:33












                    • $begingroup$
                      Thanks! But isn't there a simpler proof? I am not familiar with the Euler Totient function and it's properties..
                      $endgroup$
                      – plus1
                      Dec 19 '18 at 9:33










                    • $begingroup$
                      @gandalf61 That only shows that $a^n=a^m mod{b}$ for some m>n. Can you deduce from that that $a^{n+1}=a^{m+1} mod{b}$ and get some kind of induction going ?
                      $endgroup$
                      – plus1
                      Dec 19 '18 at 9:38






                    • 1




                      $begingroup$
                      @gandalf61, take $a = 2$ and $b = 6$. How do you go from $a^{3} equiv a^{1} pmod{b}$ to $a^{4} equiv 1 pmod{b}$?
                      $endgroup$
                      – Andreas Caranti
                      Dec 19 '18 at 9:47






                    • 1




                      $begingroup$
                      @AndreasCaranti yes, I was too hasty. If $a$ does not have an inverse $mod b$ then all we can conclude from the simpler argument is that the sequence is eventually periodic i.e. $a^n=a^m, a^{n+1}=a^{m+1}, a^{n+2}=a^{m+2} dots$
                      $endgroup$
                      – gandalf61
                      Dec 19 '18 at 9:56
















                    • 1




                      $begingroup$
                      @plus1 Even simpler, note that $a^n mod b$ can only take a finite range of values i.e. ${0,1,2,dots,b-1}$ so eventually we have$a^n=a^m mod b$ and so $a^{n-m}=1 mod b$ and the sequence is periodic with a period that is a factor of $n-m$.
                      $endgroup$
                      – gandalf61
                      Dec 19 '18 at 9:33












                    • $begingroup$
                      Thanks! But isn't there a simpler proof? I am not familiar with the Euler Totient function and it's properties..
                      $endgroup$
                      – plus1
                      Dec 19 '18 at 9:33










                    • $begingroup$
                      @gandalf61 That only shows that $a^n=a^m mod{b}$ for some m>n. Can you deduce from that that $a^{n+1}=a^{m+1} mod{b}$ and get some kind of induction going ?
                      $endgroup$
                      – plus1
                      Dec 19 '18 at 9:38






                    • 1




                      $begingroup$
                      @gandalf61, take $a = 2$ and $b = 6$. How do you go from $a^{3} equiv a^{1} pmod{b}$ to $a^{4} equiv 1 pmod{b}$?
                      $endgroup$
                      – Andreas Caranti
                      Dec 19 '18 at 9:47






                    • 1




                      $begingroup$
                      @AndreasCaranti yes, I was too hasty. If $a$ does not have an inverse $mod b$ then all we can conclude from the simpler argument is that the sequence is eventually periodic i.e. $a^n=a^m, a^{n+1}=a^{m+1}, a^{n+2}=a^{m+2} dots$
                      $endgroup$
                      – gandalf61
                      Dec 19 '18 at 9:56










                    1




                    1




                    $begingroup$
                    @plus1 Even simpler, note that $a^n mod b$ can only take a finite range of values i.e. ${0,1,2,dots,b-1}$ so eventually we have$a^n=a^m mod b$ and so $a^{n-m}=1 mod b$ and the sequence is periodic with a period that is a factor of $n-m$.
                    $endgroup$
                    – gandalf61
                    Dec 19 '18 at 9:33






                    $begingroup$
                    @plus1 Even simpler, note that $a^n mod b$ can only take a finite range of values i.e. ${0,1,2,dots,b-1}$ so eventually we have$a^n=a^m mod b$ and so $a^{n-m}=1 mod b$ and the sequence is periodic with a period that is a factor of $n-m$.
                    $endgroup$
                    – gandalf61
                    Dec 19 '18 at 9:33














                    $begingroup$
                    Thanks! But isn't there a simpler proof? I am not familiar with the Euler Totient function and it's properties..
                    $endgroup$
                    – plus1
                    Dec 19 '18 at 9:33




                    $begingroup$
                    Thanks! But isn't there a simpler proof? I am not familiar with the Euler Totient function and it's properties..
                    $endgroup$
                    – plus1
                    Dec 19 '18 at 9:33












                    $begingroup$
                    @gandalf61 That only shows that $a^n=a^m mod{b}$ for some m>n. Can you deduce from that that $a^{n+1}=a^{m+1} mod{b}$ and get some kind of induction going ?
                    $endgroup$
                    – plus1
                    Dec 19 '18 at 9:38




                    $begingroup$
                    @gandalf61 That only shows that $a^n=a^m mod{b}$ for some m>n. Can you deduce from that that $a^{n+1}=a^{m+1} mod{b}$ and get some kind of induction going ?
                    $endgroup$
                    – plus1
                    Dec 19 '18 at 9:38




                    1




                    1




                    $begingroup$
                    @gandalf61, take $a = 2$ and $b = 6$. How do you go from $a^{3} equiv a^{1} pmod{b}$ to $a^{4} equiv 1 pmod{b}$?
                    $endgroup$
                    – Andreas Caranti
                    Dec 19 '18 at 9:47




                    $begingroup$
                    @gandalf61, take $a = 2$ and $b = 6$. How do you go from $a^{3} equiv a^{1} pmod{b}$ to $a^{4} equiv 1 pmod{b}$?
                    $endgroup$
                    – Andreas Caranti
                    Dec 19 '18 at 9:47




                    1




                    1




                    $begingroup$
                    @AndreasCaranti yes, I was too hasty. If $a$ does not have an inverse $mod b$ then all we can conclude from the simpler argument is that the sequence is eventually periodic i.e. $a^n=a^m, a^{n+1}=a^{m+1}, a^{n+2}=a^{m+2} dots$
                    $endgroup$
                    – gandalf61
                    Dec 19 '18 at 9:56






                    $begingroup$
                    @AndreasCaranti yes, I was too hasty. If $a$ does not have an inverse $mod b$ then all we can conclude from the simpler argument is that the sequence is eventually periodic i.e. $a^n=a^m, a^{n+1}=a^{m+1}, a^{n+2}=a^{m+2} dots$
                    $endgroup$
                    – gandalf61
                    Dec 19 '18 at 9:56




















                    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%2f3046182%2fhow-to-prove-periodicity-modulo-b%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

                    Index of /

                    This page is only for reference, If you need detailed information, please check here
                    Read more

                    Tribalistas

                    Image
                      Nota: Para o álbum homônimo, veja Tribalistas (álbum de 2002). Para o segundo álbum homônimo, veja Tribalistas (álbum de 2017). Para o tipo de organização tribal, veja Tribalismo. Tribalistas Informação geral Origem Salvador e Rio de Janeiro País   Brasil Gênero(s) MPB Pop Samba Período em atividade 2002–2004 2017–atualmente Gravadora(s) EMI Phonomotor Records Universal Music Afiliação(ões) Dadi Pretinho da Serrinha Margareth Menezes Integrantes Arnaldo Antunes Carlinhos Brown Marisa Monte Página oficial www2.uol.com.br/tribalistas/ ...
                    Read more

                    Listed building

                    Image
                    Listed building (literalmente: prédio listado ) é toda estrutura protegida por lei pelo complexo sistema de tombamento do Reino Unido. Um listed building é qualquer estrutura oficialmente designada como tendo especial interesse arquitetônico, histórico ou cultural. É um estatuto amplamente usado, aplicado a centenas de milhares de estruturas. Estruturas tombadas não podem ser alteradas sem permissão especial, e desfrutam de isenções fiscais e outros benefícios. Cada um dos países do Reino Unido trata tombamento de forma diferente: Índice 1 Inglaterra 2 País de Gales 3 Irlanda do Norte 4 Escócia 5 Referências Inglaterra | O Palácio de Buckingham, Londres. As estruturas tombadas são listadas no Statutory List of Buildings of Special Architectural or Historic Interest , e incluem campos, sinais de trânsito, piers e áreas geográficas. A principal legislação pertinente é o Ancient Monuments and Archaeological Areas Act 1979 , [ 1 ] embora legisla...
                    Read more