Find last 3 digits of $ 2032^{2031^{2030^{dots^{2^{1}}}}}$












7












$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 text{mod}hspace{0.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$








  • 2




    $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
    2 days 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
    2 days ago












  • $begingroup$
    Bah, that's no monster. Graham's Number is a monster!
    $endgroup$
    – Cort Ammon
    yesterday
















7












$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 text{mod}hspace{0.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$








  • 2




    $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
    2 days 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
    2 days ago












  • $begingroup$
    Bah, that's no monster. Graham's Number is a monster!
    $endgroup$
    – Cort Ammon
    yesterday














7












7








7


1



$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 text{mod}hspace{0.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 text{mod}hspace{0.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








edited yesterday









Asaf Karagila

307k33439770




307k33439770










asked 2 days ago









Kristin PeterselKristin Petersel

363




363








  • 2




    $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
    2 days 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
    2 days ago












  • $begingroup$
    Bah, that's no monster. Graham's Number is a monster!
    $endgroup$
    – Cort Ammon
    yesterday














  • 2




    $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
    2 days 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
    2 days ago












  • $begingroup$
    Bah, that's no monster. Graham's Number is a monster!
    $endgroup$
    – Cort Ammon
    yesterday








2




2




$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
2 days 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
2 days 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
2 days 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
2 days ago














$begingroup$
Bah, that's no monster. Graham's Number is a monster!
$endgroup$
– Cort Ammon
yesterday




$begingroup$
Bah, that's no monster. Graham's Number is a monster!
$endgroup$
– Cort Ammon
yesterday










4 Answers
4






active

oldest

votes


















6












$begingroup$

$bmod 1000!: 32^{large 2031^{LARGE 2k}}!!equiv, 8left[dfrac{color{#0a0}{32^{large 2031^{LARGE 2k}}}}8 bmod color{#0a0}{125}right]! equiv 8left[dfrac{color{#c00}{32}}8bmod 125right]! equiv 32, $ by



$ ,begin{align} !bmod color{#0a0}{125}!: color{#0a0}{32^{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{#b6f}{2031}^{LARGE color{#d4f}2k}! bmod 20)} {rm by mod Distributive Law}\
&equiv,{2^{large 5(color{#b6f}1^{LARGE k})}}equiv, color{#c00}{32} {rm by} color{#b6f}{2031^{large 2}}!equiv 11^{large 2}equivcolor{#b6f} 1!!!pmod{!20}\
end{align} $






share|cite|improve this answer











$endgroup$









  • 2




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












  • $begingroup$
    How would you prove this?
    $endgroup$
    – Markus Punnar
    yesterday










  • $begingroup$
    @Markus Prove what? If you mean the mod Distributive Law then follow the link in my prior comment.
    $endgroup$
    – Bill Dubuque
    yesterday



















4












$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}=(text{binomial 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 $color{blue}{032}$ in the base $2032$!






share|cite|improve this answer











$endgroup$









  • 2




    $begingroup$
    (+1) same answer I got, by means similar enough that I won't add another post here.
    $endgroup$
    – robjohn
    2 days 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
    2 days ago





















4












$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^{littlemonster}equiv 31^{littlemonster}pmod {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 32 pmod {125}$



So $2032^{monster} equiv 0 pmod 8$ and $2032^{monster} equiv 32 pmod {125}$.



As $8|32$ we are done. $2032^{monster} equiv 32 pmod {1000}$.



and the last three digits are $032$.






share|cite|improve this answer











$endgroup$









  • 1




    $begingroup$
    Good idea, but you rendered $2031^{2030^{···}} bmod 125$. You need $2032^{2031^{2030^{···}}} bmod 125$.
    $endgroup$
    – Oscar Lanzi
    2 days ago










  • $begingroup$
    oops..............
    $endgroup$
    – fleablood
    yesterday






  • 1




    $begingroup$
    Actually I rendered it as $2032^{2031^{...}}equiv 31^{2031^{...}}pmod{125}$... which is still an error.
    $endgroup$
    – fleablood
    yesterday



















2












$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$













    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-203220312030-dots21%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









    6












    $begingroup$

    $bmod 1000!: 32^{large 2031^{LARGE 2k}}!!equiv, 8left[dfrac{color{#0a0}{32^{large 2031^{LARGE 2k}}}}8 bmod color{#0a0}{125}right]! equiv 8left[dfrac{color{#c00}{32}}8bmod 125right]! equiv 32, $ by



    $ ,begin{align} !bmod color{#0a0}{125}!: color{#0a0}{32^{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{#b6f}{2031}^{LARGE color{#d4f}2k}! bmod 20)} {rm by mod Distributive Law}\
    &equiv,{2^{large 5(color{#b6f}1^{LARGE k})}}equiv, color{#c00}{32} {rm by} color{#b6f}{2031^{large 2}}!equiv 11^{large 2}equivcolor{#b6f} 1!!!pmod{!20}\
    end{align} $






    share|cite|improve this answer











    $endgroup$









    • 2




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












    • $begingroup$
      How would you prove this?
      $endgroup$
      – Markus Punnar
      yesterday










    • $begingroup$
      @Markus Prove what? If you mean the mod Distributive Law then follow the link in my prior comment.
      $endgroup$
      – Bill Dubuque
      yesterday
















    6












    $begingroup$

    $bmod 1000!: 32^{large 2031^{LARGE 2k}}!!equiv, 8left[dfrac{color{#0a0}{32^{large 2031^{LARGE 2k}}}}8 bmod color{#0a0}{125}right]! equiv 8left[dfrac{color{#c00}{32}}8bmod 125right]! equiv 32, $ by



    $ ,begin{align} !bmod color{#0a0}{125}!: color{#0a0}{32^{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{#b6f}{2031}^{LARGE color{#d4f}2k}! bmod 20)} {rm by mod Distributive Law}\
    &equiv,{2^{large 5(color{#b6f}1^{LARGE k})}}equiv, color{#c00}{32} {rm by} color{#b6f}{2031^{large 2}}!equiv 11^{large 2}equivcolor{#b6f} 1!!!pmod{!20}\
    end{align} $






    share|cite|improve this answer











    $endgroup$









    • 2




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












    • $begingroup$
      How would you prove this?
      $endgroup$
      – Markus Punnar
      yesterday










    • $begingroup$
      @Markus Prove what? If you mean the mod Distributive Law then follow the link in my prior comment.
      $endgroup$
      – Bill Dubuque
      yesterday














    6












    6








    6





    $begingroup$

    $bmod 1000!: 32^{large 2031^{LARGE 2k}}!!equiv, 8left[dfrac{color{#0a0}{32^{large 2031^{LARGE 2k}}}}8 bmod color{#0a0}{125}right]! equiv 8left[dfrac{color{#c00}{32}}8bmod 125right]! equiv 32, $ by



    $ ,begin{align} !bmod color{#0a0}{125}!: color{#0a0}{32^{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{#b6f}{2031}^{LARGE color{#d4f}2k}! bmod 20)} {rm by mod Distributive Law}\
    &equiv,{2^{large 5(color{#b6f}1^{LARGE k})}}equiv, color{#c00}{32} {rm by} color{#b6f}{2031^{large 2}}!equiv 11^{large 2}equivcolor{#b6f} 1!!!pmod{!20}\
    end{align} $






    share|cite|improve this answer











    $endgroup$



    $bmod 1000!: 32^{large 2031^{LARGE 2k}}!!equiv, 8left[dfrac{color{#0a0}{32^{large 2031^{LARGE 2k}}}}8 bmod color{#0a0}{125}right]! equiv 8left[dfrac{color{#c00}{32}}8bmod 125right]! equiv 32, $ by



    $ ,begin{align} !bmod color{#0a0}{125}!: color{#0a0}{32^{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{#b6f}{2031}^{LARGE color{#d4f}2k}! bmod 20)} {rm by mod Distributive Law}\
    &equiv,{2^{large 5(color{#b6f}1^{LARGE k})}}equiv, color{#c00}{32} {rm by} color{#b6f}{2031^{large 2}}!equiv 11^{large 2}equivcolor{#b6f} 1!!!pmod{!20}\
    end{align} $







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited 2 days ago

























    answered 2 days ago









    Bill DubuqueBill Dubuque

    213k29195654




    213k29195654








    • 2




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












    • $begingroup$
      How would you prove this?
      $endgroup$
      – Markus Punnar
      yesterday










    • $begingroup$
      @Markus Prove what? If you mean the mod Distributive Law then follow the link in my prior comment.
      $endgroup$
      – Bill Dubuque
      yesterday














    • 2




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












    • $begingroup$
      How would you prove this?
      $endgroup$
      – Markus Punnar
      yesterday










    • $begingroup$
      @Markus Prove what? If you mean the mod Distributive Law then follow the link in my prior comment.
      $endgroup$
      – Bill Dubuque
      yesterday








    2




    2




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






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














    $begingroup$
    How would you prove this?
    $endgroup$
    – Markus Punnar
    yesterday




    $begingroup$
    How would you prove this?
    $endgroup$
    – Markus Punnar
    yesterday












    $begingroup$
    @Markus Prove what? If you mean the mod Distributive Law then follow the link in my prior comment.
    $endgroup$
    – Bill Dubuque
    yesterday




    $begingroup$
    @Markus Prove what? If you mean the mod Distributive Law then follow the link in my prior comment.
    $endgroup$
    – Bill Dubuque
    yesterday











    4












    $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}=(text{binomial 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 $color{blue}{032}$ in the base $2032$!






    share|cite|improve this answer











    $endgroup$









    • 2




      $begingroup$
      (+1) same answer I got, by means similar enough that I won't add another post here.
      $endgroup$
      – robjohn
      2 days 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
      2 days ago


















    4












    $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}=(text{binomial 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 $color{blue}{032}$ in the base $2032$!






    share|cite|improve this answer











    $endgroup$









    • 2




      $begingroup$
      (+1) same answer I got, by means similar enough that I won't add another post here.
      $endgroup$
      – robjohn
      2 days 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
      2 days ago
















    4












    4








    4





    $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}=(text{binomial 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 $color{blue}{032}$ 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}=(text{binomial 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 $color{blue}{032}$ in the base $2032$!







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited 2 days ago

























    answered 2 days ago









    Oscar LanziOscar Lanzi

    13.3k12136




    13.3k12136








    • 2




      $begingroup$
      (+1) same answer I got, by means similar enough that I won't add another post here.
      $endgroup$
      – robjohn
      2 days 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
      2 days ago
















    • 2




      $begingroup$
      (+1) same answer I got, by means similar enough that I won't add another post here.
      $endgroup$
      – robjohn
      2 days 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
      2 days ago










    2




    2




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






    $begingroup$
    (+1) same answer I got, by means similar enough that I won't add another post here.
    $endgroup$
    – robjohn
    2 days 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
    2 days 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
    2 days ago













    4












    $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^{littlemonster}equiv 31^{littlemonster}pmod {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 32 pmod {125}$



    So $2032^{monster} equiv 0 pmod 8$ and $2032^{monster} equiv 32 pmod {125}$.



    As $8|32$ we are done. $2032^{monster} equiv 32 pmod {1000}$.



    and the last three digits are $032$.






    share|cite|improve this answer











    $endgroup$









    • 1




      $begingroup$
      Good idea, but you rendered $2031^{2030^{···}} bmod 125$. You need $2032^{2031^{2030^{···}}} bmod 125$.
      $endgroup$
      – Oscar Lanzi
      2 days ago










    • $begingroup$
      oops..............
      $endgroup$
      – fleablood
      yesterday






    • 1




      $begingroup$
      Actually I rendered it as $2032^{2031^{...}}equiv 31^{2031^{...}}pmod{125}$... which is still an error.
      $endgroup$
      – fleablood
      yesterday
















    4












    $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^{littlemonster}equiv 31^{littlemonster}pmod {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 32 pmod {125}$



    So $2032^{monster} equiv 0 pmod 8$ and $2032^{monster} equiv 32 pmod {125}$.



    As $8|32$ we are done. $2032^{monster} equiv 32 pmod {1000}$.



    and the last three digits are $032$.






    share|cite|improve this answer











    $endgroup$









    • 1




      $begingroup$
      Good idea, but you rendered $2031^{2030^{···}} bmod 125$. You need $2032^{2031^{2030^{···}}} bmod 125$.
      $endgroup$
      – Oscar Lanzi
      2 days ago










    • $begingroup$
      oops..............
      $endgroup$
      – fleablood
      yesterday






    • 1




      $begingroup$
      Actually I rendered it as $2032^{2031^{...}}equiv 31^{2031^{...}}pmod{125}$... which is still an error.
      $endgroup$
      – fleablood
      yesterday














    4












    4








    4





    $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^{littlemonster}equiv 31^{littlemonster}pmod {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 32 pmod {125}$



    So $2032^{monster} equiv 0 pmod 8$ and $2032^{monster} equiv 32 pmod {125}$.



    As $8|32$ we are done. $2032^{monster} equiv 32 pmod {1000}$.



    and the last three digits are $032$.






    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^{littlemonster}equiv 31^{littlemonster}pmod {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 32 pmod {125}$



    So $2032^{monster} equiv 0 pmod 8$ and $2032^{monster} equiv 32 pmod {125}$.



    As $8|32$ we are done. $2032^{monster} equiv 32 pmod {1000}$.



    and the last three digits are $032$.







    share|cite|improve this answer














    share|cite|improve this answer



    share|cite|improve this answer








    edited yesterday

























    answered 2 days ago









    fleabloodfleablood

    73.4k22791




    73.4k22791








    • 1




      $begingroup$
      Good idea, but you rendered $2031^{2030^{···}} bmod 125$. You need $2032^{2031^{2030^{···}}} bmod 125$.
      $endgroup$
      – Oscar Lanzi
      2 days ago










    • $begingroup$
      oops..............
      $endgroup$
      – fleablood
      yesterday






    • 1




      $begingroup$
      Actually I rendered it as $2032^{2031^{...}}equiv 31^{2031^{...}}pmod{125}$... which is still an error.
      $endgroup$
      – fleablood
      yesterday














    • 1




      $begingroup$
      Good idea, but you rendered $2031^{2030^{···}} bmod 125$. You need $2032^{2031^{2030^{···}}} bmod 125$.
      $endgroup$
      – Oscar Lanzi
      2 days ago










    • $begingroup$
      oops..............
      $endgroup$
      – fleablood
      yesterday






    • 1




      $begingroup$
      Actually I rendered it as $2032^{2031^{...}}equiv 31^{2031^{...}}pmod{125}$... which is still an error.
      $endgroup$
      – fleablood
      yesterday








    1




    1




    $begingroup$
    Good idea, but you rendered $2031^{2030^{···}} bmod 125$. You need $2032^{2031^{2030^{···}}} bmod 125$.
    $endgroup$
    – Oscar Lanzi
    2 days ago




    $begingroup$
    Good idea, but you rendered $2031^{2030^{···}} bmod 125$. You need $2032^{2031^{2030^{···}}} bmod 125$.
    $endgroup$
    – Oscar Lanzi
    2 days ago












    $begingroup$
    oops..............
    $endgroup$
    – fleablood
    yesterday




    $begingroup$
    oops..............
    $endgroup$
    – fleablood
    yesterday




    1




    1




    $begingroup$
    Actually I rendered it as $2032^{2031^{...}}equiv 31^{2031^{...}}pmod{125}$... which is still an error.
    $endgroup$
    – fleablood
    yesterday




    $begingroup$
    Actually I rendered it as $2032^{2031^{...}}equiv 31^{2031^{...}}pmod{125}$... which is still an error.
    $endgroup$
    – fleablood
    yesterday











    2












    $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$


















      2












      $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$
















        2












        2








        2





        $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 2 days ago









        IngixIngix

        5,077159




        5,077159






























            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-203220312030-dots21%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

            數位音樂下載

            When can things happen in Etherscan, such as the picture below?

            格利澤436b