Divisibility of a number by $3$












1














I have to prove the following statement by induction:



$P(n):5^{3n} + 2^{n+1}$ is a multiple of $3$ for all $n in mathbb{N}$



I started with the base case for $n=1$, which is true, and then, by taking $P(n)$ as true, $P(n+1)$ gives me $125 * 5^{3n} + 2 * 2^{n+1}$, and I can't see how to prove that this is a multiple of $3$... any suggestions? Thanks in advance!






divisibility







share|cite|improve this question
























  • Edit: Thanks everyone, I really should have seen that!
    – JBuck
    Nov 27 at 0:17
















1














I have to prove the following statement by induction:



$P(n):5^{3n} + 2^{n+1}$ is a multiple of $3$ for all $n in mathbb{N}$



I started with the base case for $n=1$, which is true, and then, by taking $P(n)$ as true, $P(n+1)$ gives me $125 * 5^{3n} + 2 * 2^{n+1}$, and I can't see how to prove that this is a multiple of $3$... any suggestions? Thanks in advance!






divisibility







share|cite|improve this question
























  • Edit: Thanks everyone, I really should have seen that!
    – JBuck
    Nov 27 at 0:17














1












1








1







I have to prove the following statement by induction:



$P(n):5^{3n} + 2^{n+1}$ is a multiple of $3$ for all $n in mathbb{N}$



I started with the base case for $n=1$, which is true, and then, by taking $P(n)$ as true, $P(n+1)$ gives me $125 * 5^{3n} + 2 * 2^{n+1}$, and I can't see how to prove that this is a multiple of $3$... any suggestions? Thanks in advance!






divisibility







share|cite|improve this question















I have to prove the following statement by induction:



$P(n):5^{3n} + 2^{n+1}$ is a multiple of $3$ for all $n in mathbb{N}$



I started with the base case for $n=1$, which is true, and then, by taking $P(n)$ as true, $P(n+1)$ gives me $125 * 5^{3n} + 2 * 2^{n+1}$, and I can't see how to prove that this is a multiple of $3$... any suggestions? Thanks in advance!






divisibility




divisibility






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 26 at 23:01









Eevee Trainer

4,065530




4,065530










asked Nov 26 at 22:46









JBuck

336




336












  • Edit: Thanks everyone, I really should have seen that!
    – JBuck
    Nov 27 at 0:17


















  • Edit: Thanks everyone, I really should have seen that!
    – JBuck
    Nov 27 at 0:17
















Edit: Thanks everyone, I really should have seen that!
– JBuck
Nov 27 at 0:17




Edit: Thanks everyone, I really should have seen that!
– JBuck
Nov 27 at 0:17










6 Answers
6






active

oldest

votes


















2














Following your argument:



By Induction Hypothesis: $5^{3n}+2^{n+1}=3K$, for some $Kinmathbb N$, so $5^{3n}=3K-2^{n+1}$. Hence,
$$125cdot 5^{3n}+2cdot 2^{n+1}=125(3K-2^{n+1})+2cdot2^{n+1}=125cdot 3cdot K-123 cdot 2^{n-1}.$$
The first sumand is clearly divisible by 3 and the last one also, because $123=41cdot 3$.






share|cite|improve this answer





























    2














    No induction required here – lil' Fermat will do:



    $5^3equiv 2^3equiv 2mod 3$, so
    $$5^{3n}+2^{n+1}equiv 2^n+2^{n+1}=2^n(1+2)equiv 0mod 3.$$






    share|cite|improve this answer





















    • Great alternative.
      – MisterRiemann
      Nov 26 at 23:57










    • Unfortunately, I haven't studied modular arithmetic, but thanks anyway!
      – JBuck
      Nov 27 at 0:18










    • Well, in my opinion, you should study it for yourself. It simplifies many proofs, and can be taught (at an elementary level) from mid-school.
      – Bernard
      Nov 27 at 0:24



















    1














    $P(n)$ being true means that
    $$ 5^{3n}+2^{n+1} = 3k, $$
    for some $k in mathbb Z$. Now write
    $$ 125 cdot 5^{3n} + 2cdot2^{n+1} = 123 cdot 5^{3n} + 2 (5^{3n}+2^{3n}) = 3 cdot 41 cdot 5^{3n} + 2 cdot 3k = 3(41 cdot 5^{3n} + 2k). $$






    share|cite|improve this answer





























      1














      Write $125=123+2$ and use the fact that $123$ is divisible by $3$






      share|cite|improve this answer































        0














        Notice the following two facts:



        $$125 = 5^3 ;;; Rightarrow ;;; 125 cdot 5^{3n} = 5^{3n+3} = 5^{3(n+1)}$$
        $$2 cdot 2^{n+1} = 2^{(n+1)+1} = 2^{n+2}$$



        Recall further that you want to show $P(n+1)$ is true, i.e. $3$ divides $5^{3(n+1)} + 2^{(n+1)+1} = 5^{3(n+1)} + 2^{n+2}$.



        See how you might continue from there?






        share|cite|improve this answer





















        • Yeah, I clearly saw it after the other guys pointed it out, thanks!
          – JBuck
          Nov 27 at 0:19



















        0














        Calling $m_3 = 3m$ as a rule, we have



        $$
        5^{3n}+2^{n+1}=(126-1)^n +(3-1)(3-1)^n = m_3+(-1)^n+3 (p_3+(-1)^n)-(p_3+(-1)^n) = q_3 + (-1)^n-(-1)^n = q_3equiv 0 mod 3
        $$






        share|cite|improve this answer





















          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%2f3015053%2fdivisibility-of-a-number-by-3%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          6 Answers
          6






          active

          oldest

          votes








          6 Answers
          6






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          2














          Following your argument:



          By Induction Hypothesis: $5^{3n}+2^{n+1}=3K$, for some $Kinmathbb N$, so $5^{3n}=3K-2^{n+1}$. Hence,
          $$125cdot 5^{3n}+2cdot 2^{n+1}=125(3K-2^{n+1})+2cdot2^{n+1}=125cdot 3cdot K-123 cdot 2^{n-1}.$$
          The first sumand is clearly divisible by 3 and the last one also, because $123=41cdot 3$.






          share|cite|improve this answer


























            2














            Following your argument:



            By Induction Hypothesis: $5^{3n}+2^{n+1}=3K$, for some $Kinmathbb N$, so $5^{3n}=3K-2^{n+1}$. Hence,
            $$125cdot 5^{3n}+2cdot 2^{n+1}=125(3K-2^{n+1})+2cdot2^{n+1}=125cdot 3cdot K-123 cdot 2^{n-1}.$$
            The first sumand is clearly divisible by 3 and the last one also, because $123=41cdot 3$.






            share|cite|improve this answer
























              2












              2








              2






              Following your argument:



              By Induction Hypothesis: $5^{3n}+2^{n+1}=3K$, for some $Kinmathbb N$, so $5^{3n}=3K-2^{n+1}$. Hence,
              $$125cdot 5^{3n}+2cdot 2^{n+1}=125(3K-2^{n+1})+2cdot2^{n+1}=125cdot 3cdot K-123 cdot 2^{n-1}.$$
              The first sumand is clearly divisible by 3 and the last one also, because $123=41cdot 3$.






              share|cite|improve this answer












              Following your argument:



              By Induction Hypothesis: $5^{3n}+2^{n+1}=3K$, for some $Kinmathbb N$, so $5^{3n}=3K-2^{n+1}$. Hence,
              $$125cdot 5^{3n}+2cdot 2^{n+1}=125(3K-2^{n+1})+2cdot2^{n+1}=125cdot 3cdot K-123 cdot 2^{n-1}.$$
              The first sumand is clearly divisible by 3 and the last one also, because $123=41cdot 3$.







              share|cite|improve this answer












              share|cite|improve this answer



              share|cite|improve this answer










              answered Nov 26 at 22:52









              Tito Eliatron

              1,553622




              1,553622























                  2














                  No induction required here – lil' Fermat will do:



                  $5^3equiv 2^3equiv 2mod 3$, so
                  $$5^{3n}+2^{n+1}equiv 2^n+2^{n+1}=2^n(1+2)equiv 0mod 3.$$






                  share|cite|improve this answer





















                  • Great alternative.
                    – MisterRiemann
                    Nov 26 at 23:57










                  • Unfortunately, I haven't studied modular arithmetic, but thanks anyway!
                    – JBuck
                    Nov 27 at 0:18










                  • Well, in my opinion, you should study it for yourself. It simplifies many proofs, and can be taught (at an elementary level) from mid-school.
                    – Bernard
                    Nov 27 at 0:24
















                  2














                  No induction required here – lil' Fermat will do:



                  $5^3equiv 2^3equiv 2mod 3$, so
                  $$5^{3n}+2^{n+1}equiv 2^n+2^{n+1}=2^n(1+2)equiv 0mod 3.$$






                  share|cite|improve this answer





















                  • Great alternative.
                    – MisterRiemann
                    Nov 26 at 23:57










                  • Unfortunately, I haven't studied modular arithmetic, but thanks anyway!
                    – JBuck
                    Nov 27 at 0:18










                  • Well, in my opinion, you should study it for yourself. It simplifies many proofs, and can be taught (at an elementary level) from mid-school.
                    – Bernard
                    Nov 27 at 0:24














                  2












                  2








                  2






                  No induction required here – lil' Fermat will do:



                  $5^3equiv 2^3equiv 2mod 3$, so
                  $$5^{3n}+2^{n+1}equiv 2^n+2^{n+1}=2^n(1+2)equiv 0mod 3.$$






                  share|cite|improve this answer












                  No induction required here – lil' Fermat will do:



                  $5^3equiv 2^3equiv 2mod 3$, so
                  $$5^{3n}+2^{n+1}equiv 2^n+2^{n+1}=2^n(1+2)equiv 0mod 3.$$







                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Nov 26 at 23:38









                  Bernard

                  118k639112




                  118k639112












                  • Great alternative.
                    – MisterRiemann
                    Nov 26 at 23:57










                  • Unfortunately, I haven't studied modular arithmetic, but thanks anyway!
                    – JBuck
                    Nov 27 at 0:18










                  • Well, in my opinion, you should study it for yourself. It simplifies many proofs, and can be taught (at an elementary level) from mid-school.
                    – Bernard
                    Nov 27 at 0:24


















                  • Great alternative.
                    – MisterRiemann
                    Nov 26 at 23:57










                  • Unfortunately, I haven't studied modular arithmetic, but thanks anyway!
                    – JBuck
                    Nov 27 at 0:18










                  • Well, in my opinion, you should study it for yourself. It simplifies many proofs, and can be taught (at an elementary level) from mid-school.
                    – Bernard
                    Nov 27 at 0:24
















                  Great alternative.
                  – MisterRiemann
                  Nov 26 at 23:57




                  Great alternative.
                  – MisterRiemann
                  Nov 26 at 23:57












                  Unfortunately, I haven't studied modular arithmetic, but thanks anyway!
                  – JBuck
                  Nov 27 at 0:18




                  Unfortunately, I haven't studied modular arithmetic, but thanks anyway!
                  – JBuck
                  Nov 27 at 0:18












                  Well, in my opinion, you should study it for yourself. It simplifies many proofs, and can be taught (at an elementary level) from mid-school.
                  – Bernard
                  Nov 27 at 0:24




                  Well, in my opinion, you should study it for yourself. It simplifies many proofs, and can be taught (at an elementary level) from mid-school.
                  – Bernard
                  Nov 27 at 0:24











                  1














                  $P(n)$ being true means that
                  $$ 5^{3n}+2^{n+1} = 3k, $$
                  for some $k in mathbb Z$. Now write
                  $$ 125 cdot 5^{3n} + 2cdot2^{n+1} = 123 cdot 5^{3n} + 2 (5^{3n}+2^{3n}) = 3 cdot 41 cdot 5^{3n} + 2 cdot 3k = 3(41 cdot 5^{3n} + 2k). $$






                  share|cite|improve this answer


























                    1














                    $P(n)$ being true means that
                    $$ 5^{3n}+2^{n+1} = 3k, $$
                    for some $k in mathbb Z$. Now write
                    $$ 125 cdot 5^{3n} + 2cdot2^{n+1} = 123 cdot 5^{3n} + 2 (5^{3n}+2^{3n}) = 3 cdot 41 cdot 5^{3n} + 2 cdot 3k = 3(41 cdot 5^{3n} + 2k). $$






                    share|cite|improve this answer
























                      1












                      1








                      1






                      $P(n)$ being true means that
                      $$ 5^{3n}+2^{n+1} = 3k, $$
                      for some $k in mathbb Z$. Now write
                      $$ 125 cdot 5^{3n} + 2cdot2^{n+1} = 123 cdot 5^{3n} + 2 (5^{3n}+2^{3n}) = 3 cdot 41 cdot 5^{3n} + 2 cdot 3k = 3(41 cdot 5^{3n} + 2k). $$






                      share|cite|improve this answer












                      $P(n)$ being true means that
                      $$ 5^{3n}+2^{n+1} = 3k, $$
                      for some $k in mathbb Z$. Now write
                      $$ 125 cdot 5^{3n} + 2cdot2^{n+1} = 123 cdot 5^{3n} + 2 (5^{3n}+2^{3n}) = 3 cdot 41 cdot 5^{3n} + 2 cdot 3k = 3(41 cdot 5^{3n} + 2k). $$







                      share|cite|improve this answer












                      share|cite|improve this answer



                      share|cite|improve this answer










                      answered Nov 26 at 22:51









                      MisterRiemann

                      5,7691624




                      5,7691624























                          1














                          Write $125=123+2$ and use the fact that $123$ is divisible by $3$






                          share|cite|improve this answer




























                            1














                            Write $125=123+2$ and use the fact that $123$ is divisible by $3$






                            share|cite|improve this answer


























                              1












                              1








                              1






                              Write $125=123+2$ and use the fact that $123$ is divisible by $3$






                              share|cite|improve this answer














                              Write $125=123+2$ and use the fact that $123$ is divisible by $3$







                              share|cite|improve this answer














                              share|cite|improve this answer



                              share|cite|improve this answer








                              edited Nov 26 at 22:57

























                              answered Nov 26 at 22:51









                              Ross Millikan

                              291k23196370




                              291k23196370























                                  0














                                  Notice the following two facts:



                                  $$125 = 5^3 ;;; Rightarrow ;;; 125 cdot 5^{3n} = 5^{3n+3} = 5^{3(n+1)}$$
                                  $$2 cdot 2^{n+1} = 2^{(n+1)+1} = 2^{n+2}$$



                                  Recall further that you want to show $P(n+1)$ is true, i.e. $3$ divides $5^{3(n+1)} + 2^{(n+1)+1} = 5^{3(n+1)} + 2^{n+2}$.



                                  See how you might continue from there?






                                  share|cite|improve this answer





















                                  • Yeah, I clearly saw it after the other guys pointed it out, thanks!
                                    – JBuck
                                    Nov 27 at 0:19
















                                  0














                                  Notice the following two facts:



                                  $$125 = 5^3 ;;; Rightarrow ;;; 125 cdot 5^{3n} = 5^{3n+3} = 5^{3(n+1)}$$
                                  $$2 cdot 2^{n+1} = 2^{(n+1)+1} = 2^{n+2}$$



                                  Recall further that you want to show $P(n+1)$ is true, i.e. $3$ divides $5^{3(n+1)} + 2^{(n+1)+1} = 5^{3(n+1)} + 2^{n+2}$.



                                  See how you might continue from there?






                                  share|cite|improve this answer





















                                  • Yeah, I clearly saw it after the other guys pointed it out, thanks!
                                    – JBuck
                                    Nov 27 at 0:19














                                  0












                                  0








                                  0






                                  Notice the following two facts:



                                  $$125 = 5^3 ;;; Rightarrow ;;; 125 cdot 5^{3n} = 5^{3n+3} = 5^{3(n+1)}$$
                                  $$2 cdot 2^{n+1} = 2^{(n+1)+1} = 2^{n+2}$$



                                  Recall further that you want to show $P(n+1)$ is true, i.e. $3$ divides $5^{3(n+1)} + 2^{(n+1)+1} = 5^{3(n+1)} + 2^{n+2}$.



                                  See how you might continue from there?






                                  share|cite|improve this answer












                                  Notice the following two facts:



                                  $$125 = 5^3 ;;; Rightarrow ;;; 125 cdot 5^{3n} = 5^{3n+3} = 5^{3(n+1)}$$
                                  $$2 cdot 2^{n+1} = 2^{(n+1)+1} = 2^{n+2}$$



                                  Recall further that you want to show $P(n+1)$ is true, i.e. $3$ divides $5^{3(n+1)} + 2^{(n+1)+1} = 5^{3(n+1)} + 2^{n+2}$.



                                  See how you might continue from there?







                                  share|cite|improve this answer












                                  share|cite|improve this answer



                                  share|cite|improve this answer










                                  answered Nov 26 at 22:51









                                  Eevee Trainer

                                  4,065530




                                  4,065530












                                  • Yeah, I clearly saw it after the other guys pointed it out, thanks!
                                    – JBuck
                                    Nov 27 at 0:19


















                                  • Yeah, I clearly saw it after the other guys pointed it out, thanks!
                                    – JBuck
                                    Nov 27 at 0:19
















                                  Yeah, I clearly saw it after the other guys pointed it out, thanks!
                                  – JBuck
                                  Nov 27 at 0:19




                                  Yeah, I clearly saw it after the other guys pointed it out, thanks!
                                  – JBuck
                                  Nov 27 at 0:19











                                  0














                                  Calling $m_3 = 3m$ as a rule, we have



                                  $$
                                  5^{3n}+2^{n+1}=(126-1)^n +(3-1)(3-1)^n = m_3+(-1)^n+3 (p_3+(-1)^n)-(p_3+(-1)^n) = q_3 + (-1)^n-(-1)^n = q_3equiv 0 mod 3
                                  $$






                                  share|cite|improve this answer


























                                    0














                                    Calling $m_3 = 3m$ as a rule, we have



                                    $$
                                    5^{3n}+2^{n+1}=(126-1)^n +(3-1)(3-1)^n = m_3+(-1)^n+3 (p_3+(-1)^n)-(p_3+(-1)^n) = q_3 + (-1)^n-(-1)^n = q_3equiv 0 mod 3
                                    $$






                                    share|cite|improve this answer
























                                      0












                                      0








                                      0






                                      Calling $m_3 = 3m$ as a rule, we have



                                      $$
                                      5^{3n}+2^{n+1}=(126-1)^n +(3-1)(3-1)^n = m_3+(-1)^n+3 (p_3+(-1)^n)-(p_3+(-1)^n) = q_3 + (-1)^n-(-1)^n = q_3equiv 0 mod 3
                                      $$






                                      share|cite|improve this answer












                                      Calling $m_3 = 3m$ as a rule, we have



                                      $$
                                      5^{3n}+2^{n+1}=(126-1)^n +(3-1)(3-1)^n = m_3+(-1)^n+3 (p_3+(-1)^n)-(p_3+(-1)^n) = q_3 + (-1)^n-(-1)^n = q_3equiv 0 mod 3
                                      $$







                                      share|cite|improve this answer












                                      share|cite|improve this answer



                                      share|cite|improve this answer










                                      answered Nov 27 at 1:02









                                      Cesareo

                                      8,1833516




                                      8,1833516






























                                          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.





                                          Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                                          Please pay close attention to the following guidance:


                                          • 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.


                                          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%2f3015053%2fdivisibility-of-a-number-by-3%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

                                          Index of /

                                          This page is only for reference, If you need detailed information, please check here
                                          Read more

                                          Tribalistas

                                          Image
                                            Nota: Para o álbum homônimo, veja Tribalistas (álbum de 2002). Para o segundo álbum homônimo, veja Tribalistas (álbum de 2017). Para o tipo de organização tribal, veja Tribalismo. Tribalistas Informação geral Origem Salvador e Rio de Janeiro País   Brasil Gênero(s) MPB Pop Samba Período em atividade 2002–2004 2017–atualmente Gravadora(s) EMI Phonomotor Records Universal Music Afiliação(ões) Dadi Pretinho da Serrinha Margareth Menezes Integrantes Arnaldo Antunes Carlinhos Brown Marisa Monte Página oficial www2.uol.com.br/tribalistas/ ...
                                          Read more

                                          Listed building

                                          Image
                                          Listed building (literalmente: prédio listado ) é toda estrutura protegida por lei pelo complexo sistema de tombamento do Reino Unido. Um listed building é qualquer estrutura oficialmente designada como tendo especial interesse arquitetônico, histórico ou cultural. É um estatuto amplamente usado, aplicado a centenas de milhares de estruturas. Estruturas tombadas não podem ser alteradas sem permissão especial, e desfrutam de isenções fiscais e outros benefícios. Cada um dos países do Reino Unido trata tombamento de forma diferente: Índice 1 Inglaterra 2 País de Gales 3 Irlanda do Norte 4 Escócia 5 Referências Inglaterra | O Palácio de Buckingham, Londres. As estruturas tombadas são listadas no Statutory List of Buildings of Special Architectural or Historic Interest , e incluem campos, sinais de trânsito, piers e áreas geográficas. A principal legislação pertinente é o Ancient Monuments and Archaeological Areas Act 1979 , [ 1 ] embora legisla...
                                          Read more