Remainder on division with $22$












8












$begingroup$


What is the remainder obtained when $14^{16}$ is divided with $22$?



Is there a general method for this, without using number theory? I wish to solve this question using binomial theorem only - maybe expressing the numerator as a summation in which most terms are divisible by $22$, except the remainder?



How should I proceed?










share|cite|improve this question











$endgroup$












  • $begingroup$
    $14^{16} = (22 - 8)^{16}$
    $endgroup$
    – ab123
    Jul 3 '18 at 10:37












  • $begingroup$
    $8^{16} = 64^8 = (66 - 2)^8$
    $endgroup$
    – ab123
    Jul 3 '18 at 10:41








  • 7




    $begingroup$
    @ab123 Why not make an answer of that?
    $endgroup$
    – Arthur
    Jul 3 '18 at 10:41
















8












$begingroup$


What is the remainder obtained when $14^{16}$ is divided with $22$?



Is there a general method for this, without using number theory? I wish to solve this question using binomial theorem only - maybe expressing the numerator as a summation in which most terms are divisible by $22$, except the remainder?



How should I proceed?










share|cite|improve this question











$endgroup$












  • $begingroup$
    $14^{16} = (22 - 8)^{16}$
    $endgroup$
    – ab123
    Jul 3 '18 at 10:37












  • $begingroup$
    $8^{16} = 64^8 = (66 - 2)^8$
    $endgroup$
    – ab123
    Jul 3 '18 at 10:41








  • 7




    $begingroup$
    @ab123 Why not make an answer of that?
    $endgroup$
    – Arthur
    Jul 3 '18 at 10:41














8












8








8


1



$begingroup$


What is the remainder obtained when $14^{16}$ is divided with $22$?



Is there a general method for this, without using number theory? I wish to solve this question using binomial theorem only - maybe expressing the numerator as a summation in which most terms are divisible by $22$, except the remainder?



How should I proceed?










share|cite|improve this question











$endgroup$




What is the remainder obtained when $14^{16}$ is divided with $22$?



Is there a general method for this, without using number theory? I wish to solve this question using binomial theorem only - maybe expressing the numerator as a summation in which most terms are divisible by $22$, except the remainder?



How should I proceed?







number-theory elementary-number-theory modular-arithmetic divisibility binomial-theorem






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 12 at 6:10









Abcd

3,02821235




3,02821235










asked Jul 3 '18 at 10:32









arya_starkarya_stark

676218




676218












  • $begingroup$
    $14^{16} = (22 - 8)^{16}$
    $endgroup$
    – ab123
    Jul 3 '18 at 10:37












  • $begingroup$
    $8^{16} = 64^8 = (66 - 2)^8$
    $endgroup$
    – ab123
    Jul 3 '18 at 10:41








  • 7




    $begingroup$
    @ab123 Why not make an answer of that?
    $endgroup$
    – Arthur
    Jul 3 '18 at 10:41


















  • $begingroup$
    $14^{16} = (22 - 8)^{16}$
    $endgroup$
    – ab123
    Jul 3 '18 at 10:37












  • $begingroup$
    $8^{16} = 64^8 = (66 - 2)^8$
    $endgroup$
    – ab123
    Jul 3 '18 at 10:41








  • 7




    $begingroup$
    @ab123 Why not make an answer of that?
    $endgroup$
    – Arthur
    Jul 3 '18 at 10:41
















$begingroup$
$14^{16} = (22 - 8)^{16}$
$endgroup$
– ab123
Jul 3 '18 at 10:37






$begingroup$
$14^{16} = (22 - 8)^{16}$
$endgroup$
– ab123
Jul 3 '18 at 10:37














$begingroup$
$8^{16} = 64^8 = (66 - 2)^8$
$endgroup$
– ab123
Jul 3 '18 at 10:41






$begingroup$
$8^{16} = 64^8 = (66 - 2)^8$
$endgroup$
– ab123
Jul 3 '18 at 10:41






7




7




$begingroup$
@ab123 Why not make an answer of that?
$endgroup$
– Arthur
Jul 3 '18 at 10:41




$begingroup$
@ab123 Why not make an answer of that?
$endgroup$
– Arthur
Jul 3 '18 at 10:41










4 Answers
4






active

oldest

votes


















19












$begingroup$

You can use binomial expansions and see that
$$14^{16} = (22 - 8)^{16}$$
implies that the remainder is just the remainder when $(-8)^{16}( = 8^{16})$ is divided by $22.$
Proceeding similarly,



$8^{16} = 64^8 = (66 - 2)^8 implies 2^8 = 256 text{ divided by } 22 implies text{remainder = 14}$






share|cite|improve this answer











$endgroup$





















    7












    $begingroup$

    Since $$ 14^2 equiv -2 $$ so $$14^{16} equiv (-2)^8 equiv 16^2equiv (-6)^2 equiv 14$$





    or



    $$ 14^2 = 22k -2 $$ so $$14^{16} = (22k-2)^8 = 22l+2^8=22l+22cdot 11+14$$






    share|cite|improve this answer











    $endgroup$





















      3












      $begingroup$

      A method that uses FLT.



      Finding the remainder on dividing $14^{16}$ by $22$ is equivalent to twice that on dividing $7cdot14^{15}$ by $11$.



      By FLT, $14^{10}equiv1pmod{11}$ so $$7cdot14^{15}equiv7cdot14^5equiv98cdot196cdot196equiv-1cdot(-2)cdot(-2)equiv-4equiv7pmod{11}$$ hence the required remainder is $7times 2=14$.






      share|cite|improve this answer









      $endgroup$





















        2












        $begingroup$

        Using the Euclidean Algorithm



        Note that
        $$
        begin{align}
        14^{16}&equiv0&pmod2tag1
        end{align}
        $$
        Reducing mod $11$ and using Fermat's Little Theorem, we get
        $$
        begin{align}
        14^{16}
        &equiv3^6&pmod{11}\
        &equiv3&pmod{11}tag2
        end{align}
        $$
        Solving $11a+2b=1$ using the Euclidean Algorithm as implemented in this answer,
        $$
        begin{array}{r}
        &&5&2\hline
        1&0&1&-2\
        0&1&-5&11\
        11&2&1&0\
        end{array}tag3
        $$
        we have
        $$
        11(1)+2(-5)=1tag4
        $$
        from which we get
        $$
        begin{align}
        -10&equiv0&pmod2\
        -10&equiv1&pmod{11}
        end{align}tag5
        $$
        Multiplying $(5)$ by $3$ gives
        $$
        begin{align}
        -30&equiv0&pmod2\
        -30&equiv3&pmod{11}
        end{align}tag6
        $$





        Using the Chinese Remainder Theorem



        The Chinese Remainder Theorem says that the solution to $(6)$ is unique mod ${22}$. Thus, we get the smallest positive solution to be
        $$
        begin{align}
        14&equiv0&pmod2\
        14&equiv3&pmod{11}
        end{align}tag7
        $$
        Thus, $(1)$, $(2)$, and $(7)$ yields
        $$
        begin{align}
        14^{16}&equiv14&pmod{22}tag8
        end{align}
        $$






        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%2f2839477%2fremainder-on-division-with-22%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          4 Answers
          4






          active

          oldest

          votes








          4 Answers
          4






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          19












          $begingroup$

          You can use binomial expansions and see that
          $$14^{16} = (22 - 8)^{16}$$
          implies that the remainder is just the remainder when $(-8)^{16}( = 8^{16})$ is divided by $22.$
          Proceeding similarly,



          $8^{16} = 64^8 = (66 - 2)^8 implies 2^8 = 256 text{ divided by } 22 implies text{remainder = 14}$






          share|cite|improve this answer











          $endgroup$


















            19












            $begingroup$

            You can use binomial expansions and see that
            $$14^{16} = (22 - 8)^{16}$$
            implies that the remainder is just the remainder when $(-8)^{16}( = 8^{16})$ is divided by $22.$
            Proceeding similarly,



            $8^{16} = 64^8 = (66 - 2)^8 implies 2^8 = 256 text{ divided by } 22 implies text{remainder = 14}$






            share|cite|improve this answer











            $endgroup$
















              19












              19








              19





              $begingroup$

              You can use binomial expansions and see that
              $$14^{16} = (22 - 8)^{16}$$
              implies that the remainder is just the remainder when $(-8)^{16}( = 8^{16})$ is divided by $22.$
              Proceeding similarly,



              $8^{16} = 64^8 = (66 - 2)^8 implies 2^8 = 256 text{ divided by } 22 implies text{remainder = 14}$






              share|cite|improve this answer











              $endgroup$



              You can use binomial expansions and see that
              $$14^{16} = (22 - 8)^{16}$$
              implies that the remainder is just the remainder when $(-8)^{16}( = 8^{16})$ is divided by $22.$
              Proceeding similarly,



              $8^{16} = 64^8 = (66 - 2)^8 implies 2^8 = 256 text{ divided by } 22 implies text{remainder = 14}$







              share|cite|improve this answer














              share|cite|improve this answer



              share|cite|improve this answer








              edited Jul 3 '18 at 10:48

























              answered Jul 3 '18 at 10:45









              ab123ab123

              1,654423




              1,654423























                  7












                  $begingroup$

                  Since $$ 14^2 equiv -2 $$ so $$14^{16} equiv (-2)^8 equiv 16^2equiv (-6)^2 equiv 14$$





                  or



                  $$ 14^2 = 22k -2 $$ so $$14^{16} = (22k-2)^8 = 22l+2^8=22l+22cdot 11+14$$






                  share|cite|improve this answer











                  $endgroup$


















                    7












                    $begingroup$

                    Since $$ 14^2 equiv -2 $$ so $$14^{16} equiv (-2)^8 equiv 16^2equiv (-6)^2 equiv 14$$





                    or



                    $$ 14^2 = 22k -2 $$ so $$14^{16} = (22k-2)^8 = 22l+2^8=22l+22cdot 11+14$$






                    share|cite|improve this answer











                    $endgroup$
















                      7












                      7








                      7





                      $begingroup$

                      Since $$ 14^2 equiv -2 $$ so $$14^{16} equiv (-2)^8 equiv 16^2equiv (-6)^2 equiv 14$$





                      or



                      $$ 14^2 = 22k -2 $$ so $$14^{16} = (22k-2)^8 = 22l+2^8=22l+22cdot 11+14$$






                      share|cite|improve this answer











                      $endgroup$



                      Since $$ 14^2 equiv -2 $$ so $$14^{16} equiv (-2)^8 equiv 16^2equiv (-6)^2 equiv 14$$





                      or



                      $$ 14^2 = 22k -2 $$ so $$14^{16} = (22k-2)^8 = 22l+2^8=22l+22cdot 11+14$$







                      share|cite|improve this answer














                      share|cite|improve this answer



                      share|cite|improve this answer








                      edited Jul 3 '18 at 10:53

























                      answered Jul 3 '18 at 10:39









                      greedoidgreedoid

                      39.9k114798




                      39.9k114798























                          3












                          $begingroup$

                          A method that uses FLT.



                          Finding the remainder on dividing $14^{16}$ by $22$ is equivalent to twice that on dividing $7cdot14^{15}$ by $11$.



                          By FLT, $14^{10}equiv1pmod{11}$ so $$7cdot14^{15}equiv7cdot14^5equiv98cdot196cdot196equiv-1cdot(-2)cdot(-2)equiv-4equiv7pmod{11}$$ hence the required remainder is $7times 2=14$.






                          share|cite|improve this answer









                          $endgroup$


















                            3












                            $begingroup$

                            A method that uses FLT.



                            Finding the remainder on dividing $14^{16}$ by $22$ is equivalent to twice that on dividing $7cdot14^{15}$ by $11$.



                            By FLT, $14^{10}equiv1pmod{11}$ so $$7cdot14^{15}equiv7cdot14^5equiv98cdot196cdot196equiv-1cdot(-2)cdot(-2)equiv-4equiv7pmod{11}$$ hence the required remainder is $7times 2=14$.






                            share|cite|improve this answer









                            $endgroup$
















                              3












                              3








                              3





                              $begingroup$

                              A method that uses FLT.



                              Finding the remainder on dividing $14^{16}$ by $22$ is equivalent to twice that on dividing $7cdot14^{15}$ by $11$.



                              By FLT, $14^{10}equiv1pmod{11}$ so $$7cdot14^{15}equiv7cdot14^5equiv98cdot196cdot196equiv-1cdot(-2)cdot(-2)equiv-4equiv7pmod{11}$$ hence the required remainder is $7times 2=14$.






                              share|cite|improve this answer









                              $endgroup$



                              A method that uses FLT.



                              Finding the remainder on dividing $14^{16}$ by $22$ is equivalent to twice that on dividing $7cdot14^{15}$ by $11$.



                              By FLT, $14^{10}equiv1pmod{11}$ so $$7cdot14^{15}equiv7cdot14^5equiv98cdot196cdot196equiv-1cdot(-2)cdot(-2)equiv-4equiv7pmod{11}$$ hence the required remainder is $7times 2=14$.







                              share|cite|improve this answer












                              share|cite|improve this answer



                              share|cite|improve this answer










                              answered Jul 3 '18 at 14:12









                              TheSimpliFireTheSimpliFire

                              12.4k62460




                              12.4k62460























                                  2












                                  $begingroup$

                                  Using the Euclidean Algorithm



                                  Note that
                                  $$
                                  begin{align}
                                  14^{16}&equiv0&pmod2tag1
                                  end{align}
                                  $$
                                  Reducing mod $11$ and using Fermat's Little Theorem, we get
                                  $$
                                  begin{align}
                                  14^{16}
                                  &equiv3^6&pmod{11}\
                                  &equiv3&pmod{11}tag2
                                  end{align}
                                  $$
                                  Solving $11a+2b=1$ using the Euclidean Algorithm as implemented in this answer,
                                  $$
                                  begin{array}{r}
                                  &&5&2\hline
                                  1&0&1&-2\
                                  0&1&-5&11\
                                  11&2&1&0\
                                  end{array}tag3
                                  $$
                                  we have
                                  $$
                                  11(1)+2(-5)=1tag4
                                  $$
                                  from which we get
                                  $$
                                  begin{align}
                                  -10&equiv0&pmod2\
                                  -10&equiv1&pmod{11}
                                  end{align}tag5
                                  $$
                                  Multiplying $(5)$ by $3$ gives
                                  $$
                                  begin{align}
                                  -30&equiv0&pmod2\
                                  -30&equiv3&pmod{11}
                                  end{align}tag6
                                  $$





                                  Using the Chinese Remainder Theorem



                                  The Chinese Remainder Theorem says that the solution to $(6)$ is unique mod ${22}$. Thus, we get the smallest positive solution to be
                                  $$
                                  begin{align}
                                  14&equiv0&pmod2\
                                  14&equiv3&pmod{11}
                                  end{align}tag7
                                  $$
                                  Thus, $(1)$, $(2)$, and $(7)$ yields
                                  $$
                                  begin{align}
                                  14^{16}&equiv14&pmod{22}tag8
                                  end{align}
                                  $$






                                  share|cite|improve this answer









                                  $endgroup$


















                                    2












                                    $begingroup$

                                    Using the Euclidean Algorithm



                                    Note that
                                    $$
                                    begin{align}
                                    14^{16}&equiv0&pmod2tag1
                                    end{align}
                                    $$
                                    Reducing mod $11$ and using Fermat's Little Theorem, we get
                                    $$
                                    begin{align}
                                    14^{16}
                                    &equiv3^6&pmod{11}\
                                    &equiv3&pmod{11}tag2
                                    end{align}
                                    $$
                                    Solving $11a+2b=1$ using the Euclidean Algorithm as implemented in this answer,
                                    $$
                                    begin{array}{r}
                                    &&5&2\hline
                                    1&0&1&-2\
                                    0&1&-5&11\
                                    11&2&1&0\
                                    end{array}tag3
                                    $$
                                    we have
                                    $$
                                    11(1)+2(-5)=1tag4
                                    $$
                                    from which we get
                                    $$
                                    begin{align}
                                    -10&equiv0&pmod2\
                                    -10&equiv1&pmod{11}
                                    end{align}tag5
                                    $$
                                    Multiplying $(5)$ by $3$ gives
                                    $$
                                    begin{align}
                                    -30&equiv0&pmod2\
                                    -30&equiv3&pmod{11}
                                    end{align}tag6
                                    $$





                                    Using the Chinese Remainder Theorem



                                    The Chinese Remainder Theorem says that the solution to $(6)$ is unique mod ${22}$. Thus, we get the smallest positive solution to be
                                    $$
                                    begin{align}
                                    14&equiv0&pmod2\
                                    14&equiv3&pmod{11}
                                    end{align}tag7
                                    $$
                                    Thus, $(1)$, $(2)$, and $(7)$ yields
                                    $$
                                    begin{align}
                                    14^{16}&equiv14&pmod{22}tag8
                                    end{align}
                                    $$






                                    share|cite|improve this answer









                                    $endgroup$
















                                      2












                                      2








                                      2





                                      $begingroup$

                                      Using the Euclidean Algorithm



                                      Note that
                                      $$
                                      begin{align}
                                      14^{16}&equiv0&pmod2tag1
                                      end{align}
                                      $$
                                      Reducing mod $11$ and using Fermat's Little Theorem, we get
                                      $$
                                      begin{align}
                                      14^{16}
                                      &equiv3^6&pmod{11}\
                                      &equiv3&pmod{11}tag2
                                      end{align}
                                      $$
                                      Solving $11a+2b=1$ using the Euclidean Algorithm as implemented in this answer,
                                      $$
                                      begin{array}{r}
                                      &&5&2\hline
                                      1&0&1&-2\
                                      0&1&-5&11\
                                      11&2&1&0\
                                      end{array}tag3
                                      $$
                                      we have
                                      $$
                                      11(1)+2(-5)=1tag4
                                      $$
                                      from which we get
                                      $$
                                      begin{align}
                                      -10&equiv0&pmod2\
                                      -10&equiv1&pmod{11}
                                      end{align}tag5
                                      $$
                                      Multiplying $(5)$ by $3$ gives
                                      $$
                                      begin{align}
                                      -30&equiv0&pmod2\
                                      -30&equiv3&pmod{11}
                                      end{align}tag6
                                      $$





                                      Using the Chinese Remainder Theorem



                                      The Chinese Remainder Theorem says that the solution to $(6)$ is unique mod ${22}$. Thus, we get the smallest positive solution to be
                                      $$
                                      begin{align}
                                      14&equiv0&pmod2\
                                      14&equiv3&pmod{11}
                                      end{align}tag7
                                      $$
                                      Thus, $(1)$, $(2)$, and $(7)$ yields
                                      $$
                                      begin{align}
                                      14^{16}&equiv14&pmod{22}tag8
                                      end{align}
                                      $$






                                      share|cite|improve this answer









                                      $endgroup$



                                      Using the Euclidean Algorithm



                                      Note that
                                      $$
                                      begin{align}
                                      14^{16}&equiv0&pmod2tag1
                                      end{align}
                                      $$
                                      Reducing mod $11$ and using Fermat's Little Theorem, we get
                                      $$
                                      begin{align}
                                      14^{16}
                                      &equiv3^6&pmod{11}\
                                      &equiv3&pmod{11}tag2
                                      end{align}
                                      $$
                                      Solving $11a+2b=1$ using the Euclidean Algorithm as implemented in this answer,
                                      $$
                                      begin{array}{r}
                                      &&5&2\hline
                                      1&0&1&-2\
                                      0&1&-5&11\
                                      11&2&1&0\
                                      end{array}tag3
                                      $$
                                      we have
                                      $$
                                      11(1)+2(-5)=1tag4
                                      $$
                                      from which we get
                                      $$
                                      begin{align}
                                      -10&equiv0&pmod2\
                                      -10&equiv1&pmod{11}
                                      end{align}tag5
                                      $$
                                      Multiplying $(5)$ by $3$ gives
                                      $$
                                      begin{align}
                                      -30&equiv0&pmod2\
                                      -30&equiv3&pmod{11}
                                      end{align}tag6
                                      $$





                                      Using the Chinese Remainder Theorem



                                      The Chinese Remainder Theorem says that the solution to $(6)$ is unique mod ${22}$. Thus, we get the smallest positive solution to be
                                      $$
                                      begin{align}
                                      14&equiv0&pmod2\
                                      14&equiv3&pmod{11}
                                      end{align}tag7
                                      $$
                                      Thus, $(1)$, $(2)$, and $(7)$ yields
                                      $$
                                      begin{align}
                                      14^{16}&equiv14&pmod{22}tag8
                                      end{align}
                                      $$







                                      share|cite|improve this answer












                                      share|cite|improve this answer



                                      share|cite|improve this answer










                                      answered Jul 3 '18 at 15:05









                                      robjohnrobjohn

                                      266k27306629




                                      266k27306629






























                                          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%2f2839477%2fremainder-on-division-with-22%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

                                          Mario Kart Wii

                                          Understanding the size os this class of aleatory events

                                          Partial Derivative Guidance.