How do I compute $a^b,bmod c$ by hand?












76












$begingroup$


How do I efficiently compute $a^b,bmod c$:




  • When $b$ is huge, for instance $5^{844325},bmod 21$?

  • When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, for instance $5^{69},bmod 101$?

  • When $(a,c) neq 1$, for instance $6^{103},bmod 14$?


Are there any other tricks for evaluating exponents in modular arithmetic?





This is being asked in an effort to cut down on duplicates, see here: Coping with *abstract* duplicate questions.



and here: List of Generalizations of Common Questions










share|cite|improve this question











$endgroup$












  • $begingroup$
    fermat's little theorem
    $endgroup$
    – geraldgreen
    Nov 11 '11 at 22:37










  • $begingroup$
    It may be laborious when $c$ is huge, but $b$ being huge should be no problem.
    $endgroup$
    – Michael Hardy
    Nov 11 '11 at 22:45










  • $begingroup$
    @user7530 I don't think questions can be community wiki.
    $endgroup$
    – Simply Beautiful Art
    Dec 31 '16 at 22:23
















76












$begingroup$


How do I efficiently compute $a^b,bmod c$:




  • When $b$ is huge, for instance $5^{844325},bmod 21$?

  • When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, for instance $5^{69},bmod 101$?

  • When $(a,c) neq 1$, for instance $6^{103},bmod 14$?


Are there any other tricks for evaluating exponents in modular arithmetic?





This is being asked in an effort to cut down on duplicates, see here: Coping with *abstract* duplicate questions.



and here: List of Generalizations of Common Questions










share|cite|improve this question











$endgroup$












  • $begingroup$
    fermat's little theorem
    $endgroup$
    – geraldgreen
    Nov 11 '11 at 22:37










  • $begingroup$
    It may be laborious when $c$ is huge, but $b$ being huge should be no problem.
    $endgroup$
    – Michael Hardy
    Nov 11 '11 at 22:45










  • $begingroup$
    @user7530 I don't think questions can be community wiki.
    $endgroup$
    – Simply Beautiful Art
    Dec 31 '16 at 22:23














76












76








76


48



$begingroup$


How do I efficiently compute $a^b,bmod c$:




  • When $b$ is huge, for instance $5^{844325},bmod 21$?

  • When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, for instance $5^{69},bmod 101$?

  • When $(a,c) neq 1$, for instance $6^{103},bmod 14$?


Are there any other tricks for evaluating exponents in modular arithmetic?





This is being asked in an effort to cut down on duplicates, see here: Coping with *abstract* duplicate questions.



and here: List of Generalizations of Common Questions










share|cite|improve this question











$endgroup$




How do I efficiently compute $a^b,bmod c$:




  • When $b$ is huge, for instance $5^{844325},bmod 21$?

  • When $b$ is less than $c$ but it would still be a lot of work to multiply $a$ by itself $b$ times, for instance $5^{69},bmod 101$?

  • When $(a,c) neq 1$, for instance $6^{103},bmod 14$?


Are there any other tricks for evaluating exponents in modular arithmetic?





This is being asked in an effort to cut down on duplicates, see here: Coping with *abstract* duplicate questions.



and here: List of Generalizations of Common Questions







elementary-number-theory modular-arithmetic exponentiation faq






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Apr 9 '15 at 10:28









Martin Sleziak

44.8k9118272




44.8k9118272










asked Nov 11 '11 at 22:05









user7530user7530

34.7k759113




34.7k759113












  • $begingroup$
    fermat's little theorem
    $endgroup$
    – geraldgreen
    Nov 11 '11 at 22:37










  • $begingroup$
    It may be laborious when $c$ is huge, but $b$ being huge should be no problem.
    $endgroup$
    – Michael Hardy
    Nov 11 '11 at 22:45










  • $begingroup$
    @user7530 I don't think questions can be community wiki.
    $endgroup$
    – Simply Beautiful Art
    Dec 31 '16 at 22:23


















  • $begingroup$
    fermat's little theorem
    $endgroup$
    – geraldgreen
    Nov 11 '11 at 22:37










  • $begingroup$
    It may be laborious when $c$ is huge, but $b$ being huge should be no problem.
    $endgroup$
    – Michael Hardy
    Nov 11 '11 at 22:45










  • $begingroup$
    @user7530 I don't think questions can be community wiki.
    $endgroup$
    – Simply Beautiful Art
    Dec 31 '16 at 22:23
















$begingroup$
fermat's little theorem
$endgroup$
– geraldgreen
Nov 11 '11 at 22:37




$begingroup$
fermat's little theorem
$endgroup$
– geraldgreen
Nov 11 '11 at 22:37












$begingroup$
It may be laborious when $c$ is huge, but $b$ being huge should be no problem.
$endgroup$
– Michael Hardy
Nov 11 '11 at 22:45




$begingroup$
It may be laborious when $c$ is huge, but $b$ being huge should be no problem.
$endgroup$
– Michael Hardy
Nov 11 '11 at 22:45












$begingroup$
@user7530 I don't think questions can be community wiki.
$endgroup$
– Simply Beautiful Art
Dec 31 '16 at 22:23




$begingroup$
@user7530 I don't think questions can be community wiki.
$endgroup$
– Simply Beautiful Art
Dec 31 '16 at 22:23










8 Answers
8






active

oldest

votes


















39












$begingroup$

Wikipage on modular arithmetic is not bad.




  • When $b$ is huge, and $a$ and $c$ are coprime, Euler's theorem applies:
    $$
    a^b equiv a^{b , bmod , phi(c)} , bmod c
    $$
    For the example at hand, $phi(21) = phi(3) times phi(7) = 2 times 6 = 12$. $ 844325 bmod 12 = 5$, so $5^5 = 5 times 25^2 equiv 5 times 4^2 = 80 equiv 17 mod 21$.


  • When $a$ and $c$ are coprime, but $0<b<phi(c)$, repeated squaring (or using other compositions of powers) is the fastest way to go (manually):
    $$
    begin{eqnarray}
    5^4 equiv 5 times 5^3 equiv 5 times 24 equiv 19 &pmod{101}\
    19^4 equiv (19^2)^2 equiv 58^2 equiv (-43)^2 equiv 1849 equiv 31 &pmod{101} \
    31^4 equiv (31^2)^2 equiv (961)^2 equiv 52^2 equiv 2704 equiv 78 &pmod{101} \
    5^{69} equiv 5 times 5^4 times ((5^4)^4)^4 equiv 5 times 19 times 78 equiv 5 times 19 times (-23)\
    equiv 19 times (-14) equiv -266 equiv 37 & pmod{101}
    end{eqnarray}
    $$


  • When $a$ and $c$ are not coprime, let $g = gcd(a,c)$. Let $a = g times d$ and $c = g times f$, then, assuming $b > 1$:
    $$
    a^b bmod c = g^b times d^b bmod (g times f) = ( g times (g^{b-1} d^b bmod f) ) bmod c
    $$
    In the example given, $gcd(6,14) = 2$. So $2^{102} times 3^{103} mod 7$, using Euler'r theorem, with $phi(7) = 6$, and $102 equiv 0 mod 6$, $2^{102} times 3^{103} equiv 3 mod 7$, so $6^{103} equiv (2 times 3) equiv 6 mod 14 $.







share|cite|improve this answer











$endgroup$









  • 5




    $begingroup$
    Carmichael function often reduces the exponent more than Euler's totient function.
    $endgroup$
    – user26486
    Feb 18 '15 at 9:56










  • $begingroup$
    How did you arrive at $$ a^b equiv a^{b , bmod , phi(c)} , bmod c $$ using Euler's theorem?
    $endgroup$
    – Victor
    Jun 9 '17 at 20:41










  • $begingroup$
    By Euler theorem power of $a$ to Euler totient of $c$ is one module $c$, hence the exponent $b$ can be reduced modulo the totient.
    $endgroup$
    – Sasha
    Jun 9 '17 at 20:48



















26












$begingroup$

Let's try $5^{844325} bmod 21$:
$$
begin{align}
5^0 & & & equiv 1 \
5^1 & & &equiv 5 \
5^2 & equiv 25 & & equiv 4 \
5^3 & equiv 4cdot 5 & & equiv 20 \
5^4 & equiv 20cdot 5 & & equiv 16 \
5^5 & equiv 16cdot 5 & & equiv 17 \
5^6 & equiv 17cdot 5 & & equiv 1
end{align}
$$
So multiplying by $5$ six times is the same as multiplying by $1$. We want to multiply by $5$ a large number of times: $844325$. How many times do we multiply by $5$ six times? The number of times $6$ goes into $844325$ is $140720$ with a remainder of $5$. That remainder is what matters. Multiply by $5^6$ exactly $140720$ times and that's the same as multiplying by $1$ that many times. Then multiply by $5$ just $5$ more times, and get $17$.



So $5^{844325} equiv 17 bmod 21$.






share|cite|improve this answer











$endgroup$













  • $begingroup$
    You may want to check my arithmetic, but this method will do it when you get that right.
    $endgroup$
    – Michael Hardy
    Nov 11 '11 at 23:05










  • $begingroup$
    This method won't be so nice when $(5,21)neq 1$...
    $endgroup$
    – mathmath8128
    Nov 11 '11 at 23:53






  • 5




    $begingroup$
    @aengle: it will be similar: for example for $6^{844325} mod 21$ you would look at $6^0 equiv 1$, $6^1 equiv 6$, $6^2 equiv 15$, $6^3 equiv 6$, $6^4 equiv 15$, so with a period of $2$. The number of times $2$ goes into $844325$ is $422162$ with a remainder of $1$. So $6^{844324} equiv 15 mod 21$ and thus $6^{844325} equiv 6 mod 21$.
    $endgroup$
    – Henry
    Nov 12 '11 at 1:38












  • $begingroup$
    Beautiful! $(+1)$
    $endgroup$
    – user477343
    May 22 '18 at 11:56



















12












$begingroup$

Here are two examples of the square and multiply method for $5^{69} bmod 101$:



$$ begin{matrix}
5^{69} &equiv& 5 &cdot &(5^{34})^2 &equiv & 37
\ 5^{34} &equiv& &&(5^{17})^2 &equiv& 88 &(equiv -13)
\ 5^{17} &equiv& 5 &cdot &(5^8)^2 &equiv& 54
\ 5^{8} &equiv& &&(5^4)^2 &equiv& 58
\ 5^{4} &equiv& &&(5^2)^2 &equiv& 19
\ 5^{2} &equiv& &&(5^1)^2 &equiv& 25
\ 5^{1} &equiv& 5 &cdot &(1)^2 &equiv& 5
end{matrix} $$



The computation proceeds by starting with $5^{69}$ and then working downward to create the first two columns, then computing the results from the bottom up. (normally you'd skip the last line; I put it there to clarify the next paragraph)



As a shortcut, the binary representation of $69$ is $1000101_2$; reading the binary digits from left to right tell us the operations to do starting from the value $1$: $0$ says "square" and $1$ says "square and multiply by $5$".





The other way is to compute a list of repeated squares:



$$ begin{matrix}
5^1 &equiv& 5
\ 5^2 &equiv& 25
\ 5^4 &equiv& 19
\ 5^8 &equiv& 58
\ 5^{16} &equiv& 31
\ 5^{32} &equiv& 52
\ 5^{64} &equiv& 78
end{matrix} $$



Then work out which terms you need to multiply together:



$$ 5^{69} equiv 5^{64 + 4 + 1} equiv 78 cdot 19 cdot 5 equiv 37 $$






share|cite|improve this answer











$endgroup$









  • 1




    $begingroup$
    Good to have an example of square-and-multiply at hand.
    $endgroup$
    – Jyrki Lahtonen
    Jun 9 '16 at 9:23






  • 1




    $begingroup$
    If memory serves, this is sometimes referred to as the "Russian peasant" method.
    $endgroup$
    – J. M. is not a mathematician
    Jun 9 '16 at 10:20










  • $begingroup$
    @J.M.isnotamathematician It is closer to $a$ to the power of the "Russian peasant" method. en.wikipedia.org/wiki/Ancient_Egyptian_multiplication (The named method is a multiplication algorithm using doubling and adding; what we have here is a power algorithm using squaring and multiplying.)
    $endgroup$
    – Rosie F
    May 28 '18 at 17:48



















10












$begingroup$

Some tricks which are useful for modular exponentiation



The intention of this post is to collect various tricks which can sometimes simplify computations of this type. (Especially when done by hand and not using computer or calculator.) This post is community-wiki, so feel free to edit it if you have some ideas for improvements.



Using complement: $(c-a) equiv (-a) pmod c$



If the given number is close to $c$ (but smaller than $c$), replacing it by $c-a$ my help us - we will work with smaller numbers. Some examples:




  • If we want to calculate $7^{777} bmod 50$, it is useful to notice that $7^2=49 equiv (-1) pmod{50}$, so we can replace $7^2$ by $-1$
    and get $7^{777} equiv 7^{388} cdot 7 equiv (-1)^{388} cdot 7 equiv 7 pmod{50}$. (This was part of Find $3^{333} + 7^{777}pmod{ 50}$.)

  • We want to calculate $50^{50} bmod 13$. Since $4cdot 13 = 52$, we have $50 equiv -2 pmod{13}$. So we can work with $-2$ instead of $50$, which will be easier, since it is a smaller number. How to use Fermat's little theorem to find $50^{50}pmod{13}$?


If you can find a power which is close to the modulo, try to use it



Some examples:




  • We want to calculate $6^{1000} bmod 23$. Since $6=2cdot 3$, let us have a look whether we can somehow combine these two numbers to get something with small remainder modulo $23$. We may notice that $24=2^3cdot 3 equiv 1pmod{23}$. We can also notice that $27 equiv 4pmod{23}$, i.e. $3^3equiv 2^2pmod{23}$. Replacing $2^2$ with $3^3$ in the previous congruence we get $2cdot 3^4 equiv 1 pmod{23}$. Now we can combine the preceding two congruences to get $1equiv (2^3cdot 3)^3cdot(2cdot 3^4)^2 = 2^{11}cdot3^{11} = 6^{11}pmod{23}$. Notice that the congruence $6^{11}equiv1pmod{23}$ can be obtained also by different means: Find $6^{1000} mod 23$

  • We want to find $5^{119} bmod 59$. This can be solved in a very simple way using Fermat's little theorem: Find the remainder using Fermat's little theorem when $5^{119}$ is divided by $59$? However, let us forget Fermat's little theorem and let us try to find some powers of $5$ which give small remainder modulo $59$. We may notice that $5^3$ is not too far from $2cdot59$ and get $5^3equiv125equiv7pmod{59}$. Similarly, $7cdot25$ seems to be not very far from $3cdot59$, so we can try $5^5=5^3cdot5^2equiv7cdot25equiv175equiv-2pmod{59}$. And now we can use that $64$ is a power of two which is close to our remainder to get $5^{30} = (5^5)^6 equiv (-2)^6 equiv 64 equiv 5 pmod{59}$. Since we have $5^{30}equiv5pmod{59}$ and $gcd(5,59)=1$, we can cancel $5$ on both sides to get $5^{29}equiv1pmod{59}$. And the last fact can be used in further computations.

  • The task is to find $16^{74} bmod 65$. One may notice that $64$ is a power of two which is very close to $65$. So we have $2^6 = 64 equiv -1 pmod{65}$, meaning that $16^{74}=(2^4)^{74}=2^{296} = 2^{6cdot49}cdot2^2 equiv (-1)^{49}cdot4 equiv -1 pmod{65}$. See also https://math.stackexchange.com/questions/2077609/computing-1674-bmod-65.


Using Euler's criterion



Euler's criterion can tell us about value of $a^{frac{p-1}2}$ modulo a prime $p$. However, we need to know whether $a$ is a quadratic residue modulo $p$. For some numbers this can be guessed. Sometimes this can be checked using quadratic reciprocity (Of course, this is not much of an improvement in comparison with Fermat's little theorem, which gives us $a^{p-1}equiv1pmod p$.)




  • Let us have a look at $5^{29} bmod 59$ (we have already computed this using different computations above). It is easy to notice that $8^2=64equiv5pmod{59}$, so $5$ is a quadratic residue modulo $59$. So from Euler's criterion we get $5^{29}=5^{(59-1)/2}equiv1pmod{29}$.






share|cite|improve this answer











$endgroup$





















    6












    $begingroup$

    In general, squared exponentiation is used, this is $O(log(b) cdot log(n))$ if multiplication $bmod n$ is $O(log (n))$.



    powmod(a,b,n){
    res=1;
    fact=a;
    while(b>0){
    res=(res*(b%2)==1?fact:1)%n;
    fact=(fact*fact)%n;
    b=floor(b/2);
    }
    }


    when $b$ is huge (much larger than $n$) you can (attempt) to find the rank of the ring ($varphi(n)$) and find the remainder of $b pmod {varphi(n)}$ because $a^b bmod n= a^{b mod varphi(n)} bmod n$ (for $21$, it is $(3-1) cdot (7-1)=12$) this requires finding the prime factors of $n$.



    In general the rank for $n = prod{(p_i)^{k_i-1} cdot (p_i-1)}$ with $p_i^{k_i}$ the prime factors of $n$.






    share|cite|improve this answer











    $endgroup$





















      6












      $begingroup$

      The Chinese remainder theorem can reduce the computation needed. For example, we can factor $21 = 3 cdot 7$, and have



      $$ 1 cdot 7 - 2 cdot 3 = 1$$



      (in general, we can use the extended Euclidean algorithm to produce this formula)



      Consequently, if



      $$x equiv a pmod 3 qquad x equiv b pmod 7 $$



      then



      $$ x equiv a cdot (1 cdot 7 ) + b cdot (-2 cdot 3) pmod{21} $$



      Thus, we can compute $5^{844325} bmod 21$ by using our favorite means to compute:



      $$ 5^{844325} equiv 2 pmod 3 qquad 5^{844325} equiv 3 pmod 7 $$



      and thus



      $$ 5^{844325} equiv 2 cdot 7 + 3 cdot (-6) equiv -4 equiv 17 pmod{21} $$






      share|cite|improve this answer









      $endgroup$





















        4












        $begingroup$

        For the first question: use $a^{Phi(c)}=1 mod c$, where $Phi(c)$ is the number of coprimes to $c$ below $c$. For $c=21=7cdot 3$ we have $Phi(c)=(7-1)cdot(3-1)=12$



        second question: Use $a^4=(a^2)^2, a^8=(a^4)^2$ and so on. Decompose the exponent into powers of 2 and combine them using $a^ncdot a^m=a^{n+m}$ E.g. $a^{69}=a^{64}cdot a^4cdot a^1$






        share|cite|improve this answer











        $endgroup$





















          -1












          $begingroup$

          Its not hard to show that the sequence



          $$
          x_n=a^nmod{c}
          $$



          is periodic, with period $p$ (which is at most $c$). Evaluate the first few terms to get the period ${x_0,x_1,dots,x_{p-1}}$. Then you can evaluate for any huge power $n$ as



          $$
          x_n=x_{nmod{p}}
          $$






          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%2f81228%2fhow-do-i-compute-ab-bmod-c-by-hand%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            8 Answers
            8






            active

            oldest

            votes








            8 Answers
            8






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            39












            $begingroup$

            Wikipage on modular arithmetic is not bad.




            • When $b$ is huge, and $a$ and $c$ are coprime, Euler's theorem applies:
              $$
              a^b equiv a^{b , bmod , phi(c)} , bmod c
              $$
              For the example at hand, $phi(21) = phi(3) times phi(7) = 2 times 6 = 12$. $ 844325 bmod 12 = 5$, so $5^5 = 5 times 25^2 equiv 5 times 4^2 = 80 equiv 17 mod 21$.


            • When $a$ and $c$ are coprime, but $0<b<phi(c)$, repeated squaring (or using other compositions of powers) is the fastest way to go (manually):
              $$
              begin{eqnarray}
              5^4 equiv 5 times 5^3 equiv 5 times 24 equiv 19 &pmod{101}\
              19^4 equiv (19^2)^2 equiv 58^2 equiv (-43)^2 equiv 1849 equiv 31 &pmod{101} \
              31^4 equiv (31^2)^2 equiv (961)^2 equiv 52^2 equiv 2704 equiv 78 &pmod{101} \
              5^{69} equiv 5 times 5^4 times ((5^4)^4)^4 equiv 5 times 19 times 78 equiv 5 times 19 times (-23)\
              equiv 19 times (-14) equiv -266 equiv 37 & pmod{101}
              end{eqnarray}
              $$


            • When $a$ and $c$ are not coprime, let $g = gcd(a,c)$. Let $a = g times d$ and $c = g times f$, then, assuming $b > 1$:
              $$
              a^b bmod c = g^b times d^b bmod (g times f) = ( g times (g^{b-1} d^b bmod f) ) bmod c
              $$
              In the example given, $gcd(6,14) = 2$. So $2^{102} times 3^{103} mod 7$, using Euler'r theorem, with $phi(7) = 6$, and $102 equiv 0 mod 6$, $2^{102} times 3^{103} equiv 3 mod 7$, so $6^{103} equiv (2 times 3) equiv 6 mod 14 $.







            share|cite|improve this answer











            $endgroup$









            • 5




              $begingroup$
              Carmichael function often reduces the exponent more than Euler's totient function.
              $endgroup$
              – user26486
              Feb 18 '15 at 9:56










            • $begingroup$
              How did you arrive at $$ a^b equiv a^{b , bmod , phi(c)} , bmod c $$ using Euler's theorem?
              $endgroup$
              – Victor
              Jun 9 '17 at 20:41










            • $begingroup$
              By Euler theorem power of $a$ to Euler totient of $c$ is one module $c$, hence the exponent $b$ can be reduced modulo the totient.
              $endgroup$
              – Sasha
              Jun 9 '17 at 20:48
















            39












            $begingroup$

            Wikipage on modular arithmetic is not bad.




            • When $b$ is huge, and $a$ and $c$ are coprime, Euler's theorem applies:
              $$
              a^b equiv a^{b , bmod , phi(c)} , bmod c
              $$
              For the example at hand, $phi(21) = phi(3) times phi(7) = 2 times 6 = 12$. $ 844325 bmod 12 = 5$, so $5^5 = 5 times 25^2 equiv 5 times 4^2 = 80 equiv 17 mod 21$.


            • When $a$ and $c$ are coprime, but $0<b<phi(c)$, repeated squaring (or using other compositions of powers) is the fastest way to go (manually):
              $$
              begin{eqnarray}
              5^4 equiv 5 times 5^3 equiv 5 times 24 equiv 19 &pmod{101}\
              19^4 equiv (19^2)^2 equiv 58^2 equiv (-43)^2 equiv 1849 equiv 31 &pmod{101} \
              31^4 equiv (31^2)^2 equiv (961)^2 equiv 52^2 equiv 2704 equiv 78 &pmod{101} \
              5^{69} equiv 5 times 5^4 times ((5^4)^4)^4 equiv 5 times 19 times 78 equiv 5 times 19 times (-23)\
              equiv 19 times (-14) equiv -266 equiv 37 & pmod{101}
              end{eqnarray}
              $$


            • When $a$ and $c$ are not coprime, let $g = gcd(a,c)$. Let $a = g times d$ and $c = g times f$, then, assuming $b > 1$:
              $$
              a^b bmod c = g^b times d^b bmod (g times f) = ( g times (g^{b-1} d^b bmod f) ) bmod c
              $$
              In the example given, $gcd(6,14) = 2$. So $2^{102} times 3^{103} mod 7$, using Euler'r theorem, with $phi(7) = 6$, and $102 equiv 0 mod 6$, $2^{102} times 3^{103} equiv 3 mod 7$, so $6^{103} equiv (2 times 3) equiv 6 mod 14 $.







            share|cite|improve this answer











            $endgroup$









            • 5




              $begingroup$
              Carmichael function often reduces the exponent more than Euler's totient function.
              $endgroup$
              – user26486
              Feb 18 '15 at 9:56










            • $begingroup$
              How did you arrive at $$ a^b equiv a^{b , bmod , phi(c)} , bmod c $$ using Euler's theorem?
              $endgroup$
              – Victor
              Jun 9 '17 at 20:41










            • $begingroup$
              By Euler theorem power of $a$ to Euler totient of $c$ is one module $c$, hence the exponent $b$ can be reduced modulo the totient.
              $endgroup$
              – Sasha
              Jun 9 '17 at 20:48














            39












            39








            39





            $begingroup$

            Wikipage on modular arithmetic is not bad.




            • When $b$ is huge, and $a$ and $c$ are coprime, Euler's theorem applies:
              $$
              a^b equiv a^{b , bmod , phi(c)} , bmod c
              $$
              For the example at hand, $phi(21) = phi(3) times phi(7) = 2 times 6 = 12$. $ 844325 bmod 12 = 5$, so $5^5 = 5 times 25^2 equiv 5 times 4^2 = 80 equiv 17 mod 21$.


            • When $a$ and $c$ are coprime, but $0<b<phi(c)$, repeated squaring (or using other compositions of powers) is the fastest way to go (manually):
              $$
              begin{eqnarray}
              5^4 equiv 5 times 5^3 equiv 5 times 24 equiv 19 &pmod{101}\
              19^4 equiv (19^2)^2 equiv 58^2 equiv (-43)^2 equiv 1849 equiv 31 &pmod{101} \
              31^4 equiv (31^2)^2 equiv (961)^2 equiv 52^2 equiv 2704 equiv 78 &pmod{101} \
              5^{69} equiv 5 times 5^4 times ((5^4)^4)^4 equiv 5 times 19 times 78 equiv 5 times 19 times (-23)\
              equiv 19 times (-14) equiv -266 equiv 37 & pmod{101}
              end{eqnarray}
              $$


            • When $a$ and $c$ are not coprime, let $g = gcd(a,c)$. Let $a = g times d$ and $c = g times f$, then, assuming $b > 1$:
              $$
              a^b bmod c = g^b times d^b bmod (g times f) = ( g times (g^{b-1} d^b bmod f) ) bmod c
              $$
              In the example given, $gcd(6,14) = 2$. So $2^{102} times 3^{103} mod 7$, using Euler'r theorem, with $phi(7) = 6$, and $102 equiv 0 mod 6$, $2^{102} times 3^{103} equiv 3 mod 7$, so $6^{103} equiv (2 times 3) equiv 6 mod 14 $.







            share|cite|improve this answer











            $endgroup$



            Wikipage on modular arithmetic is not bad.




            • When $b$ is huge, and $a$ and $c$ are coprime, Euler's theorem applies:
              $$
              a^b equiv a^{b , bmod , phi(c)} , bmod c
              $$
              For the example at hand, $phi(21) = phi(3) times phi(7) = 2 times 6 = 12$. $ 844325 bmod 12 = 5$, so $5^5 = 5 times 25^2 equiv 5 times 4^2 = 80 equiv 17 mod 21$.


            • When $a$ and $c$ are coprime, but $0<b<phi(c)$, repeated squaring (or using other compositions of powers) is the fastest way to go (manually):
              $$
              begin{eqnarray}
              5^4 equiv 5 times 5^3 equiv 5 times 24 equiv 19 &pmod{101}\
              19^4 equiv (19^2)^2 equiv 58^2 equiv (-43)^2 equiv 1849 equiv 31 &pmod{101} \
              31^4 equiv (31^2)^2 equiv (961)^2 equiv 52^2 equiv 2704 equiv 78 &pmod{101} \
              5^{69} equiv 5 times 5^4 times ((5^4)^4)^4 equiv 5 times 19 times 78 equiv 5 times 19 times (-23)\
              equiv 19 times (-14) equiv -266 equiv 37 & pmod{101}
              end{eqnarray}
              $$


            • When $a$ and $c$ are not coprime, let $g = gcd(a,c)$. Let $a = g times d$ and $c = g times f$, then, assuming $b > 1$:
              $$
              a^b bmod c = g^b times d^b bmod (g times f) = ( g times (g^{b-1} d^b bmod f) ) bmod c
              $$
              In the example given, $gcd(6,14) = 2$. So $2^{102} times 3^{103} mod 7$, using Euler'r theorem, with $phi(7) = 6$, and $102 equiv 0 mod 6$, $2^{102} times 3^{103} equiv 3 mod 7$, so $6^{103} equiv (2 times 3) equiv 6 mod 14 $.








            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Jun 9 '16 at 9:22









            Hurkyl

            111k9119262




            111k9119262










            answered Nov 11 '11 at 22:51









            SashaSasha

            60.7k5108180




            60.7k5108180








            • 5




              $begingroup$
              Carmichael function often reduces the exponent more than Euler's totient function.
              $endgroup$
              – user26486
              Feb 18 '15 at 9:56










            • $begingroup$
              How did you arrive at $$ a^b equiv a^{b , bmod , phi(c)} , bmod c $$ using Euler's theorem?
              $endgroup$
              – Victor
              Jun 9 '17 at 20:41










            • $begingroup$
              By Euler theorem power of $a$ to Euler totient of $c$ is one module $c$, hence the exponent $b$ can be reduced modulo the totient.
              $endgroup$
              – Sasha
              Jun 9 '17 at 20:48














            • 5




              $begingroup$
              Carmichael function often reduces the exponent more than Euler's totient function.
              $endgroup$
              – user26486
              Feb 18 '15 at 9:56










            • $begingroup$
              How did you arrive at $$ a^b equiv a^{b , bmod , phi(c)} , bmod c $$ using Euler's theorem?
              $endgroup$
              – Victor
              Jun 9 '17 at 20:41










            • $begingroup$
              By Euler theorem power of $a$ to Euler totient of $c$ is one module $c$, hence the exponent $b$ can be reduced modulo the totient.
              $endgroup$
              – Sasha
              Jun 9 '17 at 20:48








            5




            5




            $begingroup$
            Carmichael function often reduces the exponent more than Euler's totient function.
            $endgroup$
            – user26486
            Feb 18 '15 at 9:56




            $begingroup$
            Carmichael function often reduces the exponent more than Euler's totient function.
            $endgroup$
            – user26486
            Feb 18 '15 at 9:56












            $begingroup$
            How did you arrive at $$ a^b equiv a^{b , bmod , phi(c)} , bmod c $$ using Euler's theorem?
            $endgroup$
            – Victor
            Jun 9 '17 at 20:41




            $begingroup$
            How did you arrive at $$ a^b equiv a^{b , bmod , phi(c)} , bmod c $$ using Euler's theorem?
            $endgroup$
            – Victor
            Jun 9 '17 at 20:41












            $begingroup$
            By Euler theorem power of $a$ to Euler totient of $c$ is one module $c$, hence the exponent $b$ can be reduced modulo the totient.
            $endgroup$
            – Sasha
            Jun 9 '17 at 20:48




            $begingroup$
            By Euler theorem power of $a$ to Euler totient of $c$ is one module $c$, hence the exponent $b$ can be reduced modulo the totient.
            $endgroup$
            – Sasha
            Jun 9 '17 at 20:48











            26












            $begingroup$

            Let's try $5^{844325} bmod 21$:
            $$
            begin{align}
            5^0 & & & equiv 1 \
            5^1 & & &equiv 5 \
            5^2 & equiv 25 & & equiv 4 \
            5^3 & equiv 4cdot 5 & & equiv 20 \
            5^4 & equiv 20cdot 5 & & equiv 16 \
            5^5 & equiv 16cdot 5 & & equiv 17 \
            5^6 & equiv 17cdot 5 & & equiv 1
            end{align}
            $$
            So multiplying by $5$ six times is the same as multiplying by $1$. We want to multiply by $5$ a large number of times: $844325$. How many times do we multiply by $5$ six times? The number of times $6$ goes into $844325$ is $140720$ with a remainder of $5$. That remainder is what matters. Multiply by $5^6$ exactly $140720$ times and that's the same as multiplying by $1$ that many times. Then multiply by $5$ just $5$ more times, and get $17$.



            So $5^{844325} equiv 17 bmod 21$.






            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              You may want to check my arithmetic, but this method will do it when you get that right.
              $endgroup$
              – Michael Hardy
              Nov 11 '11 at 23:05










            • $begingroup$
              This method won't be so nice when $(5,21)neq 1$...
              $endgroup$
              – mathmath8128
              Nov 11 '11 at 23:53






            • 5




              $begingroup$
              @aengle: it will be similar: for example for $6^{844325} mod 21$ you would look at $6^0 equiv 1$, $6^1 equiv 6$, $6^2 equiv 15$, $6^3 equiv 6$, $6^4 equiv 15$, so with a period of $2$. The number of times $2$ goes into $844325$ is $422162$ with a remainder of $1$. So $6^{844324} equiv 15 mod 21$ and thus $6^{844325} equiv 6 mod 21$.
              $endgroup$
              – Henry
              Nov 12 '11 at 1:38












            • $begingroup$
              Beautiful! $(+1)$
              $endgroup$
              – user477343
              May 22 '18 at 11:56
















            26












            $begingroup$

            Let's try $5^{844325} bmod 21$:
            $$
            begin{align}
            5^0 & & & equiv 1 \
            5^1 & & &equiv 5 \
            5^2 & equiv 25 & & equiv 4 \
            5^3 & equiv 4cdot 5 & & equiv 20 \
            5^4 & equiv 20cdot 5 & & equiv 16 \
            5^5 & equiv 16cdot 5 & & equiv 17 \
            5^6 & equiv 17cdot 5 & & equiv 1
            end{align}
            $$
            So multiplying by $5$ six times is the same as multiplying by $1$. We want to multiply by $5$ a large number of times: $844325$. How many times do we multiply by $5$ six times? The number of times $6$ goes into $844325$ is $140720$ with a remainder of $5$. That remainder is what matters. Multiply by $5^6$ exactly $140720$ times and that's the same as multiplying by $1$ that many times. Then multiply by $5$ just $5$ more times, and get $17$.



            So $5^{844325} equiv 17 bmod 21$.






            share|cite|improve this answer











            $endgroup$













            • $begingroup$
              You may want to check my arithmetic, but this method will do it when you get that right.
              $endgroup$
              – Michael Hardy
              Nov 11 '11 at 23:05










            • $begingroup$
              This method won't be so nice when $(5,21)neq 1$...
              $endgroup$
              – mathmath8128
              Nov 11 '11 at 23:53






            • 5




              $begingroup$
              @aengle: it will be similar: for example for $6^{844325} mod 21$ you would look at $6^0 equiv 1$, $6^1 equiv 6$, $6^2 equiv 15$, $6^3 equiv 6$, $6^4 equiv 15$, so with a period of $2$. The number of times $2$ goes into $844325$ is $422162$ with a remainder of $1$. So $6^{844324} equiv 15 mod 21$ and thus $6^{844325} equiv 6 mod 21$.
              $endgroup$
              – Henry
              Nov 12 '11 at 1:38












            • $begingroup$
              Beautiful! $(+1)$
              $endgroup$
              – user477343
              May 22 '18 at 11:56














            26












            26








            26





            $begingroup$

            Let's try $5^{844325} bmod 21$:
            $$
            begin{align}
            5^0 & & & equiv 1 \
            5^1 & & &equiv 5 \
            5^2 & equiv 25 & & equiv 4 \
            5^3 & equiv 4cdot 5 & & equiv 20 \
            5^4 & equiv 20cdot 5 & & equiv 16 \
            5^5 & equiv 16cdot 5 & & equiv 17 \
            5^6 & equiv 17cdot 5 & & equiv 1
            end{align}
            $$
            So multiplying by $5$ six times is the same as multiplying by $1$. We want to multiply by $5$ a large number of times: $844325$. How many times do we multiply by $5$ six times? The number of times $6$ goes into $844325$ is $140720$ with a remainder of $5$. That remainder is what matters. Multiply by $5^6$ exactly $140720$ times and that's the same as multiplying by $1$ that many times. Then multiply by $5$ just $5$ more times, and get $17$.



            So $5^{844325} equiv 17 bmod 21$.






            share|cite|improve this answer











            $endgroup$



            Let's try $5^{844325} bmod 21$:
            $$
            begin{align}
            5^0 & & & equiv 1 \
            5^1 & & &equiv 5 \
            5^2 & equiv 25 & & equiv 4 \
            5^3 & equiv 4cdot 5 & & equiv 20 \
            5^4 & equiv 20cdot 5 & & equiv 16 \
            5^5 & equiv 16cdot 5 & & equiv 17 \
            5^6 & equiv 17cdot 5 & & equiv 1
            end{align}
            $$
            So multiplying by $5$ six times is the same as multiplying by $1$. We want to multiply by $5$ a large number of times: $844325$. How many times do we multiply by $5$ six times? The number of times $6$ goes into $844325$ is $140720$ with a remainder of $5$. That remainder is what matters. Multiply by $5^6$ exactly $140720$ times and that's the same as multiplying by $1$ that many times. Then multiply by $5$ just $5$ more times, and get $17$.



            So $5^{844325} equiv 17 bmod 21$.







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited May 30 '17 at 11:04

























            answered Nov 11 '11 at 22:58









            Michael HardyMichael Hardy

            1




            1












            • $begingroup$
              You may want to check my arithmetic, but this method will do it when you get that right.
              $endgroup$
              – Michael Hardy
              Nov 11 '11 at 23:05










            • $begingroup$
              This method won't be so nice when $(5,21)neq 1$...
              $endgroup$
              – mathmath8128
              Nov 11 '11 at 23:53






            • 5




              $begingroup$
              @aengle: it will be similar: for example for $6^{844325} mod 21$ you would look at $6^0 equiv 1$, $6^1 equiv 6$, $6^2 equiv 15$, $6^3 equiv 6$, $6^4 equiv 15$, so with a period of $2$. The number of times $2$ goes into $844325$ is $422162$ with a remainder of $1$. So $6^{844324} equiv 15 mod 21$ and thus $6^{844325} equiv 6 mod 21$.
              $endgroup$
              – Henry
              Nov 12 '11 at 1:38












            • $begingroup$
              Beautiful! $(+1)$
              $endgroup$
              – user477343
              May 22 '18 at 11:56


















            • $begingroup$
              You may want to check my arithmetic, but this method will do it when you get that right.
              $endgroup$
              – Michael Hardy
              Nov 11 '11 at 23:05










            • $begingroup$
              This method won't be so nice when $(5,21)neq 1$...
              $endgroup$
              – mathmath8128
              Nov 11 '11 at 23:53






            • 5




              $begingroup$
              @aengle: it will be similar: for example for $6^{844325} mod 21$ you would look at $6^0 equiv 1$, $6^1 equiv 6$, $6^2 equiv 15$, $6^3 equiv 6$, $6^4 equiv 15$, so with a period of $2$. The number of times $2$ goes into $844325$ is $422162$ with a remainder of $1$. So $6^{844324} equiv 15 mod 21$ and thus $6^{844325} equiv 6 mod 21$.
              $endgroup$
              – Henry
              Nov 12 '11 at 1:38












            • $begingroup$
              Beautiful! $(+1)$
              $endgroup$
              – user477343
              May 22 '18 at 11:56
















            $begingroup$
            You may want to check my arithmetic, but this method will do it when you get that right.
            $endgroup$
            – Michael Hardy
            Nov 11 '11 at 23:05




            $begingroup$
            You may want to check my arithmetic, but this method will do it when you get that right.
            $endgroup$
            – Michael Hardy
            Nov 11 '11 at 23:05












            $begingroup$
            This method won't be so nice when $(5,21)neq 1$...
            $endgroup$
            – mathmath8128
            Nov 11 '11 at 23:53




            $begingroup$
            This method won't be so nice when $(5,21)neq 1$...
            $endgroup$
            – mathmath8128
            Nov 11 '11 at 23:53




            5




            5




            $begingroup$
            @aengle: it will be similar: for example for $6^{844325} mod 21$ you would look at $6^0 equiv 1$, $6^1 equiv 6$, $6^2 equiv 15$, $6^3 equiv 6$, $6^4 equiv 15$, so with a period of $2$. The number of times $2$ goes into $844325$ is $422162$ with a remainder of $1$. So $6^{844324} equiv 15 mod 21$ and thus $6^{844325} equiv 6 mod 21$.
            $endgroup$
            – Henry
            Nov 12 '11 at 1:38






            $begingroup$
            @aengle: it will be similar: for example for $6^{844325} mod 21$ you would look at $6^0 equiv 1$, $6^1 equiv 6$, $6^2 equiv 15$, $6^3 equiv 6$, $6^4 equiv 15$, so with a period of $2$. The number of times $2$ goes into $844325$ is $422162$ with a remainder of $1$. So $6^{844324} equiv 15 mod 21$ and thus $6^{844325} equiv 6 mod 21$.
            $endgroup$
            – Henry
            Nov 12 '11 at 1:38














            $begingroup$
            Beautiful! $(+1)$
            $endgroup$
            – user477343
            May 22 '18 at 11:56




            $begingroup$
            Beautiful! $(+1)$
            $endgroup$
            – user477343
            May 22 '18 at 11:56











            12












            $begingroup$

            Here are two examples of the square and multiply method for $5^{69} bmod 101$:



            $$ begin{matrix}
            5^{69} &equiv& 5 &cdot &(5^{34})^2 &equiv & 37
            \ 5^{34} &equiv& &&(5^{17})^2 &equiv& 88 &(equiv -13)
            \ 5^{17} &equiv& 5 &cdot &(5^8)^2 &equiv& 54
            \ 5^{8} &equiv& &&(5^4)^2 &equiv& 58
            \ 5^{4} &equiv& &&(5^2)^2 &equiv& 19
            \ 5^{2} &equiv& &&(5^1)^2 &equiv& 25
            \ 5^{1} &equiv& 5 &cdot &(1)^2 &equiv& 5
            end{matrix} $$



            The computation proceeds by starting with $5^{69}$ and then working downward to create the first two columns, then computing the results from the bottom up. (normally you'd skip the last line; I put it there to clarify the next paragraph)



            As a shortcut, the binary representation of $69$ is $1000101_2$; reading the binary digits from left to right tell us the operations to do starting from the value $1$: $0$ says "square" and $1$ says "square and multiply by $5$".





            The other way is to compute a list of repeated squares:



            $$ begin{matrix}
            5^1 &equiv& 5
            \ 5^2 &equiv& 25
            \ 5^4 &equiv& 19
            \ 5^8 &equiv& 58
            \ 5^{16} &equiv& 31
            \ 5^{32} &equiv& 52
            \ 5^{64} &equiv& 78
            end{matrix} $$



            Then work out which terms you need to multiply together:



            $$ 5^{69} equiv 5^{64 + 4 + 1} equiv 78 cdot 19 cdot 5 equiv 37 $$






            share|cite|improve this answer











            $endgroup$









            • 1




              $begingroup$
              Good to have an example of square-and-multiply at hand.
              $endgroup$
              – Jyrki Lahtonen
              Jun 9 '16 at 9:23






            • 1




              $begingroup$
              If memory serves, this is sometimes referred to as the "Russian peasant" method.
              $endgroup$
              – J. M. is not a mathematician
              Jun 9 '16 at 10:20










            • $begingroup$
              @J.M.isnotamathematician It is closer to $a$ to the power of the "Russian peasant" method. en.wikipedia.org/wiki/Ancient_Egyptian_multiplication (The named method is a multiplication algorithm using doubling and adding; what we have here is a power algorithm using squaring and multiplying.)
              $endgroup$
              – Rosie F
              May 28 '18 at 17:48
















            12












            $begingroup$

            Here are two examples of the square and multiply method for $5^{69} bmod 101$:



            $$ begin{matrix}
            5^{69} &equiv& 5 &cdot &(5^{34})^2 &equiv & 37
            \ 5^{34} &equiv& &&(5^{17})^2 &equiv& 88 &(equiv -13)
            \ 5^{17} &equiv& 5 &cdot &(5^8)^2 &equiv& 54
            \ 5^{8} &equiv& &&(5^4)^2 &equiv& 58
            \ 5^{4} &equiv& &&(5^2)^2 &equiv& 19
            \ 5^{2} &equiv& &&(5^1)^2 &equiv& 25
            \ 5^{1} &equiv& 5 &cdot &(1)^2 &equiv& 5
            end{matrix} $$



            The computation proceeds by starting with $5^{69}$ and then working downward to create the first two columns, then computing the results from the bottom up. (normally you'd skip the last line; I put it there to clarify the next paragraph)



            As a shortcut, the binary representation of $69$ is $1000101_2$; reading the binary digits from left to right tell us the operations to do starting from the value $1$: $0$ says "square" and $1$ says "square and multiply by $5$".





            The other way is to compute a list of repeated squares:



            $$ begin{matrix}
            5^1 &equiv& 5
            \ 5^2 &equiv& 25
            \ 5^4 &equiv& 19
            \ 5^8 &equiv& 58
            \ 5^{16} &equiv& 31
            \ 5^{32} &equiv& 52
            \ 5^{64} &equiv& 78
            end{matrix} $$



            Then work out which terms you need to multiply together:



            $$ 5^{69} equiv 5^{64 + 4 + 1} equiv 78 cdot 19 cdot 5 equiv 37 $$






            share|cite|improve this answer











            $endgroup$









            • 1




              $begingroup$
              Good to have an example of square-and-multiply at hand.
              $endgroup$
              – Jyrki Lahtonen
              Jun 9 '16 at 9:23






            • 1




              $begingroup$
              If memory serves, this is sometimes referred to as the "Russian peasant" method.
              $endgroup$
              – J. M. is not a mathematician
              Jun 9 '16 at 10:20










            • $begingroup$
              @J.M.isnotamathematician It is closer to $a$ to the power of the "Russian peasant" method. en.wikipedia.org/wiki/Ancient_Egyptian_multiplication (The named method is a multiplication algorithm using doubling and adding; what we have here is a power algorithm using squaring and multiplying.)
              $endgroup$
              – Rosie F
              May 28 '18 at 17:48














            12












            12








            12





            $begingroup$

            Here are two examples of the square and multiply method for $5^{69} bmod 101$:



            $$ begin{matrix}
            5^{69} &equiv& 5 &cdot &(5^{34})^2 &equiv & 37
            \ 5^{34} &equiv& &&(5^{17})^2 &equiv& 88 &(equiv -13)
            \ 5^{17} &equiv& 5 &cdot &(5^8)^2 &equiv& 54
            \ 5^{8} &equiv& &&(5^4)^2 &equiv& 58
            \ 5^{4} &equiv& &&(5^2)^2 &equiv& 19
            \ 5^{2} &equiv& &&(5^1)^2 &equiv& 25
            \ 5^{1} &equiv& 5 &cdot &(1)^2 &equiv& 5
            end{matrix} $$



            The computation proceeds by starting with $5^{69}$ and then working downward to create the first two columns, then computing the results from the bottom up. (normally you'd skip the last line; I put it there to clarify the next paragraph)



            As a shortcut, the binary representation of $69$ is $1000101_2$; reading the binary digits from left to right tell us the operations to do starting from the value $1$: $0$ says "square" and $1$ says "square and multiply by $5$".





            The other way is to compute a list of repeated squares:



            $$ begin{matrix}
            5^1 &equiv& 5
            \ 5^2 &equiv& 25
            \ 5^4 &equiv& 19
            \ 5^8 &equiv& 58
            \ 5^{16} &equiv& 31
            \ 5^{32} &equiv& 52
            \ 5^{64} &equiv& 78
            end{matrix} $$



            Then work out which terms you need to multiply together:



            $$ 5^{69} equiv 5^{64 + 4 + 1} equiv 78 cdot 19 cdot 5 equiv 37 $$






            share|cite|improve this answer











            $endgroup$



            Here are two examples of the square and multiply method for $5^{69} bmod 101$:



            $$ begin{matrix}
            5^{69} &equiv& 5 &cdot &(5^{34})^2 &equiv & 37
            \ 5^{34} &equiv& &&(5^{17})^2 &equiv& 88 &(equiv -13)
            \ 5^{17} &equiv& 5 &cdot &(5^8)^2 &equiv& 54
            \ 5^{8} &equiv& &&(5^4)^2 &equiv& 58
            \ 5^{4} &equiv& &&(5^2)^2 &equiv& 19
            \ 5^{2} &equiv& &&(5^1)^2 &equiv& 25
            \ 5^{1} &equiv& 5 &cdot &(1)^2 &equiv& 5
            end{matrix} $$



            The computation proceeds by starting with $5^{69}$ and then working downward to create the first two columns, then computing the results from the bottom up. (normally you'd skip the last line; I put it there to clarify the next paragraph)



            As a shortcut, the binary representation of $69$ is $1000101_2$; reading the binary digits from left to right tell us the operations to do starting from the value $1$: $0$ says "square" and $1$ says "square and multiply by $5$".





            The other way is to compute a list of repeated squares:



            $$ begin{matrix}
            5^1 &equiv& 5
            \ 5^2 &equiv& 25
            \ 5^4 &equiv& 19
            \ 5^8 &equiv& 58
            \ 5^{16} &equiv& 31
            \ 5^{32} &equiv& 52
            \ 5^{64} &equiv& 78
            end{matrix} $$



            Then work out which terms you need to multiply together:



            $$ 5^{69} equiv 5^{64 + 4 + 1} equiv 78 cdot 19 cdot 5 equiv 37 $$







            share|cite|improve this answer














            share|cite|improve this answer



            share|cite|improve this answer








            edited Oct 6 '16 at 2:33









            Martin Sleziak

            44.8k9118272




            44.8k9118272










            answered Jun 9 '16 at 9:12









            HurkylHurkyl

            111k9119262




            111k9119262








            • 1




              $begingroup$
              Good to have an example of square-and-multiply at hand.
              $endgroup$
              – Jyrki Lahtonen
              Jun 9 '16 at 9:23






            • 1




              $begingroup$
              If memory serves, this is sometimes referred to as the "Russian peasant" method.
              $endgroup$
              – J. M. is not a mathematician
              Jun 9 '16 at 10:20










            • $begingroup$
              @J.M.isnotamathematician It is closer to $a$ to the power of the "Russian peasant" method. en.wikipedia.org/wiki/Ancient_Egyptian_multiplication (The named method is a multiplication algorithm using doubling and adding; what we have here is a power algorithm using squaring and multiplying.)
              $endgroup$
              – Rosie F
              May 28 '18 at 17:48














            • 1




              $begingroup$
              Good to have an example of square-and-multiply at hand.
              $endgroup$
              – Jyrki Lahtonen
              Jun 9 '16 at 9:23






            • 1




              $begingroup$
              If memory serves, this is sometimes referred to as the "Russian peasant" method.
              $endgroup$
              – J. M. is not a mathematician
              Jun 9 '16 at 10:20










            • $begingroup$
              @J.M.isnotamathematician It is closer to $a$ to the power of the "Russian peasant" method. en.wikipedia.org/wiki/Ancient_Egyptian_multiplication (The named method is a multiplication algorithm using doubling and adding; what we have here is a power algorithm using squaring and multiplying.)
              $endgroup$
              – Rosie F
              May 28 '18 at 17:48








            1




            1




            $begingroup$
            Good to have an example of square-and-multiply at hand.
            $endgroup$
            – Jyrki Lahtonen
            Jun 9 '16 at 9:23




            $begingroup$
            Good to have an example of square-and-multiply at hand.
            $endgroup$
            – Jyrki Lahtonen
            Jun 9 '16 at 9:23




            1




            1




            $begingroup$
            If memory serves, this is sometimes referred to as the "Russian peasant" method.
            $endgroup$
            – J. M. is not a mathematician
            Jun 9 '16 at 10:20




            $begingroup$
            If memory serves, this is sometimes referred to as the "Russian peasant" method.
            $endgroup$
            – J. M. is not a mathematician
            Jun 9 '16 at 10:20












            $begingroup$
            @J.M.isnotamathematician It is closer to $a$ to the power of the "Russian peasant" method. en.wikipedia.org/wiki/Ancient_Egyptian_multiplication (The named method is a multiplication algorithm using doubling and adding; what we have here is a power algorithm using squaring and multiplying.)
            $endgroup$
            – Rosie F
            May 28 '18 at 17:48




            $begingroup$
            @J.M.isnotamathematician It is closer to $a$ to the power of the "Russian peasant" method. en.wikipedia.org/wiki/Ancient_Egyptian_multiplication (The named method is a multiplication algorithm using doubling and adding; what we have here is a power algorithm using squaring and multiplying.)
            $endgroup$
            – Rosie F
            May 28 '18 at 17:48











            10












            $begingroup$

            Some tricks which are useful for modular exponentiation



            The intention of this post is to collect various tricks which can sometimes simplify computations of this type. (Especially when done by hand and not using computer or calculator.) This post is community-wiki, so feel free to edit it if you have some ideas for improvements.



            Using complement: $(c-a) equiv (-a) pmod c$



            If the given number is close to $c$ (but smaller than $c$), replacing it by $c-a$ my help us - we will work with smaller numbers. Some examples:




            • If we want to calculate $7^{777} bmod 50$, it is useful to notice that $7^2=49 equiv (-1) pmod{50}$, so we can replace $7^2$ by $-1$
              and get $7^{777} equiv 7^{388} cdot 7 equiv (-1)^{388} cdot 7 equiv 7 pmod{50}$. (This was part of Find $3^{333} + 7^{777}pmod{ 50}$.)

            • We want to calculate $50^{50} bmod 13$. Since $4cdot 13 = 52$, we have $50 equiv -2 pmod{13}$. So we can work with $-2$ instead of $50$, which will be easier, since it is a smaller number. How to use Fermat's little theorem to find $50^{50}pmod{13}$?


            If you can find a power which is close to the modulo, try to use it



            Some examples:




            • We want to calculate $6^{1000} bmod 23$. Since $6=2cdot 3$, let us have a look whether we can somehow combine these two numbers to get something with small remainder modulo $23$. We may notice that $24=2^3cdot 3 equiv 1pmod{23}$. We can also notice that $27 equiv 4pmod{23}$, i.e. $3^3equiv 2^2pmod{23}$. Replacing $2^2$ with $3^3$ in the previous congruence we get $2cdot 3^4 equiv 1 pmod{23}$. Now we can combine the preceding two congruences to get $1equiv (2^3cdot 3)^3cdot(2cdot 3^4)^2 = 2^{11}cdot3^{11} = 6^{11}pmod{23}$. Notice that the congruence $6^{11}equiv1pmod{23}$ can be obtained also by different means: Find $6^{1000} mod 23$

            • We want to find $5^{119} bmod 59$. This can be solved in a very simple way using Fermat's little theorem: Find the remainder using Fermat's little theorem when $5^{119}$ is divided by $59$? However, let us forget Fermat's little theorem and let us try to find some powers of $5$ which give small remainder modulo $59$. We may notice that $5^3$ is not too far from $2cdot59$ and get $5^3equiv125equiv7pmod{59}$. Similarly, $7cdot25$ seems to be not very far from $3cdot59$, so we can try $5^5=5^3cdot5^2equiv7cdot25equiv175equiv-2pmod{59}$. And now we can use that $64$ is a power of two which is close to our remainder to get $5^{30} = (5^5)^6 equiv (-2)^6 equiv 64 equiv 5 pmod{59}$. Since we have $5^{30}equiv5pmod{59}$ and $gcd(5,59)=1$, we can cancel $5$ on both sides to get $5^{29}equiv1pmod{59}$. And the last fact can be used in further computations.

            • The task is to find $16^{74} bmod 65$. One may notice that $64$ is a power of two which is very close to $65$. So we have $2^6 = 64 equiv -1 pmod{65}$, meaning that $16^{74}=(2^4)^{74}=2^{296} = 2^{6cdot49}cdot2^2 equiv (-1)^{49}cdot4 equiv -1 pmod{65}$. See also https://math.stackexchange.com/questions/2077609/computing-1674-bmod-65.


            Using Euler's criterion



            Euler's criterion can tell us about value of $a^{frac{p-1}2}$ modulo a prime $p$. However, we need to know whether $a$ is a quadratic residue modulo $p$. For some numbers this can be guessed. Sometimes this can be checked using quadratic reciprocity (Of course, this is not much of an improvement in comparison with Fermat's little theorem, which gives us $a^{p-1}equiv1pmod p$.)




            • Let us have a look at $5^{29} bmod 59$ (we have already computed this using different computations above). It is easy to notice that $8^2=64equiv5pmod{59}$, so $5$ is a quadratic residue modulo $59$. So from Euler's criterion we get $5^{29}=5^{(59-1)/2}equiv1pmod{29}$.






            share|cite|improve this answer











            $endgroup$


















              10












              $begingroup$

              Some tricks which are useful for modular exponentiation



              The intention of this post is to collect various tricks which can sometimes simplify computations of this type. (Especially when done by hand and not using computer or calculator.) This post is community-wiki, so feel free to edit it if you have some ideas for improvements.



              Using complement: $(c-a) equiv (-a) pmod c$



              If the given number is close to $c$ (but smaller than $c$), replacing it by $c-a$ my help us - we will work with smaller numbers. Some examples:




              • If we want to calculate $7^{777} bmod 50$, it is useful to notice that $7^2=49 equiv (-1) pmod{50}$, so we can replace $7^2$ by $-1$
                and get $7^{777} equiv 7^{388} cdot 7 equiv (-1)^{388} cdot 7 equiv 7 pmod{50}$. (This was part of Find $3^{333} + 7^{777}pmod{ 50}$.)

              • We want to calculate $50^{50} bmod 13$. Since $4cdot 13 = 52$, we have $50 equiv -2 pmod{13}$. So we can work with $-2$ instead of $50$, which will be easier, since it is a smaller number. How to use Fermat's little theorem to find $50^{50}pmod{13}$?


              If you can find a power which is close to the modulo, try to use it



              Some examples:




              • We want to calculate $6^{1000} bmod 23$. Since $6=2cdot 3$, let us have a look whether we can somehow combine these two numbers to get something with small remainder modulo $23$. We may notice that $24=2^3cdot 3 equiv 1pmod{23}$. We can also notice that $27 equiv 4pmod{23}$, i.e. $3^3equiv 2^2pmod{23}$. Replacing $2^2$ with $3^3$ in the previous congruence we get $2cdot 3^4 equiv 1 pmod{23}$. Now we can combine the preceding two congruences to get $1equiv (2^3cdot 3)^3cdot(2cdot 3^4)^2 = 2^{11}cdot3^{11} = 6^{11}pmod{23}$. Notice that the congruence $6^{11}equiv1pmod{23}$ can be obtained also by different means: Find $6^{1000} mod 23$

              • We want to find $5^{119} bmod 59$. This can be solved in a very simple way using Fermat's little theorem: Find the remainder using Fermat's little theorem when $5^{119}$ is divided by $59$? However, let us forget Fermat's little theorem and let us try to find some powers of $5$ which give small remainder modulo $59$. We may notice that $5^3$ is not too far from $2cdot59$ and get $5^3equiv125equiv7pmod{59}$. Similarly, $7cdot25$ seems to be not very far from $3cdot59$, so we can try $5^5=5^3cdot5^2equiv7cdot25equiv175equiv-2pmod{59}$. And now we can use that $64$ is a power of two which is close to our remainder to get $5^{30} = (5^5)^6 equiv (-2)^6 equiv 64 equiv 5 pmod{59}$. Since we have $5^{30}equiv5pmod{59}$ and $gcd(5,59)=1$, we can cancel $5$ on both sides to get $5^{29}equiv1pmod{59}$. And the last fact can be used in further computations.

              • The task is to find $16^{74} bmod 65$. One may notice that $64$ is a power of two which is very close to $65$. So we have $2^6 = 64 equiv -1 pmod{65}$, meaning that $16^{74}=(2^4)^{74}=2^{296} = 2^{6cdot49}cdot2^2 equiv (-1)^{49}cdot4 equiv -1 pmod{65}$. See also https://math.stackexchange.com/questions/2077609/computing-1674-bmod-65.


              Using Euler's criterion



              Euler's criterion can tell us about value of $a^{frac{p-1}2}$ modulo a prime $p$. However, we need to know whether $a$ is a quadratic residue modulo $p$. For some numbers this can be guessed. Sometimes this can be checked using quadratic reciprocity (Of course, this is not much of an improvement in comparison with Fermat's little theorem, which gives us $a^{p-1}equiv1pmod p$.)




              • Let us have a look at $5^{29} bmod 59$ (we have already computed this using different computations above). It is easy to notice that $8^2=64equiv5pmod{59}$, so $5$ is a quadratic residue modulo $59$. So from Euler's criterion we get $5^{29}=5^{(59-1)/2}equiv1pmod{29}$.






              share|cite|improve this answer











              $endgroup$
















                10












                10








                10





                $begingroup$

                Some tricks which are useful for modular exponentiation



                The intention of this post is to collect various tricks which can sometimes simplify computations of this type. (Especially when done by hand and not using computer or calculator.) This post is community-wiki, so feel free to edit it if you have some ideas for improvements.



                Using complement: $(c-a) equiv (-a) pmod c$



                If the given number is close to $c$ (but smaller than $c$), replacing it by $c-a$ my help us - we will work with smaller numbers. Some examples:




                • If we want to calculate $7^{777} bmod 50$, it is useful to notice that $7^2=49 equiv (-1) pmod{50}$, so we can replace $7^2$ by $-1$
                  and get $7^{777} equiv 7^{388} cdot 7 equiv (-1)^{388} cdot 7 equiv 7 pmod{50}$. (This was part of Find $3^{333} + 7^{777}pmod{ 50}$.)

                • We want to calculate $50^{50} bmod 13$. Since $4cdot 13 = 52$, we have $50 equiv -2 pmod{13}$. So we can work with $-2$ instead of $50$, which will be easier, since it is a smaller number. How to use Fermat's little theorem to find $50^{50}pmod{13}$?


                If you can find a power which is close to the modulo, try to use it



                Some examples:




                • We want to calculate $6^{1000} bmod 23$. Since $6=2cdot 3$, let us have a look whether we can somehow combine these two numbers to get something with small remainder modulo $23$. We may notice that $24=2^3cdot 3 equiv 1pmod{23}$. We can also notice that $27 equiv 4pmod{23}$, i.e. $3^3equiv 2^2pmod{23}$. Replacing $2^2$ with $3^3$ in the previous congruence we get $2cdot 3^4 equiv 1 pmod{23}$. Now we can combine the preceding two congruences to get $1equiv (2^3cdot 3)^3cdot(2cdot 3^4)^2 = 2^{11}cdot3^{11} = 6^{11}pmod{23}$. Notice that the congruence $6^{11}equiv1pmod{23}$ can be obtained also by different means: Find $6^{1000} mod 23$

                • We want to find $5^{119} bmod 59$. This can be solved in a very simple way using Fermat's little theorem: Find the remainder using Fermat's little theorem when $5^{119}$ is divided by $59$? However, let us forget Fermat's little theorem and let us try to find some powers of $5$ which give small remainder modulo $59$. We may notice that $5^3$ is not too far from $2cdot59$ and get $5^3equiv125equiv7pmod{59}$. Similarly, $7cdot25$ seems to be not very far from $3cdot59$, so we can try $5^5=5^3cdot5^2equiv7cdot25equiv175equiv-2pmod{59}$. And now we can use that $64$ is a power of two which is close to our remainder to get $5^{30} = (5^5)^6 equiv (-2)^6 equiv 64 equiv 5 pmod{59}$. Since we have $5^{30}equiv5pmod{59}$ and $gcd(5,59)=1$, we can cancel $5$ on both sides to get $5^{29}equiv1pmod{59}$. And the last fact can be used in further computations.

                • The task is to find $16^{74} bmod 65$. One may notice that $64$ is a power of two which is very close to $65$. So we have $2^6 = 64 equiv -1 pmod{65}$, meaning that $16^{74}=(2^4)^{74}=2^{296} = 2^{6cdot49}cdot2^2 equiv (-1)^{49}cdot4 equiv -1 pmod{65}$. See also https://math.stackexchange.com/questions/2077609/computing-1674-bmod-65.


                Using Euler's criterion



                Euler's criterion can tell us about value of $a^{frac{p-1}2}$ modulo a prime $p$. However, we need to know whether $a$ is a quadratic residue modulo $p$. For some numbers this can be guessed. Sometimes this can be checked using quadratic reciprocity (Of course, this is not much of an improvement in comparison with Fermat's little theorem, which gives us $a^{p-1}equiv1pmod p$.)




                • Let us have a look at $5^{29} bmod 59$ (we have already computed this using different computations above). It is easy to notice that $8^2=64equiv5pmod{59}$, so $5$ is a quadratic residue modulo $59$. So from Euler's criterion we get $5^{29}=5^{(59-1)/2}equiv1pmod{29}$.






                share|cite|improve this answer











                $endgroup$



                Some tricks which are useful for modular exponentiation



                The intention of this post is to collect various tricks which can sometimes simplify computations of this type. (Especially when done by hand and not using computer or calculator.) This post is community-wiki, so feel free to edit it if you have some ideas for improvements.



                Using complement: $(c-a) equiv (-a) pmod c$



                If the given number is close to $c$ (but smaller than $c$), replacing it by $c-a$ my help us - we will work with smaller numbers. Some examples:




                • If we want to calculate $7^{777} bmod 50$, it is useful to notice that $7^2=49 equiv (-1) pmod{50}$, so we can replace $7^2$ by $-1$
                  and get $7^{777} equiv 7^{388} cdot 7 equiv (-1)^{388} cdot 7 equiv 7 pmod{50}$. (This was part of Find $3^{333} + 7^{777}pmod{ 50}$.)

                • We want to calculate $50^{50} bmod 13$. Since $4cdot 13 = 52$, we have $50 equiv -2 pmod{13}$. So we can work with $-2$ instead of $50$, which will be easier, since it is a smaller number. How to use Fermat's little theorem to find $50^{50}pmod{13}$?


                If you can find a power which is close to the modulo, try to use it



                Some examples:




                • We want to calculate $6^{1000} bmod 23$. Since $6=2cdot 3$, let us have a look whether we can somehow combine these two numbers to get something with small remainder modulo $23$. We may notice that $24=2^3cdot 3 equiv 1pmod{23}$. We can also notice that $27 equiv 4pmod{23}$, i.e. $3^3equiv 2^2pmod{23}$. Replacing $2^2$ with $3^3$ in the previous congruence we get $2cdot 3^4 equiv 1 pmod{23}$. Now we can combine the preceding two congruences to get $1equiv (2^3cdot 3)^3cdot(2cdot 3^4)^2 = 2^{11}cdot3^{11} = 6^{11}pmod{23}$. Notice that the congruence $6^{11}equiv1pmod{23}$ can be obtained also by different means: Find $6^{1000} mod 23$

                • We want to find $5^{119} bmod 59$. This can be solved in a very simple way using Fermat's little theorem: Find the remainder using Fermat's little theorem when $5^{119}$ is divided by $59$? However, let us forget Fermat's little theorem and let us try to find some powers of $5$ which give small remainder modulo $59$. We may notice that $5^3$ is not too far from $2cdot59$ and get $5^3equiv125equiv7pmod{59}$. Similarly, $7cdot25$ seems to be not very far from $3cdot59$, so we can try $5^5=5^3cdot5^2equiv7cdot25equiv175equiv-2pmod{59}$. And now we can use that $64$ is a power of two which is close to our remainder to get $5^{30} = (5^5)^6 equiv (-2)^6 equiv 64 equiv 5 pmod{59}$. Since we have $5^{30}equiv5pmod{59}$ and $gcd(5,59)=1$, we can cancel $5$ on both sides to get $5^{29}equiv1pmod{59}$. And the last fact can be used in further computations.

                • The task is to find $16^{74} bmod 65$. One may notice that $64$ is a power of two which is very close to $65$. So we have $2^6 = 64 equiv -1 pmod{65}$, meaning that $16^{74}=(2^4)^{74}=2^{296} = 2^{6cdot49}cdot2^2 equiv (-1)^{49}cdot4 equiv -1 pmod{65}$. See also https://math.stackexchange.com/questions/2077609/computing-1674-bmod-65.


                Using Euler's criterion



                Euler's criterion can tell us about value of $a^{frac{p-1}2}$ modulo a prime $p$. However, we need to know whether $a$ is a quadratic residue modulo $p$. For some numbers this can be guessed. Sometimes this can be checked using quadratic reciprocity (Of course, this is not much of an improvement in comparison with Fermat's little theorem, which gives us $a^{p-1}equiv1pmod p$.)




                • Let us have a look at $5^{29} bmod 59$ (we have already computed this using different computations above). It is easy to notice that $8^2=64equiv5pmod{59}$, so $5$ is a quadratic residue modulo $59$. So from Euler's criterion we get $5^{29}=5^{(59-1)/2}equiv1pmod{29}$.







                share|cite|improve this answer














                share|cite|improve this answer



                share|cite|improve this answer








                edited Apr 13 '17 at 12:20


























                community wiki





                6 revs, 2 users 90%
                Martin Sleziak
























                    6












                    $begingroup$

                    In general, squared exponentiation is used, this is $O(log(b) cdot log(n))$ if multiplication $bmod n$ is $O(log (n))$.



                    powmod(a,b,n){
                    res=1;
                    fact=a;
                    while(b>0){
                    res=(res*(b%2)==1?fact:1)%n;
                    fact=(fact*fact)%n;
                    b=floor(b/2);
                    }
                    }


                    when $b$ is huge (much larger than $n$) you can (attempt) to find the rank of the ring ($varphi(n)$) and find the remainder of $b pmod {varphi(n)}$ because $a^b bmod n= a^{b mod varphi(n)} bmod n$ (for $21$, it is $(3-1) cdot (7-1)=12$) this requires finding the prime factors of $n$.



                    In general the rank for $n = prod{(p_i)^{k_i-1} cdot (p_i-1)}$ with $p_i^{k_i}$ the prime factors of $n$.






                    share|cite|improve this answer











                    $endgroup$


















                      6












                      $begingroup$

                      In general, squared exponentiation is used, this is $O(log(b) cdot log(n))$ if multiplication $bmod n$ is $O(log (n))$.



                      powmod(a,b,n){
                      res=1;
                      fact=a;
                      while(b>0){
                      res=(res*(b%2)==1?fact:1)%n;
                      fact=(fact*fact)%n;
                      b=floor(b/2);
                      }
                      }


                      when $b$ is huge (much larger than $n$) you can (attempt) to find the rank of the ring ($varphi(n)$) and find the remainder of $b pmod {varphi(n)}$ because $a^b bmod n= a^{b mod varphi(n)} bmod n$ (for $21$, it is $(3-1) cdot (7-1)=12$) this requires finding the prime factors of $n$.



                      In general the rank for $n = prod{(p_i)^{k_i-1} cdot (p_i-1)}$ with $p_i^{k_i}$ the prime factors of $n$.






                      share|cite|improve this answer











                      $endgroup$
















                        6












                        6








                        6





                        $begingroup$

                        In general, squared exponentiation is used, this is $O(log(b) cdot log(n))$ if multiplication $bmod n$ is $O(log (n))$.



                        powmod(a,b,n){
                        res=1;
                        fact=a;
                        while(b>0){
                        res=(res*(b%2)==1?fact:1)%n;
                        fact=(fact*fact)%n;
                        b=floor(b/2);
                        }
                        }


                        when $b$ is huge (much larger than $n$) you can (attempt) to find the rank of the ring ($varphi(n)$) and find the remainder of $b pmod {varphi(n)}$ because $a^b bmod n= a^{b mod varphi(n)} bmod n$ (for $21$, it is $(3-1) cdot (7-1)=12$) this requires finding the prime factors of $n$.



                        In general the rank for $n = prod{(p_i)^{k_i-1} cdot (p_i-1)}$ with $p_i^{k_i}$ the prime factors of $n$.






                        share|cite|improve this answer











                        $endgroup$



                        In general, squared exponentiation is used, this is $O(log(b) cdot log(n))$ if multiplication $bmod n$ is $O(log (n))$.



                        powmod(a,b,n){
                        res=1;
                        fact=a;
                        while(b>0){
                        res=(res*(b%2)==1?fact:1)%n;
                        fact=(fact*fact)%n;
                        b=floor(b/2);
                        }
                        }


                        when $b$ is huge (much larger than $n$) you can (attempt) to find the rank of the ring ($varphi(n)$) and find the remainder of $b pmod {varphi(n)}$ because $a^b bmod n= a^{b mod varphi(n)} bmod n$ (for $21$, it is $(3-1) cdot (7-1)=12$) this requires finding the prime factors of $n$.



                        In general the rank for $n = prod{(p_i)^{k_i-1} cdot (p_i-1)}$ with $p_i^{k_i}$ the prime factors of $n$.







                        share|cite|improve this answer














                        share|cite|improve this answer



                        share|cite|improve this answer








                        edited Nov 12 '11 at 3:46









                        Srivatsan

                        20.9k371126




                        20.9k371126










                        answered Nov 11 '11 at 22:34









                        ratchet freakratchet freak

                        1,67511015




                        1,67511015























                            6












                            $begingroup$

                            The Chinese remainder theorem can reduce the computation needed. For example, we can factor $21 = 3 cdot 7$, and have



                            $$ 1 cdot 7 - 2 cdot 3 = 1$$



                            (in general, we can use the extended Euclidean algorithm to produce this formula)



                            Consequently, if



                            $$x equiv a pmod 3 qquad x equiv b pmod 7 $$



                            then



                            $$ x equiv a cdot (1 cdot 7 ) + b cdot (-2 cdot 3) pmod{21} $$



                            Thus, we can compute $5^{844325} bmod 21$ by using our favorite means to compute:



                            $$ 5^{844325} equiv 2 pmod 3 qquad 5^{844325} equiv 3 pmod 7 $$



                            and thus



                            $$ 5^{844325} equiv 2 cdot 7 + 3 cdot (-6) equiv -4 equiv 17 pmod{21} $$






                            share|cite|improve this answer









                            $endgroup$


















                              6












                              $begingroup$

                              The Chinese remainder theorem can reduce the computation needed. For example, we can factor $21 = 3 cdot 7$, and have



                              $$ 1 cdot 7 - 2 cdot 3 = 1$$



                              (in general, we can use the extended Euclidean algorithm to produce this formula)



                              Consequently, if



                              $$x equiv a pmod 3 qquad x equiv b pmod 7 $$



                              then



                              $$ x equiv a cdot (1 cdot 7 ) + b cdot (-2 cdot 3) pmod{21} $$



                              Thus, we can compute $5^{844325} bmod 21$ by using our favorite means to compute:



                              $$ 5^{844325} equiv 2 pmod 3 qquad 5^{844325} equiv 3 pmod 7 $$



                              and thus



                              $$ 5^{844325} equiv 2 cdot 7 + 3 cdot (-6) equiv -4 equiv 17 pmod{21} $$






                              share|cite|improve this answer









                              $endgroup$
















                                6












                                6








                                6





                                $begingroup$

                                The Chinese remainder theorem can reduce the computation needed. For example, we can factor $21 = 3 cdot 7$, and have



                                $$ 1 cdot 7 - 2 cdot 3 = 1$$



                                (in general, we can use the extended Euclidean algorithm to produce this formula)



                                Consequently, if



                                $$x equiv a pmod 3 qquad x equiv b pmod 7 $$



                                then



                                $$ x equiv a cdot (1 cdot 7 ) + b cdot (-2 cdot 3) pmod{21} $$



                                Thus, we can compute $5^{844325} bmod 21$ by using our favorite means to compute:



                                $$ 5^{844325} equiv 2 pmod 3 qquad 5^{844325} equiv 3 pmod 7 $$



                                and thus



                                $$ 5^{844325} equiv 2 cdot 7 + 3 cdot (-6) equiv -4 equiv 17 pmod{21} $$






                                share|cite|improve this answer









                                $endgroup$



                                The Chinese remainder theorem can reduce the computation needed. For example, we can factor $21 = 3 cdot 7$, and have



                                $$ 1 cdot 7 - 2 cdot 3 = 1$$



                                (in general, we can use the extended Euclidean algorithm to produce this formula)



                                Consequently, if



                                $$x equiv a pmod 3 qquad x equiv b pmod 7 $$



                                then



                                $$ x equiv a cdot (1 cdot 7 ) + b cdot (-2 cdot 3) pmod{21} $$



                                Thus, we can compute $5^{844325} bmod 21$ by using our favorite means to compute:



                                $$ 5^{844325} equiv 2 pmod 3 qquad 5^{844325} equiv 3 pmod 7 $$



                                and thus



                                $$ 5^{844325} equiv 2 cdot 7 + 3 cdot (-6) equiv -4 equiv 17 pmod{21} $$







                                share|cite|improve this answer












                                share|cite|improve this answer



                                share|cite|improve this answer










                                answered Jun 9 '16 at 9:21









                                HurkylHurkyl

                                111k9119262




                                111k9119262























                                    4












                                    $begingroup$

                                    For the first question: use $a^{Phi(c)}=1 mod c$, where $Phi(c)$ is the number of coprimes to $c$ below $c$. For $c=21=7cdot 3$ we have $Phi(c)=(7-1)cdot(3-1)=12$



                                    second question: Use $a^4=(a^2)^2, a^8=(a^4)^2$ and so on. Decompose the exponent into powers of 2 and combine them using $a^ncdot a^m=a^{n+m}$ E.g. $a^{69}=a^{64}cdot a^4cdot a^1$






                                    share|cite|improve this answer











                                    $endgroup$


















                                      4












                                      $begingroup$

                                      For the first question: use $a^{Phi(c)}=1 mod c$, where $Phi(c)$ is the number of coprimes to $c$ below $c$. For $c=21=7cdot 3$ we have $Phi(c)=(7-1)cdot(3-1)=12$



                                      second question: Use $a^4=(a^2)^2, a^8=(a^4)^2$ and so on. Decompose the exponent into powers of 2 and combine them using $a^ncdot a^m=a^{n+m}$ E.g. $a^{69}=a^{64}cdot a^4cdot a^1$






                                      share|cite|improve this answer











                                      $endgroup$
















                                        4












                                        4








                                        4





                                        $begingroup$

                                        For the first question: use $a^{Phi(c)}=1 mod c$, where $Phi(c)$ is the number of coprimes to $c$ below $c$. For $c=21=7cdot 3$ we have $Phi(c)=(7-1)cdot(3-1)=12$



                                        second question: Use $a^4=(a^2)^2, a^8=(a^4)^2$ and so on. Decompose the exponent into powers of 2 and combine them using $a^ncdot a^m=a^{n+m}$ E.g. $a^{69}=a^{64}cdot a^4cdot a^1$






                                        share|cite|improve this answer











                                        $endgroup$



                                        For the first question: use $a^{Phi(c)}=1 mod c$, where $Phi(c)$ is the number of coprimes to $c$ below $c$. For $c=21=7cdot 3$ we have $Phi(c)=(7-1)cdot(3-1)=12$



                                        second question: Use $a^4=(a^2)^2, a^8=(a^4)^2$ and so on. Decompose the exponent into powers of 2 and combine them using $a^ncdot a^m=a^{n+m}$ E.g. $a^{69}=a^{64}cdot a^4cdot a^1$







                                        share|cite|improve this answer














                                        share|cite|improve this answer



                                        share|cite|improve this answer








                                        edited Jul 31 '12 at 6:44









                                        Norbert

                                        45.8k774161




                                        45.8k774161










                                        answered Nov 11 '11 at 22:31









                                        MaxMax

                                        511




                                        511























                                            -1












                                            $begingroup$

                                            Its not hard to show that the sequence



                                            $$
                                            x_n=a^nmod{c}
                                            $$



                                            is periodic, with period $p$ (which is at most $c$). Evaluate the first few terms to get the period ${x_0,x_1,dots,x_{p-1}}$. Then you can evaluate for any huge power $n$ as



                                            $$
                                            x_n=x_{nmod{p}}
                                            $$






                                            share|cite|improve this answer









                                            $endgroup$


















                                              -1












                                              $begingroup$

                                              Its not hard to show that the sequence



                                              $$
                                              x_n=a^nmod{c}
                                              $$



                                              is periodic, with period $p$ (which is at most $c$). Evaluate the first few terms to get the period ${x_0,x_1,dots,x_{p-1}}$. Then you can evaluate for any huge power $n$ as



                                              $$
                                              x_n=x_{nmod{p}}
                                              $$






                                              share|cite|improve this answer









                                              $endgroup$
















                                                -1












                                                -1








                                                -1





                                                $begingroup$

                                                Its not hard to show that the sequence



                                                $$
                                                x_n=a^nmod{c}
                                                $$



                                                is periodic, with period $p$ (which is at most $c$). Evaluate the first few terms to get the period ${x_0,x_1,dots,x_{p-1}}$. Then you can evaluate for any huge power $n$ as



                                                $$
                                                x_n=x_{nmod{p}}
                                                $$






                                                share|cite|improve this answer









                                                $endgroup$



                                                Its not hard to show that the sequence



                                                $$
                                                x_n=a^nmod{c}
                                                $$



                                                is periodic, with period $p$ (which is at most $c$). Evaluate the first few terms to get the period ${x_0,x_1,dots,x_{p-1}}$. Then you can evaluate for any huge power $n$ as



                                                $$
                                                x_n=x_{nmod{p}}
                                                $$







                                                share|cite|improve this answer












                                                share|cite|improve this answer



                                                share|cite|improve this answer










                                                answered Dec 10 '18 at 9:07









                                                plus1plus1

                                                3911




                                                3911






























                                                    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%2f81228%2fhow-do-i-compute-ab-bmod-c-by-hand%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

                                                    Ellipse (mathématiques)

                                                    Quarter-circle Tiles

                                                    Mont Emei