Every positive power of $5$ appears in the last digits of bigger power of $5$












5












$begingroup$


Problem. Show that for every positive integer $n$, there is an integer $N > n$ such that the number $5^n$ appears as the last few digits $5^N$. For example, if $n = 3$, we have $5^3 = 125$ and $5^5 = 3125$, so $N = 5$ would satisfy.



This is a problem from the worksheet of the class Putnam Seminar at CMU. Please give hints towards the right direction and not the full solutions. Thanks!!






number-theory contest-math







share|cite|improve this question











$endgroup$












  • $begingroup$
    Why is the contest-math tag used? Please edit the question to add that context.
    $endgroup$
    – Shaun
    Dec 24 '18 at 20:48










  • $begingroup$
    @Shaun Well what I'm I suppose to add? It was a problem on the worksheet from my Putnam class. It feel like saying that is just distracting
    $endgroup$
    – BrianH
    Dec 24 '18 at 20:51






  • 1




    $begingroup$
    Well, the fact that it's from your Putnam class. Don't worry about potential distractions. Context is strongly encouraged by many users here and, typically, it can be very helpful for some users for any number of reasons.
    $endgroup$
    – Shaun
    Dec 24 '18 at 20:56
















5












$begingroup$


Problem. Show that for every positive integer $n$, there is an integer $N > n$ such that the number $5^n$ appears as the last few digits $5^N$. For example, if $n = 3$, we have $5^3 = 125$ and $5^5 = 3125$, so $N = 5$ would satisfy.



This is a problem from the worksheet of the class Putnam Seminar at CMU. Please give hints towards the right direction and not the full solutions. Thanks!!






number-theory contest-math







share|cite|improve this question











$endgroup$












  • $begingroup$
    Why is the contest-math tag used? Please edit the question to add that context.
    $endgroup$
    – Shaun
    Dec 24 '18 at 20:48










  • $begingroup$
    @Shaun Well what I'm I suppose to add? It was a problem on the worksheet from my Putnam class. It feel like saying that is just distracting
    $endgroup$
    – BrianH
    Dec 24 '18 at 20:51






  • 1




    $begingroup$
    Well, the fact that it's from your Putnam class. Don't worry about potential distractions. Context is strongly encouraged by many users here and, typically, it can be very helpful for some users for any number of reasons.
    $endgroup$
    – Shaun
    Dec 24 '18 at 20:56














5












5








5


1



$begingroup$


Problem. Show that for every positive integer $n$, there is an integer $N > n$ such that the number $5^n$ appears as the last few digits $5^N$. For example, if $n = 3$, we have $5^3 = 125$ and $5^5 = 3125$, so $N = 5$ would satisfy.



This is a problem from the worksheet of the class Putnam Seminar at CMU. Please give hints towards the right direction and not the full solutions. Thanks!!






number-theory contest-math







share|cite|improve this question











$endgroup$




Problem. Show that for every positive integer $n$, there is an integer $N > n$ such that the number $5^n$ appears as the last few digits $5^N$. For example, if $n = 3$, we have $5^3 = 125$ and $5^5 = 3125$, so $N = 5$ would satisfy.



This is a problem from the worksheet of the class Putnam Seminar at CMU. Please give hints towards the right direction and not the full solutions. Thanks!!






number-theory contest-math




number-theory contest-math






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 24 '18 at 20:57







BrianH

















asked Dec 22 '18 at 4:56









BrianHBrianH

658




658












  • $begingroup$
    Why is the contest-math tag used? Please edit the question to add that context.
    $endgroup$
    – Shaun
    Dec 24 '18 at 20:48










  • $begingroup$
    @Shaun Well what I'm I suppose to add? It was a problem on the worksheet from my Putnam class. It feel like saying that is just distracting
    $endgroup$
    – BrianH
    Dec 24 '18 at 20:51






  • 1




    $begingroup$
    Well, the fact that it's from your Putnam class. Don't worry about potential distractions. Context is strongly encouraged by many users here and, typically, it can be very helpful for some users for any number of reasons.
    $endgroup$
    – Shaun
    Dec 24 '18 at 20:56


















  • $begingroup$
    Why is the contest-math tag used? Please edit the question to add that context.
    $endgroup$
    – Shaun
    Dec 24 '18 at 20:48










  • $begingroup$
    @Shaun Well what I'm I suppose to add? It was a problem on the worksheet from my Putnam class. It feel like saying that is just distracting
    $endgroup$
    – BrianH
    Dec 24 '18 at 20:51






  • 1




    $begingroup$
    Well, the fact that it's from your Putnam class. Don't worry about potential distractions. Context is strongly encouraged by many users here and, typically, it can be very helpful for some users for any number of reasons.
    $endgroup$
    – Shaun
    Dec 24 '18 at 20:56
















$begingroup$
Why is the contest-math tag used? Please edit the question to add that context.
$endgroup$
– Shaun
Dec 24 '18 at 20:48




$begingroup$
Why is the contest-math tag used? Please edit the question to add that context.
$endgroup$
– Shaun
Dec 24 '18 at 20:48












$begingroup$
@Shaun Well what I'm I suppose to add? It was a problem on the worksheet from my Putnam class. It feel like saying that is just distracting
$endgroup$
– BrianH
Dec 24 '18 at 20:51




$begingroup$
@Shaun Well what I'm I suppose to add? It was a problem on the worksheet from my Putnam class. It feel like saying that is just distracting
$endgroup$
– BrianH
Dec 24 '18 at 20:51




1




1




$begingroup$
Well, the fact that it's from your Putnam class. Don't worry about potential distractions. Context is strongly encouraged by many users here and, typically, it can be very helpful for some users for any number of reasons.
$endgroup$
– Shaun
Dec 24 '18 at 20:56




$begingroup$
Well, the fact that it's from your Putnam class. Don't worry about potential distractions. Context is strongly encouraged by many users here and, typically, it can be very helpful for some users for any number of reasons.
$endgroup$
– Shaun
Dec 24 '18 at 20:56










2 Answers
2






active

oldest

votes


















9












$begingroup$

Fix $n$.
The cases $n le 3$ can be handled directly.
We now assume $n > 3$.



Let $m = lceil n log_{10} 5 rceil$ be the smallest integer such that $10^m > 5^n$. For $n > 3$, we have $m < n$.



You want to find $N$ such that $5^N = k 10^m + 5^n$ for some integer $k$. Dividing both sides by $5^n$ yields $$5^{N-n} - 1 = k 2^m/ 5^{n-m}.$$



Thus if you show you can find a large integer $q$ such that $5^q - 1$ is divisible by $2^m$ then you can choose $N$ and $k$ appropriately to conclude the proof.





Base case: For $m=2$ we have $5^1 - 1$ divisible by $2^m$. Inductive step: if $5^q-1$ is divisible by $2^m$, then $5^{2q}-1 = (5^q-1)(5^q+1)$ is divisible by $2^{m+1}$.







share|cite|improve this answer









$endgroup$





















    2












    $begingroup$

    We will prove that there exists a $N$ such that $5^n$ and $5^N$ have the same last $n$ digits



    So what we need to do is to find $5^Nequiv 5^npmod{10^n}$



    This can be achieved by setting $N=n+phi (2^n)$



    Since $5^Nequiv 5^npmod{5^n}$ and $5^Nequiv 5^npmod{2^n}$






    share|cite|improve this answer









    $endgroup$













    • $begingroup$
      Could you explain to me how you reached the last two lines?
      $endgroup$
      – BrianH
      Dec 22 '18 at 5:39











    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%2f3049126%2fevery-positive-power-of-5-appears-in-the-last-digits-of-bigger-power-of-5%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









    9












    $begingroup$

    Fix $n$.
    The cases $n le 3$ can be handled directly.
    We now assume $n > 3$.



    Let $m = lceil n log_{10} 5 rceil$ be the smallest integer such that $10^m > 5^n$. For $n > 3$, we have $m < n$.



    You want to find $N$ such that $5^N = k 10^m + 5^n$ for some integer $k$. Dividing both sides by $5^n$ yields $$5^{N-n} - 1 = k 2^m/ 5^{n-m}.$$



    Thus if you show you can find a large integer $q$ such that $5^q - 1$ is divisible by $2^m$ then you can choose $N$ and $k$ appropriately to conclude the proof.





    Base case: For $m=2$ we have $5^1 - 1$ divisible by $2^m$. Inductive step: if $5^q-1$ is divisible by $2^m$, then $5^{2q}-1 = (5^q-1)(5^q+1)$ is divisible by $2^{m+1}$.







    share|cite|improve this answer









    $endgroup$


















      9












      $begingroup$

      Fix $n$.
      The cases $n le 3$ can be handled directly.
      We now assume $n > 3$.



      Let $m = lceil n log_{10} 5 rceil$ be the smallest integer such that $10^m > 5^n$. For $n > 3$, we have $m < n$.



      You want to find $N$ such that $5^N = k 10^m + 5^n$ for some integer $k$. Dividing both sides by $5^n$ yields $$5^{N-n} - 1 = k 2^m/ 5^{n-m}.$$



      Thus if you show you can find a large integer $q$ such that $5^q - 1$ is divisible by $2^m$ then you can choose $N$ and $k$ appropriately to conclude the proof.





      Base case: For $m=2$ we have $5^1 - 1$ divisible by $2^m$. Inductive step: if $5^q-1$ is divisible by $2^m$, then $5^{2q}-1 = (5^q-1)(5^q+1)$ is divisible by $2^{m+1}$.







      share|cite|improve this answer









      $endgroup$
















        9












        9








        9





        $begingroup$

        Fix $n$.
        The cases $n le 3$ can be handled directly.
        We now assume $n > 3$.



        Let $m = lceil n log_{10} 5 rceil$ be the smallest integer such that $10^m > 5^n$. For $n > 3$, we have $m < n$.



        You want to find $N$ such that $5^N = k 10^m + 5^n$ for some integer $k$. Dividing both sides by $5^n$ yields $$5^{N-n} - 1 = k 2^m/ 5^{n-m}.$$



        Thus if you show you can find a large integer $q$ such that $5^q - 1$ is divisible by $2^m$ then you can choose $N$ and $k$ appropriately to conclude the proof.





        Base case: For $m=2$ we have $5^1 - 1$ divisible by $2^m$. Inductive step: if $5^q-1$ is divisible by $2^m$, then $5^{2q}-1 = (5^q-1)(5^q+1)$ is divisible by $2^{m+1}$.







        share|cite|improve this answer









        $endgroup$



        Fix $n$.
        The cases $n le 3$ can be handled directly.
        We now assume $n > 3$.



        Let $m = lceil n log_{10} 5 rceil$ be the smallest integer such that $10^m > 5^n$. For $n > 3$, we have $m < n$.



        You want to find $N$ such that $5^N = k 10^m + 5^n$ for some integer $k$. Dividing both sides by $5^n$ yields $$5^{N-n} - 1 = k 2^m/ 5^{n-m}.$$



        Thus if you show you can find a large integer $q$ such that $5^q - 1$ is divisible by $2^m$ then you can choose $N$ and $k$ appropriately to conclude the proof.





        Base case: For $m=2$ we have $5^1 - 1$ divisible by $2^m$. Inductive step: if $5^q-1$ is divisible by $2^m$, then $5^{2q}-1 = (5^q-1)(5^q+1)$ is divisible by $2^{m+1}$.








        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Dec 22 '18 at 5:21









        angryavianangryavian

        40.7k23380




        40.7k23380























            2












            $begingroup$

            We will prove that there exists a $N$ such that $5^n$ and $5^N$ have the same last $n$ digits



            So what we need to do is to find $5^Nequiv 5^npmod{10^n}$



            This can be achieved by setting $N=n+phi (2^n)$



            Since $5^Nequiv 5^npmod{5^n}$ and $5^Nequiv 5^npmod{2^n}$






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              Could you explain to me how you reached the last two lines?
              $endgroup$
              – BrianH
              Dec 22 '18 at 5:39
















            2












            $begingroup$

            We will prove that there exists a $N$ such that $5^n$ and $5^N$ have the same last $n$ digits



            So what we need to do is to find $5^Nequiv 5^npmod{10^n}$



            This can be achieved by setting $N=n+phi (2^n)$



            Since $5^Nequiv 5^npmod{5^n}$ and $5^Nequiv 5^npmod{2^n}$






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              Could you explain to me how you reached the last two lines?
              $endgroup$
              – BrianH
              Dec 22 '18 at 5:39














            2












            2








            2





            $begingroup$

            We will prove that there exists a $N$ such that $5^n$ and $5^N$ have the same last $n$ digits



            So what we need to do is to find $5^Nequiv 5^npmod{10^n}$



            This can be achieved by setting $N=n+phi (2^n)$



            Since $5^Nequiv 5^npmod{5^n}$ and $5^Nequiv 5^npmod{2^n}$






            share|cite|improve this answer









            $endgroup$



            We will prove that there exists a $N$ such that $5^n$ and $5^N$ have the same last $n$ digits



            So what we need to do is to find $5^Nequiv 5^npmod{10^n}$



            This can be achieved by setting $N=n+phi (2^n)$



            Since $5^Nequiv 5^npmod{5^n}$ and $5^Nequiv 5^npmod{2^n}$







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered Dec 22 '18 at 5:26









            bangzhengbangzheng

            212




            212












            • $begingroup$
              Could you explain to me how you reached the last two lines?
              $endgroup$
              – BrianH
              Dec 22 '18 at 5:39


















            • $begingroup$
              Could you explain to me how you reached the last two lines?
              $endgroup$
              – BrianH
              Dec 22 '18 at 5:39
















            $begingroup$
            Could you explain to me how you reached the last two lines?
            $endgroup$
            – BrianH
            Dec 22 '18 at 5:39




            $begingroup$
            Could you explain to me how you reached the last two lines?
            $endgroup$
            – BrianH
            Dec 22 '18 at 5:39


















            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%2f3049126%2fevery-positive-power-of-5-appears-in-the-last-digits-of-bigger-power-of-5%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

            Bressuire

            Image
            .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid ...
            Read more

            Cabo Verde

            Image
              Nota: Cabo-verdiano redireciona para este artigo. Para a língua falada em Cabo Verde, veja crioulo cabo-verdiano. Para outros significados, veja Cabo Verde (desambiguação). Coordenadas: 14° 55' N 23° 31' O Cabo Verde República de Cabo Verde Bandeira Brasão de Armas Lema: Unidade, Trabalho, Progresso Hino nacional: Cântico da Liberdade Gentílico: cabo-verdiano [ 1 ] Capital Praia 14° 55' N 23° 31' O Cidade mais populosa Praia Língua oficial Português Governo República unitária semipresidencialista [ 2 ]  - Presidente Jorge Carlos Fonseca  - Primeiro-ministro Ulisses Correia e Silva História    - Descoberta 1460   - Independência 00 • de Portugal 5 de Julho de 1975   - Multipartidarismo 13 de Janeiro de 1990  Área    - Total 4 033 km² (146.º)  - Água (%) 0,08 População    - Estimativa para 2017 560 899 [ 3 ] hab. (173.º) ...
            Read more

            Gyllenstierna

            Image
            .mw-parser-output .infobox{border:1px solid #aaa;background-color:#f9f9f9;color:black;margin:.5em 0 .5em 1em;padding:.2em;float:right;clear:right;width:22em;text-align:left;font-size:88%;line-height:1.6em}.mw-parser-output .infobox td,.mw-parser-output .infobox th{vertical-align:top;padding:0 .2em}.mw-parser-output .infobox caption{font-size:larger}.mw-parser-output .infobox.bordered{border-collapse:collapse}.mw-parser-output .infobox.bordered td,.mw-parser-output .infobox.bordered th{border:1px solid #aaa}.mw-parser-output .infobox.bordered .borderless td,.mw-parser-output .infobox.bordered .borderless th{border:0}.mw-parser-output .infobox-showbutton .mw-collapsible-text{color:inherit}.mw-parser-output .infobox.bordered .mergedtoprow td,.mw-parser-output .infobox.bordered .mergedtoprow th{border:0;border-top:1px solid #aaa;border-right:1px solid #aaa}.mw-parser-output .infobox.bordered .mergedrow td,.mw-parser-output .infobox.bordered .mergedrow th{border:0;border-right:1px solid ...
            Read more