Find last 3 digits of this monster numberWhen can you simplify the modulus? ($10^5^102 text mod 35$)how to find the last non-zero digit of $n$Why is $x^100 = 1 mod 1000$ if $x < 1000$ and $gcd (x,1000) = 1$?Last 3 digits of Marsenne numbersShow that $a^varphi(n)+1equiv a,mod n$.Showing that $a^5$ and $a$ have the same last digit using Euler's Theorem.Find the last ten digits of this exponential tower.Euler theorem, finding last digitsNumber Theory Linear Diophantine EquationsRSA decryption coefficientFinding the last 4 digits of a huge power

anything or something to eat

Can somebody explain Brexit in a few child-proof sentences?

How can "mimic phobia" be cured or prevented?

A Permanent Norse Presence in America

Drawing ramified coverings with tikz

How do I repair my stair bannister?

MAXDOP Settings for SQL Server 2014

Why has "pence" been used in this sentence, not "pences"?

Transformation of random variables and joint distributions

How will losing mobility of one hand affect my career as a programmer?

Have I saved too much for retirement so far?

What's the difference between 違法 and 不法?

Is a model fitted to data or is data fitted to a model?

THT: What is a squared annular “ring”?

Journal losing indexing services

Can I sign legal documents with a smiley face?

Are lightweight LN wallets vulnerable to transaction withholding?

How to align and center standalone amsmath equations?

Some numbers are more equivalent than others

Why did the HMS Bounty go back to a time when whales are already rare?

Is XSS in canonical link possible?

Will adding a BY-SA image to a blog post make the entire post BY-SA?

Could solar power be utilized and substitute coal in the 19th Century

Bob has never been a M before



Find last 3 digits of this monster number


When can you simplify the modulus? ($10^5^102 text mod 35$)how to find the last non-zero digit of $n$Why is $x^100 = 1 mod 1000$ if $x < 1000$ and $gcd (x,1000) = 1$?Last 3 digits of Marsenne numbersShow that $a^varphi(n)+1equiv a,mod n$.Showing that $a^5$ and $a$ have the same last digit using Euler's Theorem.Find the last ten digits of this exponential tower.Euler theorem, finding last digitsNumber Theory Linear Diophantine EquationsRSA decryption coefficientFinding the last 4 digits of a huge power













5












$begingroup$


Find the last 3 digits of this number
$$
2032^2031^2030^dots^2^1
$$

So obviously we are looking for $x$ so that
$$
2032^2031^2030^dots^2^1 equiv x quad textmodhspace0.1cm 1000
$$

I also know that usually you use Euler' theorem here, but that only works when the numbers $a$ and $n$ are coprime, but $2032$ and $1000$ are not coprime? I can easily find $varphi(1000)$, that is not a problem. Am I looking for wrong numbers to be coprime here or is there another way instead of Euler' theorem?










share|cite|improve this question









$endgroup$











  • $begingroup$
    The common factor here is $8$ and you should be able show that he power is divisible by $8$, so the residue modulo $1000$ can be determined by looking at the residue modulo $1000/8=125$
    $endgroup$
    – Mark Bennet
    3 hours ago










  • $begingroup$
    @Mark is correct, and in fact we can factor it out in a slick operational way that avoids using CRT by using the mod Distributive Law, as I show in my answer. This usually ends up being simpler than rotely applying CRT = Chinese Remainder when the base shares a common factor with the modulus.
    $endgroup$
    – Bill Dubuque
    41 mins ago
















5












$begingroup$


Find the last 3 digits of this number
$$
2032^2031^2030^dots^2^1
$$

So obviously we are looking for $x$ so that
$$
2032^2031^2030^dots^2^1 equiv x quad textmodhspace0.1cm 1000
$$

I also know that usually you use Euler' theorem here, but that only works when the numbers $a$ and $n$ are coprime, but $2032$ and $1000$ are not coprime? I can easily find $varphi(1000)$, that is not a problem. Am I looking for wrong numbers to be coprime here or is there another way instead of Euler' theorem?










share|cite|improve this question









$endgroup$











  • $begingroup$
    The common factor here is $8$ and you should be able show that he power is divisible by $8$, so the residue modulo $1000$ can be determined by looking at the residue modulo $1000/8=125$
    $endgroup$
    – Mark Bennet
    3 hours ago










  • $begingroup$
    @Mark is correct, and in fact we can factor it out in a slick operational way that avoids using CRT by using the mod Distributive Law, as I show in my answer. This usually ends up being simpler than rotely applying CRT = Chinese Remainder when the base shares a common factor with the modulus.
    $endgroup$
    – Bill Dubuque
    41 mins ago














5












5








5





$begingroup$


Find the last 3 digits of this number
$$
2032^2031^2030^dots^2^1
$$

So obviously we are looking for $x$ so that
$$
2032^2031^2030^dots^2^1 equiv x quad textmodhspace0.1cm 1000
$$

I also know that usually you use Euler' theorem here, but that only works when the numbers $a$ and $n$ are coprime, but $2032$ and $1000$ are not coprime? I can easily find $varphi(1000)$, that is not a problem. Am I looking for wrong numbers to be coprime here or is there another way instead of Euler' theorem?










share|cite|improve this question









$endgroup$




Find the last 3 digits of this number
$$
2032^2031^2030^dots^2^1
$$

So obviously we are looking for $x$ so that
$$
2032^2031^2030^dots^2^1 equiv x quad textmodhspace0.1cm 1000
$$

I also know that usually you use Euler' theorem here, but that only works when the numbers $a$ and $n$ are coprime, but $2032$ and $1000$ are not coprime? I can easily find $varphi(1000)$, that is not a problem. Am I looking for wrong numbers to be coprime here or is there another way instead of Euler' theorem?







number-theory totient-function






share|cite|improve this question













share|cite|improve this question











share|cite|improve this question




share|cite|improve this question










asked 3 hours ago









Kristin PeterselKristin Petersel

263




263











  • $begingroup$
    The common factor here is $8$ and you should be able show that he power is divisible by $8$, so the residue modulo $1000$ can be determined by looking at the residue modulo $1000/8=125$
    $endgroup$
    – Mark Bennet
    3 hours ago










  • $begingroup$
    @Mark is correct, and in fact we can factor it out in a slick operational way that avoids using CRT by using the mod Distributive Law, as I show in my answer. This usually ends up being simpler than rotely applying CRT = Chinese Remainder when the base shares a common factor with the modulus.
    $endgroup$
    – Bill Dubuque
    41 mins ago

















  • $begingroup$
    The common factor here is $8$ and you should be able show that he power is divisible by $8$, so the residue modulo $1000$ can be determined by looking at the residue modulo $1000/8=125$
    $endgroup$
    – Mark Bennet
    3 hours ago










  • $begingroup$
    @Mark is correct, and in fact we can factor it out in a slick operational way that avoids using CRT by using the mod Distributive Law, as I show in my answer. This usually ends up being simpler than rotely applying CRT = Chinese Remainder when the base shares a common factor with the modulus.
    $endgroup$
    – Bill Dubuque
    41 mins ago
















$begingroup$
The common factor here is $8$ and you should be able show that he power is divisible by $8$, so the residue modulo $1000$ can be determined by looking at the residue modulo $1000/8=125$
$endgroup$
– Mark Bennet
3 hours ago




$begingroup$
The common factor here is $8$ and you should be able show that he power is divisible by $8$, so the residue modulo $1000$ can be determined by looking at the residue modulo $1000/8=125$
$endgroup$
– Mark Bennet
3 hours ago












$begingroup$
@Mark is correct, and in fact we can factor it out in a slick operational way that avoids using CRT by using the mod Distributive Law, as I show in my answer. This usually ends up being simpler than rotely applying CRT = Chinese Remainder when the base shares a common factor with the modulus.
$endgroup$
– Bill Dubuque
41 mins ago





$begingroup$
@Mark is correct, and in fact we can factor it out in a slick operational way that avoids using CRT by using the mod Distributive Law, as I show in my answer. This usually ends up being simpler than rotely applying CRT = Chinese Remainder when the base shares a common factor with the modulus.
$endgroup$
– Bill Dubuque
41 mins ago











4 Answers
4






active

oldest

votes


















1












$begingroup$

It's a lot simpler than it looks. I shall call the number $N$.



You will know the residue modulo $10^3$, thus the last three digits, if you first get the residues modulo $2^3=8$ and modulo $5^3=125$.



$N$ is obviously a multiple of $8$, thus $Nequiv 0bmod 8$. Which leaves $bmod 125$.



The base $2032equiv 32$. When this is raised to a power, the residue of this power depends only on the residue of the exponent $bmod 100$ where $100$ is the Euler totient of $125$. But the exponent on $2032$ has the form



$2031^10k=(2030+1)^10k=(textbinomial expansion)=100m+1$



So $Nequiv 32^1equiv 32bmod 125$. The only multiple of $8$ between $0$ and $999$ satisfying this result is $32$ itself so ... $Nequiv 32bmod 1000$. Meaning the last three digits were there all along, the $colorblue032$ in the base $2032$!






share|cite|improve this answer











$endgroup$








  • 1




    $begingroup$
    (+1) same answer I got, by means similar enough that I won't add another post here.
    $endgroup$
    – robjohn
    2 hours ago











  • $begingroup$
    Worth emphasis is that arguments like this can be presented completely operationally by employing the mod Distributive Law, and this clarifies and simplifies the arithmetic - see my answer.
    $endgroup$
    – Bill Dubuque
    1 hour ago



















0












$begingroup$

By the Chinese Remainder Theorem, if you want to find what remainder a given number has when divided by $1000$, you can split that into 2 problems: Find the remainder$mod 8$ and$mod 125$. Obviously



$$z_0:=2032^2031^2030^dots^2^1 equiv 0 pmod 8$$



What remains to be found is $x_0 in [0,124]$ in



$$z_0 equiv x_0 pmod 125.$$



As $z_0$ is now coprime to $125$, you can apply Euler's theorem now. With



$$z_1:=2031^2030^dots^2^1$$



and



$$phi(125)=100$$ the new problem becomes to find $x_1 in [0,99]$ in



$$z_1 equiv x_1 pmod 100$$



and then use



$$32^x_1 equiv x_0 pmod 125$$



to find $x_0$.



So this reduced the original problem$mod 1000$ to a smaller problem$mod 100$.



Applying this reduction procedure a few more times (using the Chinese Remainder Theorem if appropriate), should result in congruences with smaller and smaller module that can in the end be solved (e.g $mod 2$).



Then to solve the original problem you need to back-substitute the calculated $x_i$ to get $x_i-1$, just as outlined for $x_1,x_0$ above.






share|cite|improve this answer









$endgroup$




















    0












    $begingroup$

    Don't be scared. If it turns into a monster and eats you, run away after you throw stones at it. Don't run away before throwing stones just because it looks like a monster.



    $2032^monster$ and $1000$ are relatively prime so we can't use Euler theorem but we can break it down with Chinese remainder theorem.



    $2032^monster = 0 pmod 8$ and so we just need to solve $2032^monster pmod 125$ and for that we can use Euler Theorem.



    $phi(125=5^3) = (5-1)*5^3-1 = 100$.



    So $2032^monster equiv 32^monster % 100$.



    And $monster = 2031^littlemonsterequiv 31^littlemonsterpmod 100$



    $31$ and $100$ are relatively prime and $phi(100)= 40$ so



    $31^littlemonster equiv 31^littlemonster % 40 pmod 100$.



    $littlemonster = 2030^smallmonster$ but $5|2030$ and as $smallmonster > 2$ we know $8|2^smallmonster$ and $2^smallmonster|2030^smallmonster$.



    So $littlemonster equiv 0 pmod 40$.



    $2031^littlemonster equiv 31^0 equiv 1 pmod 100$



    So $2032^monster equiv 31 pmod 125$



    So $2032^monster equiv 0 pmod 8$ and $2032^monster equiv 31 pmod 125$.



    So $2032^monster equiv 31 + 125k pmod 1000$ where $8|31 + 125k$.



    I.e. $31+125k equiv -1 - 3k equiv 0 pmod 8$ so $3k equiv -1equiv 15 pmod 8$ so $k=5$ and



    $2032^monster equiv 656pmod1000$






    share|cite|improve this answer









    $endgroup$




















      0












      $begingroup$

      $bmod 1000!: 32^large 2031^LARGE 2k!!equiv, 8left[dfraccolor#0a032^large 2031^LARGE 2k8 bmod color#0a0125right]! equiv 8left[dfraccolor#c00328bmod 125right]! equiv 32, $ by



      $ ,beginalign !bmod color#0a0125!: color#0a032^large 2031^LARGE 2k!!
      &equiv, 2^large 5cdot 2031^LARGE 2k! bmod 100 rm by 100 = phi(125) rm [Euler totient]\
      &equiv,2^large 5(color#b6f2031^LARGE color#d4f2k! bmod 20) rm by mod Distributive Law\
      &equiv,2^large 5(color#b6f1^LARGE k)equiv, color#c0032 rm by color#b6f2031^large 2!equiv 11^large 2equivcolor#b6f 1!!!pmod!20\
      endalign $






      share|cite|improve this answer











      $endgroup$












      • $begingroup$
        We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
        $endgroup$
        – Bill Dubuque
        1 hour ago











      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%2f3161051%2ffind-last-3-digits-of-this-monster-number%23new-answer', 'question_page');

      );

      Post as a guest















      Required, but never shown

























      4 Answers
      4






      active

      oldest

      votes








      4 Answers
      4






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes









      1












      $begingroup$

      It's a lot simpler than it looks. I shall call the number $N$.



      You will know the residue modulo $10^3$, thus the last three digits, if you first get the residues modulo $2^3=8$ and modulo $5^3=125$.



      $N$ is obviously a multiple of $8$, thus $Nequiv 0bmod 8$. Which leaves $bmod 125$.



      The base $2032equiv 32$. When this is raised to a power, the residue of this power depends only on the residue of the exponent $bmod 100$ where $100$ is the Euler totient of $125$. But the exponent on $2032$ has the form



      $2031^10k=(2030+1)^10k=(textbinomial expansion)=100m+1$



      So $Nequiv 32^1equiv 32bmod 125$. The only multiple of $8$ between $0$ and $999$ satisfying this result is $32$ itself so ... $Nequiv 32bmod 1000$. Meaning the last three digits were there all along, the $colorblue032$ in the base $2032$!






      share|cite|improve this answer











      $endgroup$








      • 1




        $begingroup$
        (+1) same answer I got, by means similar enough that I won't add another post here.
        $endgroup$
        – robjohn
        2 hours ago











      • $begingroup$
        Worth emphasis is that arguments like this can be presented completely operationally by employing the mod Distributive Law, and this clarifies and simplifies the arithmetic - see my answer.
        $endgroup$
        – Bill Dubuque
        1 hour ago
















      1












      $begingroup$

      It's a lot simpler than it looks. I shall call the number $N$.



      You will know the residue modulo $10^3$, thus the last three digits, if you first get the residues modulo $2^3=8$ and modulo $5^3=125$.



      $N$ is obviously a multiple of $8$, thus $Nequiv 0bmod 8$. Which leaves $bmod 125$.



      The base $2032equiv 32$. When this is raised to a power, the residue of this power depends only on the residue of the exponent $bmod 100$ where $100$ is the Euler totient of $125$. But the exponent on $2032$ has the form



      $2031^10k=(2030+1)^10k=(textbinomial expansion)=100m+1$



      So $Nequiv 32^1equiv 32bmod 125$. The only multiple of $8$ between $0$ and $999$ satisfying this result is $32$ itself so ... $Nequiv 32bmod 1000$. Meaning the last three digits were there all along, the $colorblue032$ in the base $2032$!






      share|cite|improve this answer











      $endgroup$








      • 1




        $begingroup$
        (+1) same answer I got, by means similar enough that I won't add another post here.
        $endgroup$
        – robjohn
        2 hours ago











      • $begingroup$
        Worth emphasis is that arguments like this can be presented completely operationally by employing the mod Distributive Law, and this clarifies and simplifies the arithmetic - see my answer.
        $endgroup$
        – Bill Dubuque
        1 hour ago














      1












      1








      1





      $begingroup$

      It's a lot simpler than it looks. I shall call the number $N$.



      You will know the residue modulo $10^3$, thus the last three digits, if you first get the residues modulo $2^3=8$ and modulo $5^3=125$.



      $N$ is obviously a multiple of $8$, thus $Nequiv 0bmod 8$. Which leaves $bmod 125$.



      The base $2032equiv 32$. When this is raised to a power, the residue of this power depends only on the residue of the exponent $bmod 100$ where $100$ is the Euler totient of $125$. But the exponent on $2032$ has the form



      $2031^10k=(2030+1)^10k=(textbinomial expansion)=100m+1$



      So $Nequiv 32^1equiv 32bmod 125$. The only multiple of $8$ between $0$ and $999$ satisfying this result is $32$ itself so ... $Nequiv 32bmod 1000$. Meaning the last three digits were there all along, the $colorblue032$ in the base $2032$!






      share|cite|improve this answer











      $endgroup$



      It's a lot simpler than it looks. I shall call the number $N$.



      You will know the residue modulo $10^3$, thus the last three digits, if you first get the residues modulo $2^3=8$ and modulo $5^3=125$.



      $N$ is obviously a multiple of $8$, thus $Nequiv 0bmod 8$. Which leaves $bmod 125$.



      The base $2032equiv 32$. When this is raised to a power, the residue of this power depends only on the residue of the exponent $bmod 100$ where $100$ is the Euler totient of $125$. But the exponent on $2032$ has the form



      $2031^10k=(2030+1)^10k=(textbinomial expansion)=100m+1$



      So $Nequiv 32^1equiv 32bmod 125$. The only multiple of $8$ between $0$ and $999$ satisfying this result is $32$ itself so ... $Nequiv 32bmod 1000$. Meaning the last three digits were there all along, the $colorblue032$ in the base $2032$!







      share|cite|improve this answer














      share|cite|improve this answer



      share|cite|improve this answer








      edited 3 hours ago

























      answered 3 hours ago









      Oscar LanziOscar Lanzi

      13.2k12136




      13.2k12136







      • 1




        $begingroup$
        (+1) same answer I got, by means similar enough that I won't add another post here.
        $endgroup$
        – robjohn
        2 hours ago











      • $begingroup$
        Worth emphasis is that arguments like this can be presented completely operationally by employing the mod Distributive Law, and this clarifies and simplifies the arithmetic - see my answer.
        $endgroup$
        – Bill Dubuque
        1 hour ago













      • 1




        $begingroup$
        (+1) same answer I got, by means similar enough that I won't add another post here.
        $endgroup$
        – robjohn
        2 hours ago











      • $begingroup$
        Worth emphasis is that arguments like this can be presented completely operationally by employing the mod Distributive Law, and this clarifies and simplifies the arithmetic - see my answer.
        $endgroup$
        – Bill Dubuque
        1 hour ago








      1




      1




      $begingroup$
      (+1) same answer I got, by means similar enough that I won't add another post here.
      $endgroup$
      – robjohn
      2 hours ago





      $begingroup$
      (+1) same answer I got, by means similar enough that I won't add another post here.
      $endgroup$
      – robjohn
      2 hours ago













      $begingroup$
      Worth emphasis is that arguments like this can be presented completely operationally by employing the mod Distributive Law, and this clarifies and simplifies the arithmetic - see my answer.
      $endgroup$
      – Bill Dubuque
      1 hour ago





      $begingroup$
      Worth emphasis is that arguments like this can be presented completely operationally by employing the mod Distributive Law, and this clarifies and simplifies the arithmetic - see my answer.
      $endgroup$
      – Bill Dubuque
      1 hour ago












      0












      $begingroup$

      By the Chinese Remainder Theorem, if you want to find what remainder a given number has when divided by $1000$, you can split that into 2 problems: Find the remainder$mod 8$ and$mod 125$. Obviously



      $$z_0:=2032^2031^2030^dots^2^1 equiv 0 pmod 8$$



      What remains to be found is $x_0 in [0,124]$ in



      $$z_0 equiv x_0 pmod 125.$$



      As $z_0$ is now coprime to $125$, you can apply Euler's theorem now. With



      $$z_1:=2031^2030^dots^2^1$$



      and



      $$phi(125)=100$$ the new problem becomes to find $x_1 in [0,99]$ in



      $$z_1 equiv x_1 pmod 100$$



      and then use



      $$32^x_1 equiv x_0 pmod 125$$



      to find $x_0$.



      So this reduced the original problem$mod 1000$ to a smaller problem$mod 100$.



      Applying this reduction procedure a few more times (using the Chinese Remainder Theorem if appropriate), should result in congruences with smaller and smaller module that can in the end be solved (e.g $mod 2$).



      Then to solve the original problem you need to back-substitute the calculated $x_i$ to get $x_i-1$, just as outlined for $x_1,x_0$ above.






      share|cite|improve this answer









      $endgroup$

















        0












        $begingroup$

        By the Chinese Remainder Theorem, if you want to find what remainder a given number has when divided by $1000$, you can split that into 2 problems: Find the remainder$mod 8$ and$mod 125$. Obviously



        $$z_0:=2032^2031^2030^dots^2^1 equiv 0 pmod 8$$



        What remains to be found is $x_0 in [0,124]$ in



        $$z_0 equiv x_0 pmod 125.$$



        As $z_0$ is now coprime to $125$, you can apply Euler's theorem now. With



        $$z_1:=2031^2030^dots^2^1$$



        and



        $$phi(125)=100$$ the new problem becomes to find $x_1 in [0,99]$ in



        $$z_1 equiv x_1 pmod 100$$



        and then use



        $$32^x_1 equiv x_0 pmod 125$$



        to find $x_0$.



        So this reduced the original problem$mod 1000$ to a smaller problem$mod 100$.



        Applying this reduction procedure a few more times (using the Chinese Remainder Theorem if appropriate), should result in congruences with smaller and smaller module that can in the end be solved (e.g $mod 2$).



        Then to solve the original problem you need to back-substitute the calculated $x_i$ to get $x_i-1$, just as outlined for $x_1,x_0$ above.






        share|cite|improve this answer









        $endgroup$















          0












          0








          0





          $begingroup$

          By the Chinese Remainder Theorem, if you want to find what remainder a given number has when divided by $1000$, you can split that into 2 problems: Find the remainder$mod 8$ and$mod 125$. Obviously



          $$z_0:=2032^2031^2030^dots^2^1 equiv 0 pmod 8$$



          What remains to be found is $x_0 in [0,124]$ in



          $$z_0 equiv x_0 pmod 125.$$



          As $z_0$ is now coprime to $125$, you can apply Euler's theorem now. With



          $$z_1:=2031^2030^dots^2^1$$



          and



          $$phi(125)=100$$ the new problem becomes to find $x_1 in [0,99]$ in



          $$z_1 equiv x_1 pmod 100$$



          and then use



          $$32^x_1 equiv x_0 pmod 125$$



          to find $x_0$.



          So this reduced the original problem$mod 1000$ to a smaller problem$mod 100$.



          Applying this reduction procedure a few more times (using the Chinese Remainder Theorem if appropriate), should result in congruences with smaller and smaller module that can in the end be solved (e.g $mod 2$).



          Then to solve the original problem you need to back-substitute the calculated $x_i$ to get $x_i-1$, just as outlined for $x_1,x_0$ above.






          share|cite|improve this answer









          $endgroup$



          By the Chinese Remainder Theorem, if you want to find what remainder a given number has when divided by $1000$, you can split that into 2 problems: Find the remainder$mod 8$ and$mod 125$. Obviously



          $$z_0:=2032^2031^2030^dots^2^1 equiv 0 pmod 8$$



          What remains to be found is $x_0 in [0,124]$ in



          $$z_0 equiv x_0 pmod 125.$$



          As $z_0$ is now coprime to $125$, you can apply Euler's theorem now. With



          $$z_1:=2031^2030^dots^2^1$$



          and



          $$phi(125)=100$$ the new problem becomes to find $x_1 in [0,99]$ in



          $$z_1 equiv x_1 pmod 100$$



          and then use



          $$32^x_1 equiv x_0 pmod 125$$



          to find $x_0$.



          So this reduced the original problem$mod 1000$ to a smaller problem$mod 100$.



          Applying this reduction procedure a few more times (using the Chinese Remainder Theorem if appropriate), should result in congruences with smaller and smaller module that can in the end be solved (e.g $mod 2$).



          Then to solve the original problem you need to back-substitute the calculated $x_i$ to get $x_i-1$, just as outlined for $x_1,x_0$ above.







          share|cite|improve this answer












          share|cite|improve this answer



          share|cite|improve this answer










          answered 3 hours ago









          IngixIngix

          5,032159




          5,032159





















              0












              $begingroup$

              Don't be scared. If it turns into a monster and eats you, run away after you throw stones at it. Don't run away before throwing stones just because it looks like a monster.



              $2032^monster$ and $1000$ are relatively prime so we can't use Euler theorem but we can break it down with Chinese remainder theorem.



              $2032^monster = 0 pmod 8$ and so we just need to solve $2032^monster pmod 125$ and for that we can use Euler Theorem.



              $phi(125=5^3) = (5-1)*5^3-1 = 100$.



              So $2032^monster equiv 32^monster % 100$.



              And $monster = 2031^littlemonsterequiv 31^littlemonsterpmod 100$



              $31$ and $100$ are relatively prime and $phi(100)= 40$ so



              $31^littlemonster equiv 31^littlemonster % 40 pmod 100$.



              $littlemonster = 2030^smallmonster$ but $5|2030$ and as $smallmonster > 2$ we know $8|2^smallmonster$ and $2^smallmonster|2030^smallmonster$.



              So $littlemonster equiv 0 pmod 40$.



              $2031^littlemonster equiv 31^0 equiv 1 pmod 100$



              So $2032^monster equiv 31 pmod 125$



              So $2032^monster equiv 0 pmod 8$ and $2032^monster equiv 31 pmod 125$.



              So $2032^monster equiv 31 + 125k pmod 1000$ where $8|31 + 125k$.



              I.e. $31+125k equiv -1 - 3k equiv 0 pmod 8$ so $3k equiv -1equiv 15 pmod 8$ so $k=5$ and



              $2032^monster equiv 656pmod1000$






              share|cite|improve this answer









              $endgroup$

















                0












                $begingroup$

                Don't be scared. If it turns into a monster and eats you, run away after you throw stones at it. Don't run away before throwing stones just because it looks like a monster.



                $2032^monster$ and $1000$ are relatively prime so we can't use Euler theorem but we can break it down with Chinese remainder theorem.



                $2032^monster = 0 pmod 8$ and so we just need to solve $2032^monster pmod 125$ and for that we can use Euler Theorem.



                $phi(125=5^3) = (5-1)*5^3-1 = 100$.



                So $2032^monster equiv 32^monster % 100$.



                And $monster = 2031^littlemonsterequiv 31^littlemonsterpmod 100$



                $31$ and $100$ are relatively prime and $phi(100)= 40$ so



                $31^littlemonster equiv 31^littlemonster % 40 pmod 100$.



                $littlemonster = 2030^smallmonster$ but $5|2030$ and as $smallmonster > 2$ we know $8|2^smallmonster$ and $2^smallmonster|2030^smallmonster$.



                So $littlemonster equiv 0 pmod 40$.



                $2031^littlemonster equiv 31^0 equiv 1 pmod 100$



                So $2032^monster equiv 31 pmod 125$



                So $2032^monster equiv 0 pmod 8$ and $2032^monster equiv 31 pmod 125$.



                So $2032^monster equiv 31 + 125k pmod 1000$ where $8|31 + 125k$.



                I.e. $31+125k equiv -1 - 3k equiv 0 pmod 8$ so $3k equiv -1equiv 15 pmod 8$ so $k=5$ and



                $2032^monster equiv 656pmod1000$






                share|cite|improve this answer









                $endgroup$















                  0












                  0








                  0





                  $begingroup$

                  Don't be scared. If it turns into a monster and eats you, run away after you throw stones at it. Don't run away before throwing stones just because it looks like a monster.



                  $2032^monster$ and $1000$ are relatively prime so we can't use Euler theorem but we can break it down with Chinese remainder theorem.



                  $2032^monster = 0 pmod 8$ and so we just need to solve $2032^monster pmod 125$ and for that we can use Euler Theorem.



                  $phi(125=5^3) = (5-1)*5^3-1 = 100$.



                  So $2032^monster equiv 32^monster % 100$.



                  And $monster = 2031^littlemonsterequiv 31^littlemonsterpmod 100$



                  $31$ and $100$ are relatively prime and $phi(100)= 40$ so



                  $31^littlemonster equiv 31^littlemonster % 40 pmod 100$.



                  $littlemonster = 2030^smallmonster$ but $5|2030$ and as $smallmonster > 2$ we know $8|2^smallmonster$ and $2^smallmonster|2030^smallmonster$.



                  So $littlemonster equiv 0 pmod 40$.



                  $2031^littlemonster equiv 31^0 equiv 1 pmod 100$



                  So $2032^monster equiv 31 pmod 125$



                  So $2032^monster equiv 0 pmod 8$ and $2032^monster equiv 31 pmod 125$.



                  So $2032^monster equiv 31 + 125k pmod 1000$ where $8|31 + 125k$.



                  I.e. $31+125k equiv -1 - 3k equiv 0 pmod 8$ so $3k equiv -1equiv 15 pmod 8$ so $k=5$ and



                  $2032^monster equiv 656pmod1000$






                  share|cite|improve this answer









                  $endgroup$



                  Don't be scared. If it turns into a monster and eats you, run away after you throw stones at it. Don't run away before throwing stones just because it looks like a monster.



                  $2032^monster$ and $1000$ are relatively prime so we can't use Euler theorem but we can break it down with Chinese remainder theorem.



                  $2032^monster = 0 pmod 8$ and so we just need to solve $2032^monster pmod 125$ and for that we can use Euler Theorem.



                  $phi(125=5^3) = (5-1)*5^3-1 = 100$.



                  So $2032^monster equiv 32^monster % 100$.



                  And $monster = 2031^littlemonsterequiv 31^littlemonsterpmod 100$



                  $31$ and $100$ are relatively prime and $phi(100)= 40$ so



                  $31^littlemonster equiv 31^littlemonster % 40 pmod 100$.



                  $littlemonster = 2030^smallmonster$ but $5|2030$ and as $smallmonster > 2$ we know $8|2^smallmonster$ and $2^smallmonster|2030^smallmonster$.



                  So $littlemonster equiv 0 pmod 40$.



                  $2031^littlemonster equiv 31^0 equiv 1 pmod 100$



                  So $2032^monster equiv 31 pmod 125$



                  So $2032^monster equiv 0 pmod 8$ and $2032^monster equiv 31 pmod 125$.



                  So $2032^monster equiv 31 + 125k pmod 1000$ where $8|31 + 125k$.



                  I.e. $31+125k equiv -1 - 3k equiv 0 pmod 8$ so $3k equiv -1equiv 15 pmod 8$ so $k=5$ and



                  $2032^monster equiv 656pmod1000$







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered 1 hour ago









                  fleabloodfleablood

                  73.1k22789




                  73.1k22789





















                      0












                      $begingroup$

                      $bmod 1000!: 32^large 2031^LARGE 2k!!equiv, 8left[dfraccolor#0a032^large 2031^LARGE 2k8 bmod color#0a0125right]! equiv 8left[dfraccolor#c00328bmod 125right]! equiv 32, $ by



                      $ ,beginalign !bmod color#0a0125!: color#0a032^large 2031^LARGE 2k!!
                      &equiv, 2^large 5cdot 2031^LARGE 2k! bmod 100 rm by 100 = phi(125) rm [Euler totient]\
                      &equiv,2^large 5(color#b6f2031^LARGE color#d4f2k! bmod 20) rm by mod Distributive Law\
                      &equiv,2^large 5(color#b6f1^LARGE k)equiv, color#c0032 rm by color#b6f2031^large 2!equiv 11^large 2equivcolor#b6f 1!!!pmod!20\
                      endalign $






                      share|cite|improve this answer











                      $endgroup$












                      • $begingroup$
                        We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
                        $endgroup$
                        – Bill Dubuque
                        1 hour ago
















                      0












                      $begingroup$

                      $bmod 1000!: 32^large 2031^LARGE 2k!!equiv, 8left[dfraccolor#0a032^large 2031^LARGE 2k8 bmod color#0a0125right]! equiv 8left[dfraccolor#c00328bmod 125right]! equiv 32, $ by



                      $ ,beginalign !bmod color#0a0125!: color#0a032^large 2031^LARGE 2k!!
                      &equiv, 2^large 5cdot 2031^LARGE 2k! bmod 100 rm by 100 = phi(125) rm [Euler totient]\
                      &equiv,2^large 5(color#b6f2031^LARGE color#d4f2k! bmod 20) rm by mod Distributive Law\
                      &equiv,2^large 5(color#b6f1^LARGE k)equiv, color#c0032 rm by color#b6f2031^large 2!equiv 11^large 2equivcolor#b6f 1!!!pmod!20\
                      endalign $






                      share|cite|improve this answer











                      $endgroup$












                      • $begingroup$
                        We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
                        $endgroup$
                        – Bill Dubuque
                        1 hour ago














                      0












                      0








                      0





                      $begingroup$

                      $bmod 1000!: 32^large 2031^LARGE 2k!!equiv, 8left[dfraccolor#0a032^large 2031^LARGE 2k8 bmod color#0a0125right]! equiv 8left[dfraccolor#c00328bmod 125right]! equiv 32, $ by



                      $ ,beginalign !bmod color#0a0125!: color#0a032^large 2031^LARGE 2k!!
                      &equiv, 2^large 5cdot 2031^LARGE 2k! bmod 100 rm by 100 = phi(125) rm [Euler totient]\
                      &equiv,2^large 5(color#b6f2031^LARGE color#d4f2k! bmod 20) rm by mod Distributive Law\
                      &equiv,2^large 5(color#b6f1^LARGE k)equiv, color#c0032 rm by color#b6f2031^large 2!equiv 11^large 2equivcolor#b6f 1!!!pmod!20\
                      endalign $






                      share|cite|improve this answer











                      $endgroup$



                      $bmod 1000!: 32^large 2031^LARGE 2k!!equiv, 8left[dfraccolor#0a032^large 2031^LARGE 2k8 bmod color#0a0125right]! equiv 8left[dfraccolor#c00328bmod 125right]! equiv 32, $ by



                      $ ,beginalign !bmod color#0a0125!: color#0a032^large 2031^LARGE 2k!!
                      &equiv, 2^large 5cdot 2031^LARGE 2k! bmod 100 rm by 100 = phi(125) rm [Euler totient]\
                      &equiv,2^large 5(color#b6f2031^LARGE color#d4f2k! bmod 20) rm by mod Distributive Law\
                      &equiv,2^large 5(color#b6f1^LARGE k)equiv, color#c0032 rm by color#b6f2031^large 2!equiv 11^large 2equivcolor#b6f 1!!!pmod!20\
                      endalign $







                      share|cite|improve this answer














                      share|cite|improve this answer



                      share|cite|improve this answer








                      edited 1 hour ago

























                      answered 1 hour ago









                      Bill DubuqueBill Dubuque

                      213k29195654




                      213k29195654











                      • $begingroup$
                        We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
                        $endgroup$
                        – Bill Dubuque
                        1 hour ago

















                      • $begingroup$
                        We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
                        $endgroup$
                        – Bill Dubuque
                        1 hour ago
















                      $begingroup$
                      We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
                      $endgroup$
                      – Bill Dubuque
                      1 hour ago





                      $begingroup$
                      We used twice: $, abbmod ac, =, a,(bbmod c), =, $ mod Distributive Law $ $
                      $endgroup$
                      – Bill Dubuque
                      1 hour ago


















                      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%2f3161051%2ffind-last-3-digits-of-this-monster-number%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

                      How does Billy Russo acquire his 'Jigsaw' mask? Unicorn Meta Zoo #1: Why another podcast? Announcing the arrival of Valued Associate #679: Cesar Manara Favourite questions and answers from the 1st quarter of 2019Why does Bane wear the mask?Why does Kylo Ren wear a mask?Why did Captain America remove his mask while fighting Batroc the Leaper?How did the OA acquire her wisdom?Is Billy Breckenridge gay?How does Adrian Toomes hide his earnings from the IRS?What is the state of affairs on Nootka Sound by the end of season 1?How did Tia Dalma acquire Captain Barbossa's body?How is one “Deemed Worthy”, to acquire the Greatsword “Dawn”?How did Karen acquire the handgun?

                      Личност Атрибути на личността | Литература и източници | НавигацияРаждането на личносттаредактиратередактирате

                      A sequel to Domino's tragic life Why Christmas is for Friends Cold comfort at Charles' padSad farewell for Lady JanePS Most watched News videos