Calculation of the last three digits of $132^{1601}$ (solving $x equiv 132^{1601} pmod {1000}$)












3












$begingroup$


I want to calculate the last three digits of $132^{1601}$. This is equivalent to find $x equiv 132^{1601} pmod {1000}$.



This is how I've solved it:



$Phi(1000)=400,$



$132^{400} equiv 1 pmod {1000},$



So $x equiv 132^{1601} pmod {1000} equiv (132^{400})^4132 pmod {1000} equiv 132 pmod {1000}.$



Is this approach correct?



Thanks.



EDIT: one of my friends suggest that it must be split using the Chinese reminder theorem and that the solution is $632 pmod {1000}$. How is that possible?






elementary-number-theory modular-arithmetic







share|cite|improve this question











$endgroup$








  • 2




    $begingroup$
    Note: Euler doesn't apply here since $gcd(132,1000)>1$.
    $endgroup$
    – lulu
    Feb 2 at 19:11






  • 1




    $begingroup$
    Your friend is correct; I have posted a solution along those lines below.
    $endgroup$
    – lulu
    Feb 2 at 19:19






  • 1




    $begingroup$
    math.stackexchange.com/questions/607829/…
    $endgroup$
    – lab bhattacharjee
    Feb 2 at 19:21






  • 1




    $begingroup$
    math.stackexchange.com/questions/1804639/… and math.stackexchange.com/questions/759810/last-two-digits-problem and math.stackexchange.com/questions/1844558/…
    $endgroup$
    – lab bhattacharjee
    Feb 2 at 19:23






  • 1




    $begingroup$
    @lab Thanks for spending the time to gather that list of related questions.
    $endgroup$
    – Bill Dubuque
    Feb 2 at 21:27
















3












$begingroup$


I want to calculate the last three digits of $132^{1601}$. This is equivalent to find $x equiv 132^{1601} pmod {1000}$.



This is how I've solved it:



$Phi(1000)=400,$



$132^{400} equiv 1 pmod {1000},$



So $x equiv 132^{1601} pmod {1000} equiv (132^{400})^4132 pmod {1000} equiv 132 pmod {1000}.$



Is this approach correct?



Thanks.



EDIT: one of my friends suggest that it must be split using the Chinese reminder theorem and that the solution is $632 pmod {1000}$. How is that possible?






elementary-number-theory modular-arithmetic







share|cite|improve this question











$endgroup$








  • 2




    $begingroup$
    Note: Euler doesn't apply here since $gcd(132,1000)>1$.
    $endgroup$
    – lulu
    Feb 2 at 19:11






  • 1




    $begingroup$
    Your friend is correct; I have posted a solution along those lines below.
    $endgroup$
    – lulu
    Feb 2 at 19:19






  • 1




    $begingroup$
    math.stackexchange.com/questions/607829/…
    $endgroup$
    – lab bhattacharjee
    Feb 2 at 19:21






  • 1




    $begingroup$
    math.stackexchange.com/questions/1804639/… and math.stackexchange.com/questions/759810/last-two-digits-problem and math.stackexchange.com/questions/1844558/…
    $endgroup$
    – lab bhattacharjee
    Feb 2 at 19:23






  • 1




    $begingroup$
    @lab Thanks for spending the time to gather that list of related questions.
    $endgroup$
    – Bill Dubuque
    Feb 2 at 21:27














3












3








3


1



$begingroup$


I want to calculate the last three digits of $132^{1601}$. This is equivalent to find $x equiv 132^{1601} pmod {1000}$.



This is how I've solved it:



$Phi(1000)=400,$



$132^{400} equiv 1 pmod {1000},$



So $x equiv 132^{1601} pmod {1000} equiv (132^{400})^4132 pmod {1000} equiv 132 pmod {1000}.$



Is this approach correct?



Thanks.



EDIT: one of my friends suggest that it must be split using the Chinese reminder theorem and that the solution is $632 pmod {1000}$. How is that possible?






elementary-number-theory modular-arithmetic







share|cite|improve this question











$endgroup$




I want to calculate the last three digits of $132^{1601}$. This is equivalent to find $x equiv 132^{1601} pmod {1000}$.



This is how I've solved it:



$Phi(1000)=400,$



$132^{400} equiv 1 pmod {1000},$



So $x equiv 132^{1601} pmod {1000} equiv (132^{400})^4132 pmod {1000} equiv 132 pmod {1000}.$



Is this approach correct?



Thanks.



EDIT: one of my friends suggest that it must be split using the Chinese reminder theorem and that the solution is $632 pmod {1000}$. How is that possible?






elementary-number-theory modular-arithmetic




elementary-number-theory modular-arithmetic






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Feb 3 at 3:16









J. W. Tanner

4,7721420




4,7721420










asked Feb 2 at 19:04









AlessarAlessar

313115




313115








  • 2




    $begingroup$
    Note: Euler doesn't apply here since $gcd(132,1000)>1$.
    $endgroup$
    – lulu
    Feb 2 at 19:11






  • 1




    $begingroup$
    Your friend is correct; I have posted a solution along those lines below.
    $endgroup$
    – lulu
    Feb 2 at 19:19






  • 1




    $begingroup$
    math.stackexchange.com/questions/607829/…
    $endgroup$
    – lab bhattacharjee
    Feb 2 at 19:21






  • 1




    $begingroup$
    math.stackexchange.com/questions/1804639/… and math.stackexchange.com/questions/759810/last-two-digits-problem and math.stackexchange.com/questions/1844558/…
    $endgroup$
    – lab bhattacharjee
    Feb 2 at 19:23






  • 1




    $begingroup$
    @lab Thanks for spending the time to gather that list of related questions.
    $endgroup$
    – Bill Dubuque
    Feb 2 at 21:27














  • 2




    $begingroup$
    Note: Euler doesn't apply here since $gcd(132,1000)>1$.
    $endgroup$
    – lulu
    Feb 2 at 19:11






  • 1




    $begingroup$
    Your friend is correct; I have posted a solution along those lines below.
    $endgroup$
    – lulu
    Feb 2 at 19:19






  • 1




    $begingroup$
    math.stackexchange.com/questions/607829/…
    $endgroup$
    – lab bhattacharjee
    Feb 2 at 19:21






  • 1




    $begingroup$
    math.stackexchange.com/questions/1804639/… and math.stackexchange.com/questions/759810/last-two-digits-problem and math.stackexchange.com/questions/1844558/…
    $endgroup$
    – lab bhattacharjee
    Feb 2 at 19:23






  • 1




    $begingroup$
    @lab Thanks for spending the time to gather that list of related questions.
    $endgroup$
    – Bill Dubuque
    Feb 2 at 21:27








2




2




$begingroup$
Note: Euler doesn't apply here since $gcd(132,1000)>1$.
$endgroup$
– lulu
Feb 2 at 19:11




$begingroup$
Note: Euler doesn't apply here since $gcd(132,1000)>1$.
$endgroup$
– lulu
Feb 2 at 19:11




1




1




$begingroup$
Your friend is correct; I have posted a solution along those lines below.
$endgroup$
– lulu
Feb 2 at 19:19




$begingroup$
Your friend is correct; I have posted a solution along those lines below.
$endgroup$
– lulu
Feb 2 at 19:19




1




1




$begingroup$
math.stackexchange.com/questions/607829/…
$endgroup$
– lab bhattacharjee
Feb 2 at 19:21




$begingroup$
math.stackexchange.com/questions/607829/…
$endgroup$
– lab bhattacharjee
Feb 2 at 19:21




1




1




$begingroup$
math.stackexchange.com/questions/1804639/… and math.stackexchange.com/questions/759810/last-two-digits-problem and math.stackexchange.com/questions/1844558/…
$endgroup$
– lab bhattacharjee
Feb 2 at 19:23




$begingroup$
math.stackexchange.com/questions/1804639/… and math.stackexchange.com/questions/759810/last-two-digits-problem and math.stackexchange.com/questions/1844558/…
$endgroup$
– lab bhattacharjee
Feb 2 at 19:23




1




1




$begingroup$
@lab Thanks for spending the time to gather that list of related questions.
$endgroup$
– Bill Dubuque
Feb 2 at 21:27




$begingroup$
@lab Thanks for spending the time to gather that list of related questions.
$endgroup$
– Bill Dubuque
Feb 2 at 21:27










6 Answers
6






active

oldest

votes


















7












$begingroup$

You can not apply Euler to this directly, since $132$ is not relatively prime to $1000$. Indeed, it is clear that $132^{400}not equiv 1 pmod {1000}$ since this would imply that $2,|,1$.



To solve the problem, work mod $2^3$ and $5^3$ separately. Clearly $132^{1601}equiv 0pmod {2^3}$. Now, $varphi(5^3)=100$ and Euler applies here (since $gcd(132,5)=1$) so we do have $$132^{100}equiv 1 pmod {5^3}implies 132^{1600}equiv 1 pmod {5^3}$$



Thus $$132^{1601}equiv 132equiv 7pmod {5^3}$$



It follows that we want to find a class $npmod {1000}$ such that $$nequiv 0 pmod 8quad &quad nequiv 7 pmod {125}$$ The Chinese Remainder Theorem guarantees a unique solution, which is easily found to be $$boxed {132^{1601}equiv 632pmod {1000}}$$



Note: with numbers as small as these, the CRT can be solved by mental arithmetic (or, at least, by simple calculations). We start with $7$. Clearly that isn't divisible by $8$ so we add $125$ to get $132$. That's divisible by $4$, but not by $8$. Now, adding $125$ to this would give an odd number so add $250$. We now get $382$, still no good. Adding $250$ again gives $632$ and that one works, so we are done.



If you prefer to solve it algorithmically, write the solution as $n=7+125m$ We want to solve $$7+125mequiv 0pmod 8implies 5mequiv 1 pmod 8implies mequiv 5 pmod 8$$ In that way we get $n=7+5times 125=632$.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    You should show the work for CRT instead of pulling the answer out of a hat like magic.
    $endgroup$
    – Bill Dubuque
    Feb 2 at 19:58






  • 1




    $begingroup$
    @BillDubuque It's a matter of simple mental arithmetic...easier to do than to read about. But, sure. I'll edit to include a discussion of the mechanics.
    $endgroup$
    – lulu
    Feb 2 at 20:00






  • 1




    $begingroup$
    Thanks for elaborating. Magic disguised as math always irks me!
    $endgroup$
    – Bill Dubuque
    Feb 2 at 20:07






  • 1




    $begingroup$
    @Alessar This is the same as your prior error. Euler/Fermat can only be used when the base is prime to the modulus.
    $endgroup$
    – lulu
    Feb 4 at 13:46






  • 1




    $begingroup$
    @Alessar Nobody said the modulus had to be prime. Euler tells us that $gcd(a,n)=1implies a^{varphi(n)}equiv 1 pmod n$. This holds for composite $n$ as well as prime. BUT you need the assumption that $gcd (a,n)=1$. That's the mistake you keep making.
    $endgroup$
    – lulu
    Feb 4 at 15:08





















2












$begingroup$

I would do it in a slightly different way: split $132$ as a factor of $1000$ times a factor coprime to $1000$:
$$132=4cdot 33.$$



On the other hand, $;varphi(1000)=varphi(2^3),varphi(5^3)=4,(4cdot 5^2)=400$, so by Euler's theorem
$$33^{1601}equiv 33^{1601bmod400}=33^1.$$



As to $4$, we'll use the Chinese remainder theorem, in the form:




If $a$ and $b$ are coprime, the solutions of the system of congruences $;begin{cases}xequivalphamod a,\ xequiv betamod b,end{cases};$ are given by
$$xequivbeta ua+alpha vbmod ab.$$




Now $4^kequiv 0mod 8$ for all $k>1$, and as $4$ is coprime to $125$, $;4^{1601}equiv 4^{1601bmod varphi(125)}= 4^1 mod 125 $, so that a Bézout's relation between $8$ and $125$:
$$47cdot 8-3cdot 125=1$$
(obtained with the extended Euclidean algorithm) yields the congruence
$$4^{1601}equiv 4cdot47cdot8=1504equiv 504mod 1000, $$
and ultimately
$$132^{1601}=4^{1601}33^{1601}equiv 504cdot 33 =500cdot 32+500+4cdot 33=632mod 1000.$$






share|cite|improve this answer









$endgroup$













  • $begingroup$
    This is a really interesting approach!!! Thanks!!!
    $endgroup$
    – Alessar
    Feb 4 at 11:13



















2












$begingroup$

$2mid 132,1000,$ so Euler $phi$ doesn't apply. Use CRT, or simpler (a minute of mental calculation)



$ 4k^{large 1+100N}!bmod 1000, =, 8 overbrace{left[ dfrac{(4k)^{large 1+color{#c00}{100}N}}8bmod color{#c00}{125}right]}^{qquad large color{#c00}{100 = phi(125)}
} !$ $= 8underbrace{left[ dfrac{k}2bmod 125right]} =!!!!!!begin{align}overbrace{4k!+!500}^{ large 632 {rm if} 4k = 132}!!!& {rm if} 2nmid k \ 4kqquad & {rm if} 2mid k \ phantom{.} end{align} $

by $, abbmod ac, =, a(bbmod c) $ [mod distributive law] $ $ & $ dfrac{k}2equiv dfrac{k!+!125}2,pmod{!!125} ,$ if $ 2nmid k$






share|cite|improve this answer











$endgroup$













  • $begingroup$
    Above we assume $,N>0,$ so $,8mid (4k)^{large 1+100N},,$ and $,(k,5)=1,$ so $,(4k,125)=1,$ enabling Euler $phi,,$ and also that $, k,$ Is already reduced $!bmod 125,,$ i.e. $,0le k < 125 $
    $endgroup$
    – Bill Dubuque
    Feb 2 at 21:41





















1












$begingroup$

Like Find the last two digits of $2^{2156789}$ and Last Two Digits Problem and How to find last two digits of $2^{2016}$,



let us find $P=132^{1601-2}pmod{125}$



Now $132equiv7pmod{125},1601-2equiv-1pmod{phi(125)}$



$implies Pequiv7^{-1}pmod{125}equiv18$



$implies132^2Pequiv18cdot132^2pmod{125cdot132^2}$



$equiv18(100+32)(100+32)pmod{1000}$



$equiv18(200cdot32+32^2)$



$equiv18(400+24)equiv200+432$






share|cite|improve this answer









$endgroup$





















    1












    $begingroup$

    Euler's theorem $a^{phi n} equiv 1 pmod n$ only works if $gcd(a,n) = 1$. Which is not the case with $132, 1000$



    However $1000 = 8*125$



    And CRT theorem does guarantee that if we can solve $132^{1601}pmod 8$ and $132^{1601} pmod {125}$ those two solutions will provide a unique solution to $132^{1601} pmod {1000}$



    ....



    We can't use Euler's Theorem for $132^{1601} pmod 8$, of course, but $132 = 33*4$ so $132^{1601} = 33^{1601}*4^{1601}$ and $8|4^k$ for all $k ge 2$ so $132^{1601} equiv 0 pmod 8$.



    And for $132^{1601} pmod {125}$ we CAN use Euler's theorem.



    As $125|1000$ then $phi{125}|phi{1000}$ so $132^{1601}equiv 132 pmod {125}$. (in fact $phi(125) = 20$ but... why redo work you already did.)



    So we need to find the unique solution $x equiv 0 pmod 8$ and $x equiv 132 pmod {125}$. That is $x = 8m = 132 + 125k$ where $0 le m < 125$ and $0 le k < 8$.



    As $8not mid 132$ we can't have $8mid k$ but as $4|132$ we must have $4|k$.



    In other words $k =4$ and $x equiv 132 + 500equiv 632 pmod {1000}$ is the unique solution.



    .....



    If we want to verify this:



    $132^{1601} = 4^{1601}*33^{1601}$ And $33^{1601} equiv 33pmod{1000}$ so



    $4^{1601}equiv 4pmod {125}$ so $4^{1601} equiv 4,129,254,379,504,629,754,$ or $879 pmod {1000}$. But as $8|4^{1601}$ then $4^{1601}equiv 504equiv 500 + 4 pmod{1000}$



    So $132^{1601} = 4^{1601}33^{1601} equiv (500 + 4)33 pmod{1000}$



    $equiv 500 + 132equiv {1000}$



    ==========



    In general. If you have $a$ and $n$ and $gcd(a,n) = d$ then we can set up $n = n'D$ where $gcd(n',D) = 1$ and $d|D$.



    Then we can solve $a^k equiv xpmod n$ by solving $a^k pmod{n'}$ and $a^k equiv pmod D$.



    $a^k pmod{n'}$ can be solved by Euler's Theorem.



    $a$ can also be written as $a = a'delta$ where $gcd(a',n) = gcd(a', d) = 1$ and $d|delta$ (note that either $delta$ or $D$ equals $d$). And so we can solve $a^kpmod D$ by solving $a^k = a'^k*d^k*(frac {delta}d)^k = MD = Md*frac Ddimplies$



    $a'^k d^{k-1}(frac {delta}d)^k = Mfrac Dd$ . If $D= d$ then will mean $a^kequiv 0 pmod D$. Other wise this means $a'^k d^{k-1} = Mfrac Dd$. Now $frac Dd$ has the same prime factors of $d$ so this will usually mean $a^k equiv 0pmod D$ but might not if the powers of the prime factors of $frac Dd$ are higher than the prime factors of $d^{k-1}$. But if that is the case we can reduce and and solve by Euler's theorem.



    So Euler's theorem in combination with CRT will always allow us to solve these.






    share|cite|improve this answer











    $endgroup$





















      1












      $begingroup$

      $overbrace{132^{large 1+color{#c00}{100}N}}^{large X}!!equiv 132, overbrace{{rm holds} bmod color{#c00}{125}}^{largecolor{#c00}{100 = phi(125)}},$ & $overbrace{!bmod 4}^{large 0^K equiv 0},$ so mod $500,,$ so it's $overbrace{ 132 {rm or} underbrace{132!+!500}_{large rm must be this }!pmod{!1000}}^{large 132 notequiv X {rm by} N>1 ,{Large Rightarrow}, 8 mid 132^{LARGE 2}, mid X!! } $






      share|cite|improve this answer











      $endgroup$














        Your Answer








        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%2f3097662%2fcalculation-of-the-last-three-digits-of-1321601-solving-x-equiv-132160%23new-answer', 'question_page');
        }
        );

        Post as a guest















        Required, but never shown

























        6 Answers
        6






        active

        oldest

        votes








        6 Answers
        6






        active

        oldest

        votes









        active

        oldest

        votes






        active

        oldest

        votes









        7












        $begingroup$

        You can not apply Euler to this directly, since $132$ is not relatively prime to $1000$. Indeed, it is clear that $132^{400}not equiv 1 pmod {1000}$ since this would imply that $2,|,1$.



        To solve the problem, work mod $2^3$ and $5^3$ separately. Clearly $132^{1601}equiv 0pmod {2^3}$. Now, $varphi(5^3)=100$ and Euler applies here (since $gcd(132,5)=1$) so we do have $$132^{100}equiv 1 pmod {5^3}implies 132^{1600}equiv 1 pmod {5^3}$$



        Thus $$132^{1601}equiv 132equiv 7pmod {5^3}$$



        It follows that we want to find a class $npmod {1000}$ such that $$nequiv 0 pmod 8quad &quad nequiv 7 pmod {125}$$ The Chinese Remainder Theorem guarantees a unique solution, which is easily found to be $$boxed {132^{1601}equiv 632pmod {1000}}$$



        Note: with numbers as small as these, the CRT can be solved by mental arithmetic (or, at least, by simple calculations). We start with $7$. Clearly that isn't divisible by $8$ so we add $125$ to get $132$. That's divisible by $4$, but not by $8$. Now, adding $125$ to this would give an odd number so add $250$. We now get $382$, still no good. Adding $250$ again gives $632$ and that one works, so we are done.



        If you prefer to solve it algorithmically, write the solution as $n=7+125m$ We want to solve $$7+125mequiv 0pmod 8implies 5mequiv 1 pmod 8implies mequiv 5 pmod 8$$ In that way we get $n=7+5times 125=632$.






        share|cite|improve this answer











        $endgroup$













        • $begingroup$
          You should show the work for CRT instead of pulling the answer out of a hat like magic.
          $endgroup$
          – Bill Dubuque
          Feb 2 at 19:58






        • 1




          $begingroup$
          @BillDubuque It's a matter of simple mental arithmetic...easier to do than to read about. But, sure. I'll edit to include a discussion of the mechanics.
          $endgroup$
          – lulu
          Feb 2 at 20:00






        • 1




          $begingroup$
          Thanks for elaborating. Magic disguised as math always irks me!
          $endgroup$
          – Bill Dubuque
          Feb 2 at 20:07






        • 1




          $begingroup$
          @Alessar This is the same as your prior error. Euler/Fermat can only be used when the base is prime to the modulus.
          $endgroup$
          – lulu
          Feb 4 at 13:46






        • 1




          $begingroup$
          @Alessar Nobody said the modulus had to be prime. Euler tells us that $gcd(a,n)=1implies a^{varphi(n)}equiv 1 pmod n$. This holds for composite $n$ as well as prime. BUT you need the assumption that $gcd (a,n)=1$. That's the mistake you keep making.
          $endgroup$
          – lulu
          Feb 4 at 15:08


















        7












        $begingroup$

        You can not apply Euler to this directly, since $132$ is not relatively prime to $1000$. Indeed, it is clear that $132^{400}not equiv 1 pmod {1000}$ since this would imply that $2,|,1$.



        To solve the problem, work mod $2^3$ and $5^3$ separately. Clearly $132^{1601}equiv 0pmod {2^3}$. Now, $varphi(5^3)=100$ and Euler applies here (since $gcd(132,5)=1$) so we do have $$132^{100}equiv 1 pmod {5^3}implies 132^{1600}equiv 1 pmod {5^3}$$



        Thus $$132^{1601}equiv 132equiv 7pmod {5^3}$$



        It follows that we want to find a class $npmod {1000}$ such that $$nequiv 0 pmod 8quad &quad nequiv 7 pmod {125}$$ The Chinese Remainder Theorem guarantees a unique solution, which is easily found to be $$boxed {132^{1601}equiv 632pmod {1000}}$$



        Note: with numbers as small as these, the CRT can be solved by mental arithmetic (or, at least, by simple calculations). We start with $7$. Clearly that isn't divisible by $8$ so we add $125$ to get $132$. That's divisible by $4$, but not by $8$. Now, adding $125$ to this would give an odd number so add $250$. We now get $382$, still no good. Adding $250$ again gives $632$ and that one works, so we are done.



        If you prefer to solve it algorithmically, write the solution as $n=7+125m$ We want to solve $$7+125mequiv 0pmod 8implies 5mequiv 1 pmod 8implies mequiv 5 pmod 8$$ In that way we get $n=7+5times 125=632$.






        share|cite|improve this answer











        $endgroup$













        • $begingroup$
          You should show the work for CRT instead of pulling the answer out of a hat like magic.
          $endgroup$
          – Bill Dubuque
          Feb 2 at 19:58






        • 1




          $begingroup$
          @BillDubuque It's a matter of simple mental arithmetic...easier to do than to read about. But, sure. I'll edit to include a discussion of the mechanics.
          $endgroup$
          – lulu
          Feb 2 at 20:00






        • 1




          $begingroup$
          Thanks for elaborating. Magic disguised as math always irks me!
          $endgroup$
          – Bill Dubuque
          Feb 2 at 20:07






        • 1




          $begingroup$
          @Alessar This is the same as your prior error. Euler/Fermat can only be used when the base is prime to the modulus.
          $endgroup$
          – lulu
          Feb 4 at 13:46






        • 1




          $begingroup$
          @Alessar Nobody said the modulus had to be prime. Euler tells us that $gcd(a,n)=1implies a^{varphi(n)}equiv 1 pmod n$. This holds for composite $n$ as well as prime. BUT you need the assumption that $gcd (a,n)=1$. That's the mistake you keep making.
          $endgroup$
          – lulu
          Feb 4 at 15:08
















        7












        7








        7





        $begingroup$

        You can not apply Euler to this directly, since $132$ is not relatively prime to $1000$. Indeed, it is clear that $132^{400}not equiv 1 pmod {1000}$ since this would imply that $2,|,1$.



        To solve the problem, work mod $2^3$ and $5^3$ separately. Clearly $132^{1601}equiv 0pmod {2^3}$. Now, $varphi(5^3)=100$ and Euler applies here (since $gcd(132,5)=1$) so we do have $$132^{100}equiv 1 pmod {5^3}implies 132^{1600}equiv 1 pmod {5^3}$$



        Thus $$132^{1601}equiv 132equiv 7pmod {5^3}$$



        It follows that we want to find a class $npmod {1000}$ such that $$nequiv 0 pmod 8quad &quad nequiv 7 pmod {125}$$ The Chinese Remainder Theorem guarantees a unique solution, which is easily found to be $$boxed {132^{1601}equiv 632pmod {1000}}$$



        Note: with numbers as small as these, the CRT can be solved by mental arithmetic (or, at least, by simple calculations). We start with $7$. Clearly that isn't divisible by $8$ so we add $125$ to get $132$. That's divisible by $4$, but not by $8$. Now, adding $125$ to this would give an odd number so add $250$. We now get $382$, still no good. Adding $250$ again gives $632$ and that one works, so we are done.



        If you prefer to solve it algorithmically, write the solution as $n=7+125m$ We want to solve $$7+125mequiv 0pmod 8implies 5mequiv 1 pmod 8implies mequiv 5 pmod 8$$ In that way we get $n=7+5times 125=632$.






        share|cite|improve this answer











        $endgroup$



        You can not apply Euler to this directly, since $132$ is not relatively prime to $1000$. Indeed, it is clear that $132^{400}not equiv 1 pmod {1000}$ since this would imply that $2,|,1$.



        To solve the problem, work mod $2^3$ and $5^3$ separately. Clearly $132^{1601}equiv 0pmod {2^3}$. Now, $varphi(5^3)=100$ and Euler applies here (since $gcd(132,5)=1$) so we do have $$132^{100}equiv 1 pmod {5^3}implies 132^{1600}equiv 1 pmod {5^3}$$



        Thus $$132^{1601}equiv 132equiv 7pmod {5^3}$$



        It follows that we want to find a class $npmod {1000}$ such that $$nequiv 0 pmod 8quad &quad nequiv 7 pmod {125}$$ The Chinese Remainder Theorem guarantees a unique solution, which is easily found to be $$boxed {132^{1601}equiv 632pmod {1000}}$$



        Note: with numbers as small as these, the CRT can be solved by mental arithmetic (or, at least, by simple calculations). We start with $7$. Clearly that isn't divisible by $8$ so we add $125$ to get $132$. That's divisible by $4$, but not by $8$. Now, adding $125$ to this would give an odd number so add $250$. We now get $382$, still no good. Adding $250$ again gives $632$ and that one works, so we are done.



        If you prefer to solve it algorithmically, write the solution as $n=7+125m$ We want to solve $$7+125mequiv 0pmod 8implies 5mequiv 1 pmod 8implies mequiv 5 pmod 8$$ In that way we get $n=7+5times 125=632$.







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Feb 2 at 20:10

























        answered Feb 2 at 19:19









        lulululu

        43.6k25081




        43.6k25081












        • $begingroup$
          You should show the work for CRT instead of pulling the answer out of a hat like magic.
          $endgroup$
          – Bill Dubuque
          Feb 2 at 19:58






        • 1




          $begingroup$
          @BillDubuque It's a matter of simple mental arithmetic...easier to do than to read about. But, sure. I'll edit to include a discussion of the mechanics.
          $endgroup$
          – lulu
          Feb 2 at 20:00






        • 1




          $begingroup$
          Thanks for elaborating. Magic disguised as math always irks me!
          $endgroup$
          – Bill Dubuque
          Feb 2 at 20:07






        • 1




          $begingroup$
          @Alessar This is the same as your prior error. Euler/Fermat can only be used when the base is prime to the modulus.
          $endgroup$
          – lulu
          Feb 4 at 13:46






        • 1




          $begingroup$
          @Alessar Nobody said the modulus had to be prime. Euler tells us that $gcd(a,n)=1implies a^{varphi(n)}equiv 1 pmod n$. This holds for composite $n$ as well as prime. BUT you need the assumption that $gcd (a,n)=1$. That's the mistake you keep making.
          $endgroup$
          – lulu
          Feb 4 at 15:08




















        • $begingroup$
          You should show the work for CRT instead of pulling the answer out of a hat like magic.
          $endgroup$
          – Bill Dubuque
          Feb 2 at 19:58






        • 1




          $begingroup$
          @BillDubuque It's a matter of simple mental arithmetic...easier to do than to read about. But, sure. I'll edit to include a discussion of the mechanics.
          $endgroup$
          – lulu
          Feb 2 at 20:00






        • 1




          $begingroup$
          Thanks for elaborating. Magic disguised as math always irks me!
          $endgroup$
          – Bill Dubuque
          Feb 2 at 20:07






        • 1




          $begingroup$
          @Alessar This is the same as your prior error. Euler/Fermat can only be used when the base is prime to the modulus.
          $endgroup$
          – lulu
          Feb 4 at 13:46






        • 1




          $begingroup$
          @Alessar Nobody said the modulus had to be prime. Euler tells us that $gcd(a,n)=1implies a^{varphi(n)}equiv 1 pmod n$. This holds for composite $n$ as well as prime. BUT you need the assumption that $gcd (a,n)=1$. That's the mistake you keep making.
          $endgroup$
          – lulu
          Feb 4 at 15:08


















        $begingroup$
        You should show the work for CRT instead of pulling the answer out of a hat like magic.
        $endgroup$
        – Bill Dubuque
        Feb 2 at 19:58




        $begingroup$
        You should show the work for CRT instead of pulling the answer out of a hat like magic.
        $endgroup$
        – Bill Dubuque
        Feb 2 at 19:58




        1




        1




        $begingroup$
        @BillDubuque It's a matter of simple mental arithmetic...easier to do than to read about. But, sure. I'll edit to include a discussion of the mechanics.
        $endgroup$
        – lulu
        Feb 2 at 20:00




        $begingroup$
        @BillDubuque It's a matter of simple mental arithmetic...easier to do than to read about. But, sure. I'll edit to include a discussion of the mechanics.
        $endgroup$
        – lulu
        Feb 2 at 20:00




        1




        1




        $begingroup$
        Thanks for elaborating. Magic disguised as math always irks me!
        $endgroup$
        – Bill Dubuque
        Feb 2 at 20:07




        $begingroup$
        Thanks for elaborating. Magic disguised as math always irks me!
        $endgroup$
        – Bill Dubuque
        Feb 2 at 20:07




        1




        1




        $begingroup$
        @Alessar This is the same as your prior error. Euler/Fermat can only be used when the base is prime to the modulus.
        $endgroup$
        – lulu
        Feb 4 at 13:46




        $begingroup$
        @Alessar This is the same as your prior error. Euler/Fermat can only be used when the base is prime to the modulus.
        $endgroup$
        – lulu
        Feb 4 at 13:46




        1




        1




        $begingroup$
        @Alessar Nobody said the modulus had to be prime. Euler tells us that $gcd(a,n)=1implies a^{varphi(n)}equiv 1 pmod n$. This holds for composite $n$ as well as prime. BUT you need the assumption that $gcd (a,n)=1$. That's the mistake you keep making.
        $endgroup$
        – lulu
        Feb 4 at 15:08






        $begingroup$
        @Alessar Nobody said the modulus had to be prime. Euler tells us that $gcd(a,n)=1implies a^{varphi(n)}equiv 1 pmod n$. This holds for composite $n$ as well as prime. BUT you need the assumption that $gcd (a,n)=1$. That's the mistake you keep making.
        $endgroup$
        – lulu
        Feb 4 at 15:08













        2












        $begingroup$

        I would do it in a slightly different way: split $132$ as a factor of $1000$ times a factor coprime to $1000$:
        $$132=4cdot 33.$$



        On the other hand, $;varphi(1000)=varphi(2^3),varphi(5^3)=4,(4cdot 5^2)=400$, so by Euler's theorem
        $$33^{1601}equiv 33^{1601bmod400}=33^1.$$



        As to $4$, we'll use the Chinese remainder theorem, in the form:




        If $a$ and $b$ are coprime, the solutions of the system of congruences $;begin{cases}xequivalphamod a,\ xequiv betamod b,end{cases};$ are given by
        $$xequivbeta ua+alpha vbmod ab.$$




        Now $4^kequiv 0mod 8$ for all $k>1$, and as $4$ is coprime to $125$, $;4^{1601}equiv 4^{1601bmod varphi(125)}= 4^1 mod 125 $, so that a Bézout's relation between $8$ and $125$:
        $$47cdot 8-3cdot 125=1$$
        (obtained with the extended Euclidean algorithm) yields the congruence
        $$4^{1601}equiv 4cdot47cdot8=1504equiv 504mod 1000, $$
        and ultimately
        $$132^{1601}=4^{1601}33^{1601}equiv 504cdot 33 =500cdot 32+500+4cdot 33=632mod 1000.$$






        share|cite|improve this answer









        $endgroup$













        • $begingroup$
          This is a really interesting approach!!! Thanks!!!
          $endgroup$
          – Alessar
          Feb 4 at 11:13
















        2












        $begingroup$

        I would do it in a slightly different way: split $132$ as a factor of $1000$ times a factor coprime to $1000$:
        $$132=4cdot 33.$$



        On the other hand, $;varphi(1000)=varphi(2^3),varphi(5^3)=4,(4cdot 5^2)=400$, so by Euler's theorem
        $$33^{1601}equiv 33^{1601bmod400}=33^1.$$



        As to $4$, we'll use the Chinese remainder theorem, in the form:




        If $a$ and $b$ are coprime, the solutions of the system of congruences $;begin{cases}xequivalphamod a,\ xequiv betamod b,end{cases};$ are given by
        $$xequivbeta ua+alpha vbmod ab.$$




        Now $4^kequiv 0mod 8$ for all $k>1$, and as $4$ is coprime to $125$, $;4^{1601}equiv 4^{1601bmod varphi(125)}= 4^1 mod 125 $, so that a Bézout's relation between $8$ and $125$:
        $$47cdot 8-3cdot 125=1$$
        (obtained with the extended Euclidean algorithm) yields the congruence
        $$4^{1601}equiv 4cdot47cdot8=1504equiv 504mod 1000, $$
        and ultimately
        $$132^{1601}=4^{1601}33^{1601}equiv 504cdot 33 =500cdot 32+500+4cdot 33=632mod 1000.$$






        share|cite|improve this answer









        $endgroup$













        • $begingroup$
          This is a really interesting approach!!! Thanks!!!
          $endgroup$
          – Alessar
          Feb 4 at 11:13














        2












        2








        2





        $begingroup$

        I would do it in a slightly different way: split $132$ as a factor of $1000$ times a factor coprime to $1000$:
        $$132=4cdot 33.$$



        On the other hand, $;varphi(1000)=varphi(2^3),varphi(5^3)=4,(4cdot 5^2)=400$, so by Euler's theorem
        $$33^{1601}equiv 33^{1601bmod400}=33^1.$$



        As to $4$, we'll use the Chinese remainder theorem, in the form:




        If $a$ and $b$ are coprime, the solutions of the system of congruences $;begin{cases}xequivalphamod a,\ xequiv betamod b,end{cases};$ are given by
        $$xequivbeta ua+alpha vbmod ab.$$




        Now $4^kequiv 0mod 8$ for all $k>1$, and as $4$ is coprime to $125$, $;4^{1601}equiv 4^{1601bmod varphi(125)}= 4^1 mod 125 $, so that a Bézout's relation between $8$ and $125$:
        $$47cdot 8-3cdot 125=1$$
        (obtained with the extended Euclidean algorithm) yields the congruence
        $$4^{1601}equiv 4cdot47cdot8=1504equiv 504mod 1000, $$
        and ultimately
        $$132^{1601}=4^{1601}33^{1601}equiv 504cdot 33 =500cdot 32+500+4cdot 33=632mod 1000.$$






        share|cite|improve this answer









        $endgroup$



        I would do it in a slightly different way: split $132$ as a factor of $1000$ times a factor coprime to $1000$:
        $$132=4cdot 33.$$



        On the other hand, $;varphi(1000)=varphi(2^3),varphi(5^3)=4,(4cdot 5^2)=400$, so by Euler's theorem
        $$33^{1601}equiv 33^{1601bmod400}=33^1.$$



        As to $4$, we'll use the Chinese remainder theorem, in the form:




        If $a$ and $b$ are coprime, the solutions of the system of congruences $;begin{cases}xequivalphamod a,\ xequiv betamod b,end{cases};$ are given by
        $$xequivbeta ua+alpha vbmod ab.$$




        Now $4^kequiv 0mod 8$ for all $k>1$, and as $4$ is coprime to $125$, $;4^{1601}equiv 4^{1601bmod varphi(125)}= 4^1 mod 125 $, so that a Bézout's relation between $8$ and $125$:
        $$47cdot 8-3cdot 125=1$$
        (obtained with the extended Euclidean algorithm) yields the congruence
        $$4^{1601}equiv 4cdot47cdot8=1504equiv 504mod 1000, $$
        and ultimately
        $$132^{1601}=4^{1601}33^{1601}equiv 504cdot 33 =500cdot 32+500+4cdot 33=632mod 1000.$$







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered Feb 2 at 19:52









        BernardBernard

        124k741117




        124k741117












        • $begingroup$
          This is a really interesting approach!!! Thanks!!!
          $endgroup$
          – Alessar
          Feb 4 at 11:13


















        • $begingroup$
          This is a really interesting approach!!! Thanks!!!
          $endgroup$
          – Alessar
          Feb 4 at 11:13
















        $begingroup$
        This is a really interesting approach!!! Thanks!!!
        $endgroup$
        – Alessar
        Feb 4 at 11:13




        $begingroup$
        This is a really interesting approach!!! Thanks!!!
        $endgroup$
        – Alessar
        Feb 4 at 11:13











        2












        $begingroup$

        $2mid 132,1000,$ so Euler $phi$ doesn't apply. Use CRT, or simpler (a minute of mental calculation)



        $ 4k^{large 1+100N}!bmod 1000, =, 8 overbrace{left[ dfrac{(4k)^{large 1+color{#c00}{100}N}}8bmod color{#c00}{125}right]}^{qquad large color{#c00}{100 = phi(125)}
        } !$         $= 8underbrace{left[ dfrac{k}2bmod 125right]} =!!!!!!begin{align}overbrace{4k!+!500}^{ large 632 {rm if} 4k = 132}!!!& {rm if} 2nmid k \ 4kqquad & {rm if} 2mid k \ phantom{.} end{align} $

        by $, abbmod ac, =, a(bbmod c) $ [mod distributive law] $ $ & $ dfrac{k}2equiv dfrac{k!+!125}2,pmod{!!125} ,$ if $ 2nmid k$






        share|cite|improve this answer











        $endgroup$













        • $begingroup$
          Above we assume $,N>0,$ so $,8mid (4k)^{large 1+100N},,$ and $,(k,5)=1,$ so $,(4k,125)=1,$ enabling Euler $phi,,$ and also that $, k,$ Is already reduced $!bmod 125,,$ i.e. $,0le k < 125 $
          $endgroup$
          – Bill Dubuque
          Feb 2 at 21:41


















        2












        $begingroup$

        $2mid 132,1000,$ so Euler $phi$ doesn't apply. Use CRT, or simpler (a minute of mental calculation)



        $ 4k^{large 1+100N}!bmod 1000, =, 8 overbrace{left[ dfrac{(4k)^{large 1+color{#c00}{100}N}}8bmod color{#c00}{125}right]}^{qquad large color{#c00}{100 = phi(125)}
        } !$         $= 8underbrace{left[ dfrac{k}2bmod 125right]} =!!!!!!begin{align}overbrace{4k!+!500}^{ large 632 {rm if} 4k = 132}!!!& {rm if} 2nmid k \ 4kqquad & {rm if} 2mid k \ phantom{.} end{align} $

        by $, abbmod ac, =, a(bbmod c) $ [mod distributive law] $ $ & $ dfrac{k}2equiv dfrac{k!+!125}2,pmod{!!125} ,$ if $ 2nmid k$






        share|cite|improve this answer











        $endgroup$













        • $begingroup$
          Above we assume $,N>0,$ so $,8mid (4k)^{large 1+100N},,$ and $,(k,5)=1,$ so $,(4k,125)=1,$ enabling Euler $phi,,$ and also that $, k,$ Is already reduced $!bmod 125,,$ i.e. $,0le k < 125 $
          $endgroup$
          – Bill Dubuque
          Feb 2 at 21:41
















        2












        2








        2





        $begingroup$

        $2mid 132,1000,$ so Euler $phi$ doesn't apply. Use CRT, or simpler (a minute of mental calculation)



        $ 4k^{large 1+100N}!bmod 1000, =, 8 overbrace{left[ dfrac{(4k)^{large 1+color{#c00}{100}N}}8bmod color{#c00}{125}right]}^{qquad large color{#c00}{100 = phi(125)}
        } !$         $= 8underbrace{left[ dfrac{k}2bmod 125right]} =!!!!!!begin{align}overbrace{4k!+!500}^{ large 632 {rm if} 4k = 132}!!!& {rm if} 2nmid k \ 4kqquad & {rm if} 2mid k \ phantom{.} end{align} $

        by $, abbmod ac, =, a(bbmod c) $ [mod distributive law] $ $ & $ dfrac{k}2equiv dfrac{k!+!125}2,pmod{!!125} ,$ if $ 2nmid k$






        share|cite|improve this answer











        $endgroup$



        $2mid 132,1000,$ so Euler $phi$ doesn't apply. Use CRT, or simpler (a minute of mental calculation)



        $ 4k^{large 1+100N}!bmod 1000, =, 8 overbrace{left[ dfrac{(4k)^{large 1+color{#c00}{100}N}}8bmod color{#c00}{125}right]}^{qquad large color{#c00}{100 = phi(125)}
        } !$         $= 8underbrace{left[ dfrac{k}2bmod 125right]} =!!!!!!begin{align}overbrace{4k!+!500}^{ large 632 {rm if} 4k = 132}!!!& {rm if} 2nmid k \ 4kqquad & {rm if} 2mid k \ phantom{.} end{align} $

        by $, abbmod ac, =, a(bbmod c) $ [mod distributive law] $ $ & $ dfrac{k}2equiv dfrac{k!+!125}2,pmod{!!125} ,$ if $ 2nmid k$







        share|cite|improve this answer














        share|cite|improve this answer



        share|cite|improve this answer








        edited Feb 2 at 20:40

























        answered Feb 2 at 19:37









        Bill DubuqueBill Dubuque

        214k29197658




        214k29197658












        • $begingroup$
          Above we assume $,N>0,$ so $,8mid (4k)^{large 1+100N},,$ and $,(k,5)=1,$ so $,(4k,125)=1,$ enabling Euler $phi,,$ and also that $, k,$ Is already reduced $!bmod 125,,$ i.e. $,0le k < 125 $
          $endgroup$
          – Bill Dubuque
          Feb 2 at 21:41




















        • $begingroup$
          Above we assume $,N>0,$ so $,8mid (4k)^{large 1+100N},,$ and $,(k,5)=1,$ so $,(4k,125)=1,$ enabling Euler $phi,,$ and also that $, k,$ Is already reduced $!bmod 125,,$ i.e. $,0le k < 125 $
          $endgroup$
          – Bill Dubuque
          Feb 2 at 21:41


















        $begingroup$
        Above we assume $,N>0,$ so $,8mid (4k)^{large 1+100N},,$ and $,(k,5)=1,$ so $,(4k,125)=1,$ enabling Euler $phi,,$ and also that $, k,$ Is already reduced $!bmod 125,,$ i.e. $,0le k < 125 $
        $endgroup$
        – Bill Dubuque
        Feb 2 at 21:41






        $begingroup$
        Above we assume $,N>0,$ so $,8mid (4k)^{large 1+100N},,$ and $,(k,5)=1,$ so $,(4k,125)=1,$ enabling Euler $phi,,$ and also that $, k,$ Is already reduced $!bmod 125,,$ i.e. $,0le k < 125 $
        $endgroup$
        – Bill Dubuque
        Feb 2 at 21:41













        1












        $begingroup$

        Like Find the last two digits of $2^{2156789}$ and Last Two Digits Problem and How to find last two digits of $2^{2016}$,



        let us find $P=132^{1601-2}pmod{125}$



        Now $132equiv7pmod{125},1601-2equiv-1pmod{phi(125)}$



        $implies Pequiv7^{-1}pmod{125}equiv18$



        $implies132^2Pequiv18cdot132^2pmod{125cdot132^2}$



        $equiv18(100+32)(100+32)pmod{1000}$



        $equiv18(200cdot32+32^2)$



        $equiv18(400+24)equiv200+432$






        share|cite|improve this answer









        $endgroup$


















          1












          $begingroup$

          Like Find the last two digits of $2^{2156789}$ and Last Two Digits Problem and How to find last two digits of $2^{2016}$,



          let us find $P=132^{1601-2}pmod{125}$



          Now $132equiv7pmod{125},1601-2equiv-1pmod{phi(125)}$



          $implies Pequiv7^{-1}pmod{125}equiv18$



          $implies132^2Pequiv18cdot132^2pmod{125cdot132^2}$



          $equiv18(100+32)(100+32)pmod{1000}$



          $equiv18(200cdot32+32^2)$



          $equiv18(400+24)equiv200+432$






          share|cite|improve this answer









          $endgroup$
















            1












            1








            1





            $begingroup$

            Like Find the last two digits of $2^{2156789}$ and Last Two Digits Problem and How to find last two digits of $2^{2016}$,



            let us find $P=132^{1601-2}pmod{125}$



            Now $132equiv7pmod{125},1601-2equiv-1pmod{phi(125)}$



            $implies Pequiv7^{-1}pmod{125}equiv18$



            $implies132^2Pequiv18cdot132^2pmod{125cdot132^2}$



            $equiv18(100+32)(100+32)pmod{1000}$



            $equiv18(200cdot32+32^2)$



            $equiv18(400+24)equiv200+432$






            share|cite|improve this answer









            $endgroup$



            Like Find the last two digits of $2^{2156789}$ and Last Two Digits Problem and How to find last two digits of $2^{2016}$,



            let us find $P=132^{1601-2}pmod{125}$



            Now $132equiv7pmod{125},1601-2equiv-1pmod{phi(125)}$



            $implies Pequiv7^{-1}pmod{125}equiv18$



            $implies132^2Pequiv18cdot132^2pmod{125cdot132^2}$



            $equiv18(100+32)(100+32)pmod{1000}$



            $equiv18(200cdot32+32^2)$



            $equiv18(400+24)equiv200+432$







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered Feb 2 at 19:35









            lab bhattacharjeelab bhattacharjee

            229k15159279




            229k15159279























                1












                $begingroup$

                Euler's theorem $a^{phi n} equiv 1 pmod n$ only works if $gcd(a,n) = 1$. Which is not the case with $132, 1000$



                However $1000 = 8*125$



                And CRT theorem does guarantee that if we can solve $132^{1601}pmod 8$ and $132^{1601} pmod {125}$ those two solutions will provide a unique solution to $132^{1601} pmod {1000}$



                ....



                We can't use Euler's Theorem for $132^{1601} pmod 8$, of course, but $132 = 33*4$ so $132^{1601} = 33^{1601}*4^{1601}$ and $8|4^k$ for all $k ge 2$ so $132^{1601} equiv 0 pmod 8$.



                And for $132^{1601} pmod {125}$ we CAN use Euler's theorem.



                As $125|1000$ then $phi{125}|phi{1000}$ so $132^{1601}equiv 132 pmod {125}$. (in fact $phi(125) = 20$ but... why redo work you already did.)



                So we need to find the unique solution $x equiv 0 pmod 8$ and $x equiv 132 pmod {125}$. That is $x = 8m = 132 + 125k$ where $0 le m < 125$ and $0 le k < 8$.



                As $8not mid 132$ we can't have $8mid k$ but as $4|132$ we must have $4|k$.



                In other words $k =4$ and $x equiv 132 + 500equiv 632 pmod {1000}$ is the unique solution.



                .....



                If we want to verify this:



                $132^{1601} = 4^{1601}*33^{1601}$ And $33^{1601} equiv 33pmod{1000}$ so



                $4^{1601}equiv 4pmod {125}$ so $4^{1601} equiv 4,129,254,379,504,629,754,$ or $879 pmod {1000}$. But as $8|4^{1601}$ then $4^{1601}equiv 504equiv 500 + 4 pmod{1000}$



                So $132^{1601} = 4^{1601}33^{1601} equiv (500 + 4)33 pmod{1000}$



                $equiv 500 + 132equiv {1000}$



                ==========



                In general. If you have $a$ and $n$ and $gcd(a,n) = d$ then we can set up $n = n'D$ where $gcd(n',D) = 1$ and $d|D$.



                Then we can solve $a^k equiv xpmod n$ by solving $a^k pmod{n'}$ and $a^k equiv pmod D$.



                $a^k pmod{n'}$ can be solved by Euler's Theorem.



                $a$ can also be written as $a = a'delta$ where $gcd(a',n) = gcd(a', d) = 1$ and $d|delta$ (note that either $delta$ or $D$ equals $d$). And so we can solve $a^kpmod D$ by solving $a^k = a'^k*d^k*(frac {delta}d)^k = MD = Md*frac Ddimplies$



                $a'^k d^{k-1}(frac {delta}d)^k = Mfrac Dd$ . If $D= d$ then will mean $a^kequiv 0 pmod D$. Other wise this means $a'^k d^{k-1} = Mfrac Dd$. Now $frac Dd$ has the same prime factors of $d$ so this will usually mean $a^k equiv 0pmod D$ but might not if the powers of the prime factors of $frac Dd$ are higher than the prime factors of $d^{k-1}$. But if that is the case we can reduce and and solve by Euler's theorem.



                So Euler's theorem in combination with CRT will always allow us to solve these.






                share|cite|improve this answer











                $endgroup$


















                  1












                  $begingroup$

                  Euler's theorem $a^{phi n} equiv 1 pmod n$ only works if $gcd(a,n) = 1$. Which is not the case with $132, 1000$



                  However $1000 = 8*125$



                  And CRT theorem does guarantee that if we can solve $132^{1601}pmod 8$ and $132^{1601} pmod {125}$ those two solutions will provide a unique solution to $132^{1601} pmod {1000}$



                  ....



                  We can't use Euler's Theorem for $132^{1601} pmod 8$, of course, but $132 = 33*4$ so $132^{1601} = 33^{1601}*4^{1601}$ and $8|4^k$ for all $k ge 2$ so $132^{1601} equiv 0 pmod 8$.



                  And for $132^{1601} pmod {125}$ we CAN use Euler's theorem.



                  As $125|1000$ then $phi{125}|phi{1000}$ so $132^{1601}equiv 132 pmod {125}$. (in fact $phi(125) = 20$ but... why redo work you already did.)



                  So we need to find the unique solution $x equiv 0 pmod 8$ and $x equiv 132 pmod {125}$. That is $x = 8m = 132 + 125k$ where $0 le m < 125$ and $0 le k < 8$.



                  As $8not mid 132$ we can't have $8mid k$ but as $4|132$ we must have $4|k$.



                  In other words $k =4$ and $x equiv 132 + 500equiv 632 pmod {1000}$ is the unique solution.



                  .....



                  If we want to verify this:



                  $132^{1601} = 4^{1601}*33^{1601}$ And $33^{1601} equiv 33pmod{1000}$ so



                  $4^{1601}equiv 4pmod {125}$ so $4^{1601} equiv 4,129,254,379,504,629,754,$ or $879 pmod {1000}$. But as $8|4^{1601}$ then $4^{1601}equiv 504equiv 500 + 4 pmod{1000}$



                  So $132^{1601} = 4^{1601}33^{1601} equiv (500 + 4)33 pmod{1000}$



                  $equiv 500 + 132equiv {1000}$



                  ==========



                  In general. If you have $a$ and $n$ and $gcd(a,n) = d$ then we can set up $n = n'D$ where $gcd(n',D) = 1$ and $d|D$.



                  Then we can solve $a^k equiv xpmod n$ by solving $a^k pmod{n'}$ and $a^k equiv pmod D$.



                  $a^k pmod{n'}$ can be solved by Euler's Theorem.



                  $a$ can also be written as $a = a'delta$ where $gcd(a',n) = gcd(a', d) = 1$ and $d|delta$ (note that either $delta$ or $D$ equals $d$). And so we can solve $a^kpmod D$ by solving $a^k = a'^k*d^k*(frac {delta}d)^k = MD = Md*frac Ddimplies$



                  $a'^k d^{k-1}(frac {delta}d)^k = Mfrac Dd$ . If $D= d$ then will mean $a^kequiv 0 pmod D$. Other wise this means $a'^k d^{k-1} = Mfrac Dd$. Now $frac Dd$ has the same prime factors of $d$ so this will usually mean $a^k equiv 0pmod D$ but might not if the powers of the prime factors of $frac Dd$ are higher than the prime factors of $d^{k-1}$. But if that is the case we can reduce and and solve by Euler's theorem.



                  So Euler's theorem in combination with CRT will always allow us to solve these.






                  share|cite|improve this answer











                  $endgroup$
















                    1












                    1








                    1





                    $begingroup$

                    Euler's theorem $a^{phi n} equiv 1 pmod n$ only works if $gcd(a,n) = 1$. Which is not the case with $132, 1000$



                    However $1000 = 8*125$



                    And CRT theorem does guarantee that if we can solve $132^{1601}pmod 8$ and $132^{1601} pmod {125}$ those two solutions will provide a unique solution to $132^{1601} pmod {1000}$



                    ....



                    We can't use Euler's Theorem for $132^{1601} pmod 8$, of course, but $132 = 33*4$ so $132^{1601} = 33^{1601}*4^{1601}$ and $8|4^k$ for all $k ge 2$ so $132^{1601} equiv 0 pmod 8$.



                    And for $132^{1601} pmod {125}$ we CAN use Euler's theorem.



                    As $125|1000$ then $phi{125}|phi{1000}$ so $132^{1601}equiv 132 pmod {125}$. (in fact $phi(125) = 20$ but... why redo work you already did.)



                    So we need to find the unique solution $x equiv 0 pmod 8$ and $x equiv 132 pmod {125}$. That is $x = 8m = 132 + 125k$ where $0 le m < 125$ and $0 le k < 8$.



                    As $8not mid 132$ we can't have $8mid k$ but as $4|132$ we must have $4|k$.



                    In other words $k =4$ and $x equiv 132 + 500equiv 632 pmod {1000}$ is the unique solution.



                    .....



                    If we want to verify this:



                    $132^{1601} = 4^{1601}*33^{1601}$ And $33^{1601} equiv 33pmod{1000}$ so



                    $4^{1601}equiv 4pmod {125}$ so $4^{1601} equiv 4,129,254,379,504,629,754,$ or $879 pmod {1000}$. But as $8|4^{1601}$ then $4^{1601}equiv 504equiv 500 + 4 pmod{1000}$



                    So $132^{1601} = 4^{1601}33^{1601} equiv (500 + 4)33 pmod{1000}$



                    $equiv 500 + 132equiv {1000}$



                    ==========



                    In general. If you have $a$ and $n$ and $gcd(a,n) = d$ then we can set up $n = n'D$ where $gcd(n',D) = 1$ and $d|D$.



                    Then we can solve $a^k equiv xpmod n$ by solving $a^k pmod{n'}$ and $a^k equiv pmod D$.



                    $a^k pmod{n'}$ can be solved by Euler's Theorem.



                    $a$ can also be written as $a = a'delta$ where $gcd(a',n) = gcd(a', d) = 1$ and $d|delta$ (note that either $delta$ or $D$ equals $d$). And so we can solve $a^kpmod D$ by solving $a^k = a'^k*d^k*(frac {delta}d)^k = MD = Md*frac Ddimplies$



                    $a'^k d^{k-1}(frac {delta}d)^k = Mfrac Dd$ . If $D= d$ then will mean $a^kequiv 0 pmod D$. Other wise this means $a'^k d^{k-1} = Mfrac Dd$. Now $frac Dd$ has the same prime factors of $d$ so this will usually mean $a^k equiv 0pmod D$ but might not if the powers of the prime factors of $frac Dd$ are higher than the prime factors of $d^{k-1}$. But if that is the case we can reduce and and solve by Euler's theorem.



                    So Euler's theorem in combination with CRT will always allow us to solve these.






                    share|cite|improve this answer











                    $endgroup$



                    Euler's theorem $a^{phi n} equiv 1 pmod n$ only works if $gcd(a,n) = 1$. Which is not the case with $132, 1000$



                    However $1000 = 8*125$



                    And CRT theorem does guarantee that if we can solve $132^{1601}pmod 8$ and $132^{1601} pmod {125}$ those two solutions will provide a unique solution to $132^{1601} pmod {1000}$



                    ....



                    We can't use Euler's Theorem for $132^{1601} pmod 8$, of course, but $132 = 33*4$ so $132^{1601} = 33^{1601}*4^{1601}$ and $8|4^k$ for all $k ge 2$ so $132^{1601} equiv 0 pmod 8$.



                    And for $132^{1601} pmod {125}$ we CAN use Euler's theorem.



                    As $125|1000$ then $phi{125}|phi{1000}$ so $132^{1601}equiv 132 pmod {125}$. (in fact $phi(125) = 20$ but... why redo work you already did.)



                    So we need to find the unique solution $x equiv 0 pmod 8$ and $x equiv 132 pmod {125}$. That is $x = 8m = 132 + 125k$ where $0 le m < 125$ and $0 le k < 8$.



                    As $8not mid 132$ we can't have $8mid k$ but as $4|132$ we must have $4|k$.



                    In other words $k =4$ and $x equiv 132 + 500equiv 632 pmod {1000}$ is the unique solution.



                    .....



                    If we want to verify this:



                    $132^{1601} = 4^{1601}*33^{1601}$ And $33^{1601} equiv 33pmod{1000}$ so



                    $4^{1601}equiv 4pmod {125}$ so $4^{1601} equiv 4,129,254,379,504,629,754,$ or $879 pmod {1000}$. But as $8|4^{1601}$ then $4^{1601}equiv 504equiv 500 + 4 pmod{1000}$



                    So $132^{1601} = 4^{1601}33^{1601} equiv (500 + 4)33 pmod{1000}$



                    $equiv 500 + 132equiv {1000}$



                    ==========



                    In general. If you have $a$ and $n$ and $gcd(a,n) = d$ then we can set up $n = n'D$ where $gcd(n',D) = 1$ and $d|D$.



                    Then we can solve $a^k equiv xpmod n$ by solving $a^k pmod{n'}$ and $a^k equiv pmod D$.



                    $a^k pmod{n'}$ can be solved by Euler's Theorem.



                    $a$ can also be written as $a = a'delta$ where $gcd(a',n) = gcd(a', d) = 1$ and $d|delta$ (note that either $delta$ or $D$ equals $d$). And so we can solve $a^kpmod D$ by solving $a^k = a'^k*d^k*(frac {delta}d)^k = MD = Md*frac Ddimplies$



                    $a'^k d^{k-1}(frac {delta}d)^k = Mfrac Dd$ . If $D= d$ then will mean $a^kequiv 0 pmod D$. Other wise this means $a'^k d^{k-1} = Mfrac Dd$. Now $frac Dd$ has the same prime factors of $d$ so this will usually mean $a^k equiv 0pmod D$ but might not if the powers of the prime factors of $frac Dd$ are higher than the prime factors of $d^{k-1}$. But if that is the case we can reduce and and solve by Euler's theorem.



                    So Euler's theorem in combination with CRT will always allow us to solve these.







                    share|cite|improve this answer














                    share|cite|improve this answer



                    share|cite|improve this answer








                    edited Feb 2 at 22:18

























                    answered Feb 2 at 21:05









                    fleabloodfleablood

                    1




                    1























                        1












                        $begingroup$

                        $overbrace{132^{large 1+color{#c00}{100}N}}^{large X}!!equiv 132, overbrace{{rm holds} bmod color{#c00}{125}}^{largecolor{#c00}{100 = phi(125)}},$ & $overbrace{!bmod 4}^{large 0^K equiv 0},$ so mod $500,,$ so it's $overbrace{ 132 {rm or} underbrace{132!+!500}_{large rm must be this }!pmod{!1000}}^{large 132 notequiv X {rm by} N>1 ,{Large Rightarrow}, 8 mid 132^{LARGE 2}, mid X!! } $






                        share|cite|improve this answer











                        $endgroup$


















                          1












                          $begingroup$

                          $overbrace{132^{large 1+color{#c00}{100}N}}^{large X}!!equiv 132, overbrace{{rm holds} bmod color{#c00}{125}}^{largecolor{#c00}{100 = phi(125)}},$ & $overbrace{!bmod 4}^{large 0^K equiv 0},$ so mod $500,,$ so it's $overbrace{ 132 {rm or} underbrace{132!+!500}_{large rm must be this }!pmod{!1000}}^{large 132 notequiv X {rm by} N>1 ,{Large Rightarrow}, 8 mid 132^{LARGE 2}, mid X!! } $






                          share|cite|improve this answer











                          $endgroup$
















                            1












                            1








                            1





                            $begingroup$

                            $overbrace{132^{large 1+color{#c00}{100}N}}^{large X}!!equiv 132, overbrace{{rm holds} bmod color{#c00}{125}}^{largecolor{#c00}{100 = phi(125)}},$ & $overbrace{!bmod 4}^{large 0^K equiv 0},$ so mod $500,,$ so it's $overbrace{ 132 {rm or} underbrace{132!+!500}_{large rm must be this }!pmod{!1000}}^{large 132 notequiv X {rm by} N>1 ,{Large Rightarrow}, 8 mid 132^{LARGE 2}, mid X!! } $






                            share|cite|improve this answer











                            $endgroup$



                            $overbrace{132^{large 1+color{#c00}{100}N}}^{large X}!!equiv 132, overbrace{{rm holds} bmod color{#c00}{125}}^{largecolor{#c00}{100 = phi(125)}},$ & $overbrace{!bmod 4}^{large 0^K equiv 0},$ so mod $500,,$ so it's $overbrace{ 132 {rm or} underbrace{132!+!500}_{large rm must be this }!pmod{!1000}}^{large 132 notequiv X {rm by} N>1 ,{Large Rightarrow}, 8 mid 132^{LARGE 2}, mid X!! } $







                            share|cite|improve this answer














                            share|cite|improve this answer



                            share|cite|improve this answer








                            edited Feb 2 at 23:50

























                            answered Feb 2 at 23:44









                            Bill DubuqueBill Dubuque

                            214k29197658




                            214k29197658






























                                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%2f3097662%2fcalculation-of-the-last-three-digits-of-1321601-solving-x-equiv-132160%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

                                MongoDB - Not Authorized To Execute Command

                                Image
                                .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I have successfully enabled authorization on MongoDB and I have created an account on the admin database and then I created an account for my database called test. The following connection string to connect to my test database works successfully: mongo --host 192.168.17.52 --port 27017 -u user1 -p password --authenticationDatabase test Only problem I have now is, I cannot execute commands such as: show dbs. I get the following error when I try to do so: "errmsg" : "not authorized on admin to execute command { listDatabases: 1.0, lsid: { id: UUID("a1d5bc0d-bc58-485e-b232-270758a89455") }, $db: "admin...
                                Read more

                                How to fix TextFormField cause rebuild widget in Flutter

                                Image
                                .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box; } 0 I've got the same issue at #9280. I tried all solutions from that topic with/without GlobalKey for Scaffold and Form but the problem wasn't fixed. I tried to build a authentication form with login and signup. But the keyboard doesn't show when I tap the TextFormField at the first time. Then I try to input some letter from physical keyboard, the widget is rebuilt. Like this: login screen Nothing to be log when I run flutter run --verbose, so I logged manually. Every tapping on field, the widget called dispose -> init -> build. [√] Flutter (Channel beta, v1.0.0, on Microsoft Windows [Version 10.0.17763.195], ...
                                Read more

                                Npm cannot find a required file even through it is in the searched directory

                                Image
                                up vote 0 down vote favorite I got that error: users-Air:pdfuploader user$ npm run start client@0.1.0 start /Users/user/Documents/pdfuploader react-scripts start Could not find a required file. Name: index.html Searched in: /Users/user/Documents/pdfuploader/public npm ERR! code ELIFECYCLE npm ERR! errno 1 npm ERR! client@0.1.0 start: `react-scripts start` npm ERR! Exit status 1 npm ERR! npm ERR! Failed at the client@0.1.0 start script. npm ERR! This is probably not a problem with npm. There is likely additional logging output above. npm ERR! A complete log of this run can be found in: npm ERR! /Users/user/.npm/_logs/2018-11-19T10_19_14_555Z-debug.log users-Air:pdfuploader user$ And the file is in /Users/user/Documents/pdfuploader/public as you can see in my github repository: https://github.c...
                                Read more